http://moiidei.com/nauka-estestvennyie/kolichestvennaya-otsenka-pohozhesti-uporyadochennyih-konechnyih-mnozhestv-raznotipnyih-element.html
Количественная оценка похожести упорядоченных конечных
множеств разнотипных элементов
Поле множеств
Под полем множеств Р здесь будет пониматься конечное упорядоченное
множество элементов - ячеек , в которые могут размещаться или не
размещаться элементы сравниваемых множеств. Если обозначить элемент
буквой "a" , то графически поле множеств с числом ячеек n(P) = 32 можно представить, например, так
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa (P1)
aaaa
aaaa aa
aaaa aaaaaa
или так aaaa (P2) или так aaaaaaaa (P3)
aaaa aaaaaaaa
aaaa aaaaaa
aaaa aa
aaaa
В дальнейшем мы будем пользоваться в основном представлением (Р1) для удобства записи.
Сравниваемые бинарные множества
Сначала мы будем рассматривать бинарные множества, т.е. множества
двоичных элементов S. Примерами таких элементов могут служить чёрная и
белая точки, 1 и 0, слова "да" и "нет" и пр.
Вот один из примеров множества нулей и единиц на поле множеств Р
10001110001101101100011101011100 (S1)
Другой пример
10101110001101101101010101011100 (S2)
Вопрос: насколько похожи эти два множества?
В принципе, для классических множеств, которые состоят из элементов одного типа, существует такая оценка. Она называется коэффициентом Жаккара J(Jaccard) , который вычисляется как отношение числа элементов пересечения
двух множеств к числу элементов объединения этих множеств. Коэффициент
равен нулю, когда множества не имеют общих элементов, и единице, когда множества равны, в остальных случаях значение где-то посередине.
Этот коэффициент нельзя напрямую применить к множествам типа S1 и S2, состоящим из двух видов элементов, но можно его модернизировать применительно к таким множествам.
Для этого введём нумерацию ячеек поля множеств Р.
Тогда каждое из множеств S на поле множеств Р можно представить как
объединение подмножества номеров ячеек C1S поля Р, в которых содержатся
элементы 1 и подмножества номеров ячеек C0S поля Р, в которых содержатся
элементы 0. При таком представлении множеств похожесть двух множеств S1
и S2 можно определить как разность похожестей двух подмножеств.
Будем обозначать число элементов произвольного множества S как n(S), а
похожесть множеств S1, S2 как J(S1,S2).
Тогда n(C1S1ПC1S2) обозначает число элементов 1 в пересечении множеств C1S1,C1S2, а n(C0S1ПC0S2) обозначает число элементов 0 в пересечении множеств C0S1,C0S2.
Знак "П" обозначает операцию пересечения множеств.
Соответственно, n(C1S1UC1S2) обозначает число элементов 1 в объединении множеств C1S1,C1S2, а n(C0S1UC0S2) обозначает число элементов 0 в объединении множеств C0S1,C0S2.
Знак "U" обозначает операцию объединения множеств .
Тогда
J(C1S1,C1S2) = n(C1S1ПC1S2) / n(C1S1UC1S2) ;
J(C0S1,C0S2) = n(C0S1ПC0S2) / n(C0S1UC0S2) ;
знак "/" обозначает операцию деления (отношения).
Найдём значение cхожести для множеств S1 и S2, которую обозначим
как J(S1,S2).
Введём нумерацию ячеек для поля множеств P1.
0 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031
a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a P1
Соответственно, множества S1 и S2
0 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031
1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 1 0 0 S1
0 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031
1 0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 S2
Множества C1S1,C1S2
C1S1 = {0,4,5,6,10,11,13,14,16,17,21,22,23,25,27,28,29}
C1S2 = {0,2,4,5,6,10,11,13,14,16,17,19,21,23,25,27,28,29}
их пересечение
C1S1ПC1S2 = {0,4,5,6,10,11,13,14,16,17,21,23,25,27,28,29}
Число элементов в пересечении n(C1S1ПC1S2) = 16
Объединение этих множеств
C1S1UC1S2 ={0,2,4,5,6,10,11,13,14,16,17,19,21,22,23,25,27,28,29}
Число элементов в объединении n(C1S1UC1S2) = 19
Тогда похожесть множеств C1S1,C1S2 равна
J(C1S1,C1S2) = n(C1S1ПC1S2)/ n(C1S1UC1S2) = 16/19 = 0,842;
Проделаем те же операции над множествами C0S1,C0S2
C0S1 = {1,2,3,7,8,9,12,15,18,19,20,24,26,30,31}
С0S2 = {1,3,7,8,9,12,15,18,20,22,24,26,30,31}
их пересечение
C0S1ПC0S2 = {1,3,7,8,9,12,15,18,20,24,26,30,31}
Число элементов в пересечении n(C0S1ПC0S2) = 13
Объединение этих множеств
C0S1UC0S2 = {1,2,3,7,8,9,12,15,18,19,20,22,24,26,30,31}
Число элементов в объединении n(C0S1UC0S2) = 16
Тогда похожесть множеств C0S1,C0S2 равна
J(C0S1,C0S2) = n(C0S1ПC0S2) / n(C0S1UC0S2)= 13/16 = 0,8125;
Пока что мы нашли схожести двух пар множеств двух типов на поле P - пары множеств C1S1,C1S2 с элементами 1 и пары множеств C0S1,C0S2 с
элементами 0.
А какова схожесть множеств S1 и S2 в целом?
Понятно, что схожести этих множеств C1S1,C1S2 и C0S1,C0S2
определяют и схожесть множеств S1 и S2, но в какой мере?
Введём понятия веса пары подмножеств, например C1S1,C1S2 или
С0S1,C0S2 на поле P как отношение числа элементов в объединении
пары к общему числу элементов поля P. Тогда
w(C1S1,C1S2 ) = n(C1S1UC1S2)/n(P)= 19/32 = 0.594;
w(C0S1,C0S2 ) = n(C0S1UC0S2)/n(P)= 16/32 = 0.5,
где символом w обозначен вес каждой пары множеств на
поле P.
И, наконец, найдём схожесть множеств S1 и S2 по следующей формуле
(знак * обозначает операцию умножения, а знак + обозначает операцию
сложения)
J(S1,S2) = J(C1S1,C1S2) *w(C1S1,C1S2 ) + J(C0S1,C0S2) * w(C0S1,C0S2 )
= 0.842*0.594+0.812*0.5 = 0.906
Количественная оценка похожести множеств с
разнотипными элементами
Выше была предложена методика и формула для вычисления величины похожести двух множеств на поле P , каждое из которых содержит элементы
двух типов.
Принципы, заложенные в предложенных методике и формуле, могут быть распространены и на вычисление похожести двух множеств на поле P,
каждое из которых содержит элементы, число типов которых превышает 2. Например, множества могут содержать не только белые и чёрные точки, но и серые точки разной степени серости, а также цветные точки. .
Пусть имеется поле P с числом ячеек n(P).
На этом поле последовательно сформированы два множества
разнотипных элементов S1 и S2 с разным, в общем случае, числом типов
элементов.
0 1 2 3 4.............63 64........................1278 1279..............n-1 P
a b b c d.............d c ......................... a e.............. k S1
b k b c d.............c c.............................b e .............. l S2
Отметим, кстати, что каждое множество может содержать и пустые
элементы, т.е. незаполненные ячейки "a" на поле P, которые тоже рассматриваются как один из типов элементов множеств S1,S2.
Типы элементов (a, b, c, d, ...,e,...,k,l, ...) множеств S1 и S2 тоже можно рассматривать как множества соответственно T1и T2, которые образуют объединённое множество
T1UT2;
с соответствующим общим числом типов n(T1UT2).
Введём переменную t и упорядочим множество T1UT2, введя нумерацию типов
от 0 до n(T1UT2), и найдём все множества ячеек множеств на поле P
для S1,S2 и для всех типов элементов от 0 до n(T1UT2)
C0S1, C1S1, C2S1, ..., CtS1,..., Cn(T1UT2)S1
C0S2, C1S2, C2S2, ..., CtS2,..., Cn(T1UT2)S2
Затем находим пересечения вышеприведенных множеств
C0S1ПC0S2, C1S1ПC1S2 , ... CtS1ПCtS2 , ... Cn(T1UT2)S1ПCn(T1UT2)S2
и их объединения
C0S1UC0S2, C1S1UC1S2 , ... CtS1UCtS2 ,... Cn(T1UT2)S1UCn(T1UT2)S2
Для каждого пересечения и объединения находим число элементов
n(C0S1ПC0S2), n(C1S1ПC1S2) ,...n(CtS1ПCtS2) ,...n(Cn(T1UT2)S1ПCn(T1UT2)S2)
n(C0S1UC0S2), n(C1S1UC1S2) ,...n(CtS1UCtS2) ,... n(Cn(T1UT2)S1UCn(T1UT2)S2)
Для каждой пары множеств CtS1, CtS2 вычисляем значение похожести по
формуле
J(CtS1,CtS2) = n(CtS1ПCtS2) / n(CtS1UCtS2)
Затем для каждой пары множеств CtS1,CtS2 вычисляем вес по формуле
w(CtS1,CtS2 ) = = n(CtS1UCtS2)/n(P)
И, наконец, найдём схожесть множеств S1 и S2 по следующей формуле
t=n(T1UT2)-1
J(S1,S2) = E J(CtS1,CtS2) * w(CtS1,CtS2 ) ,
t=0
где символ E обозначает операцию суммирования переменных членов последовательности.
Область применения количественной
оценки похожести множеств
Эта оценка может применяться в любой области человеческой деятельности для сравнения объектов, чья структура может быть представлена
упорядоченным конечным множеством элементов.
Например, сравнение и измерение похожести изображений , если
сравниваемые изображения можно представить в виде одинакового числа элементов (не обязательно точек).
Сравнение и измерение похожести кодов одинаковой длины и, естественно, одинаковой природы. Например, двоичный код или генетический код.
Количественная оценка похожести упорядоченных конечных
множеств разнотипных элементов
Поле множеств
Под полем множеств Р здесь будет пониматься конечное упорядоченное
множество элементов - ячеек , в которые могут размещаться или не
размещаться элементы сравниваемых множеств. Если обозначить элемент
буквой "a" , то графически поле множеств с числом ячеек n(P) = 32 можно представить, например, так
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa (P1)
aaaa
aaaa aa
aaaa aaaaaa
или так aaaa (P2) или так aaaaaaaa (P3)
aaaa aaaaaaaa
aaaa aaaaaa
aaaa aa
aaaa
В дальнейшем мы будем пользоваться в основном представлением (Р1) для удобства записи.
Сравниваемые бинарные множества
Сначала мы будем рассматривать бинарные множества, т.е. множества
двоичных элементов S. Примерами таких элементов могут служить чёрная и
белая точки, 1 и 0, слова "да" и "нет" и пр.
Вот один из примеров множества нулей и единиц на поле множеств Р
10001110001101101100011101011100 (S1)
Другой пример
10101110001101101101010101011100 (S2)
Вопрос: насколько похожи эти два множества?
В принципе, для классических множеств, которые состоят из элементов одного типа, существует такая оценка. Она называется коэффициентом Жаккара J(Jaccard) , который вычисляется как отношение числа элементов пересечения
двух множеств к числу элементов объединения этих множеств. Коэффициент
равен нулю, когда множества не имеют общих элементов, и единице, когда множества равны, в остальных случаях значение где-то посередине.
Этот коэффициент нельзя напрямую применить к множествам типа S1 и S2, состоящим из двух видов элементов, но можно его модернизировать применительно к таким множествам.
Для этого введём нумерацию ячеек поля множеств Р.
Тогда каждое из множеств S на поле множеств Р можно представить как
объединение подмножества номеров ячеек C1S поля Р, в которых содержатся
элементы 1 и подмножества номеров ячеек C0S поля Р, в которых содержатся
элементы 0. При таком представлении множеств похожесть двух множеств S1
и S2 можно определить как разность похожестей двух подмножеств.
Будем обозначать число элементов произвольного множества S как n(S), а
похожесть множеств S1, S2 как J(S1,S2).
Тогда n(C1S1ПC1S2) обозначает число элементов 1 в пересечении множеств C1S1,C1S2, а n(C0S1ПC0S2) обозначает число элементов 0 в пересечении множеств C0S1,C0S2.
Знак "П" обозначает операцию пересечения множеств.
Соответственно, n(C1S1UC1S2) обозначает число элементов 1 в объединении множеств C1S1,C1S2, а n(C0S1UC0S2) обозначает число элементов 0 в объединении множеств C0S1,C0S2.
Знак "U" обозначает операцию объединения множеств .
Тогда
J(C1S1,C1S2) = n(C1S1ПC1S2) / n(C1S1UC1S2) ;
J(C0S1,C0S2) = n(C0S1ПC0S2) / n(C0S1UC0S2) ;
знак "/" обозначает операцию деления (отношения).
Найдём значение cхожести для множеств S1 и S2, которую обозначим
как J(S1,S2).
Введём нумерацию ячеек для поля множеств P1.
0 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031
a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a P1
Соответственно, множества S1 и S2
0 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031
1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 1 0 0 S1
0 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031
1 0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 S2
Множества C1S1,C1S2
C1S1 = {0,4,5,6,10,11,13,14,16,17,21,22,23,25,27,28,29}
C1S2 = {0,2,4,5,6,10,11,13,14,16,17,19,21,23,25,27,28,29}
их пересечение
C1S1ПC1S2 = {0,4,5,6,10,11,13,14,16,17,21,23,25,27,28,29}
Число элементов в пересечении n(C1S1ПC1S2) = 16
Объединение этих множеств
C1S1UC1S2 ={0,2,4,5,6,10,11,13,14,16,17,19,21,22,23,25,27,28,29}
Число элементов в объединении n(C1S1UC1S2) = 19
Тогда похожесть множеств C1S1,C1S2 равна
J(C1S1,C1S2) = n(C1S1ПC1S2)/ n(C1S1UC1S2) = 16/19 = 0,842;
Проделаем те же операции над множествами C0S1,C0S2
C0S1 = {1,2,3,7,8,9,12,15,18,19,20,24,26,30,31}
С0S2 = {1,3,7,8,9,12,15,18,20,22,24,26,30,31}
их пересечение
C0S1ПC0S2 = {1,3,7,8,9,12,15,18,20,24,26,30,31}
Число элементов в пересечении n(C0S1ПC0S2) = 13
Объединение этих множеств
C0S1UC0S2 = {1,2,3,7,8,9,12,15,18,19,20,22,24,26,30,31}
Число элементов в объединении n(C0S1UC0S2) = 16
Тогда похожесть множеств C0S1,C0S2 равна
J(C0S1,C0S2) = n(C0S1ПC0S2) / n(C0S1UC0S2)= 13/16 = 0,8125;
Пока что мы нашли схожести двух пар множеств двух типов на поле P - пары множеств C1S1,C1S2 с элементами 1 и пары множеств C0S1,C0S2 с
элементами 0.
А какова схожесть множеств S1 и S2 в целом?
Понятно, что схожести этих множеств C1S1,C1S2 и C0S1,C0S2
определяют и схожесть множеств S1 и S2, но в какой мере?
Введём понятия веса пары подмножеств, например C1S1,C1S2 или
С0S1,C0S2 на поле P как отношение числа элементов в объединении
пары к общему числу элементов поля P. Тогда
w(C1S1,C1S2 ) = n(C1S1UC1S2)/n(P)= 19/32 = 0.594;
w(C0S1,C0S2 ) = n(C0S1UC0S2)/n(P)= 16/32 = 0.5,
где символом w обозначен вес каждой пары множеств на
поле P.
И, наконец, найдём схожесть множеств S1 и S2 по следующей формуле
(знак * обозначает операцию умножения, а знак + обозначает операцию
сложения)
J(S1,S2) = J(C1S1,C1S2) *w(C1S1,C1S2 ) + J(C0S1,C0S2) * w(C0S1,C0S2 )
= 0.842*0.594+0.812*0.5 = 0.906
Количественная оценка похожести множеств с
разнотипными элементами
Выше была предложена методика и формула для вычисления величины похожести двух множеств на поле P , каждое из которых содержит элементы
двух типов.
Принципы, заложенные в предложенных методике и формуле, могут быть распространены и на вычисление похожести двух множеств на поле P,
каждое из которых содержит элементы, число типов которых превышает 2. Например, множества могут содержать не только белые и чёрные точки, но и серые точки разной степени серости, а также цветные точки. .
Пусть имеется поле P с числом ячеек n(P).
На этом поле последовательно сформированы два множества
разнотипных элементов S1 и S2 с разным, в общем случае, числом типов
элементов.
0 1 2 3 4.............63 64........................1278 1279..............n-1 P
a b b c d.............d c ......................... a e.............. k S1
b k b c d.............c c.............................b e .............. l S2
Отметим, кстати, что каждое множество может содержать и пустые
элементы, т.е. незаполненные ячейки "a" на поле P, которые тоже рассматриваются как один из типов элементов множеств S1,S2.
Типы элементов (a, b, c, d, ...,e,...,k,l, ...) множеств S1 и S2 тоже можно рассматривать как множества соответственно T1и T2, которые образуют объединённое множество
T1UT2;
с соответствующим общим числом типов n(T1UT2).
Введём переменную t и упорядочим множество T1UT2, введя нумерацию типов
от 0 до n(T1UT2), и найдём все множества ячеек множеств на поле P
для S1,S2 и для всех типов элементов от 0 до n(T1UT2)
C0S1, C1S1, C2S1, ..., CtS1,..., Cn(T1UT2)S1
C0S2, C1S2, C2S2, ..., CtS2,..., Cn(T1UT2)S2
Затем находим пересечения вышеприведенных множеств
C0S1ПC0S2, C1S1ПC1S2 , ... CtS1ПCtS2 , ... Cn(T1UT2)S1ПCn(T1UT2)S2
и их объединения
C0S1UC0S2, C1S1UC1S2 , ... CtS1UCtS2 ,... Cn(T1UT2)S1UCn(T1UT2)S2
Для каждого пересечения и объединения находим число элементов
n(C0S1ПC0S2), n(C1S1ПC1S2) ,...n(CtS1ПCtS2) ,...n(Cn(T1UT2)S1ПCn(T1UT2)S2)
n(C0S1UC0S2), n(C1S1UC1S2) ,...n(CtS1UCtS2) ,... n(Cn(T1UT2)S1UCn(T1UT2)S2)
Для каждой пары множеств CtS1, CtS2 вычисляем значение похожести по
формуле
J(CtS1,CtS2) = n(CtS1ПCtS2) / n(CtS1UCtS2)
Затем для каждой пары множеств CtS1,CtS2 вычисляем вес по формуле
w(CtS1,CtS2 ) = = n(CtS1UCtS2)/n(P)
И, наконец, найдём схожесть множеств S1 и S2 по следующей формуле
t=n(T1UT2)-1
J(S1,S2) = E J(CtS1,CtS2) * w(CtS1,CtS2 ) ,
t=0
где символ E обозначает операцию суммирования переменных членов последовательности.
Область применения количественной
оценки похожести множеств
Эта оценка может применяться в любой области человеческой деятельности для сравнения объектов, чья структура может быть представлена
упорядоченным конечным множеством элементов.
Например, сравнение и измерение похожести изображений , если
сравниваемые изображения можно представить в виде одинакового числа элементов (не обязательно точек).
Сравнение и измерение похожести кодов одинаковой длины и, естественно, одинаковой природы. Например, двоичный код или генетический код.
