Внимание!
Предложения и заявки заказчиков

Размещение рекламных материалов

коммерческая реализация изобретений - ООО 'Адвансед Девелопмент Проджект' смотреть>>>

Требуются разработки по средствам контроля и ограничения по количеству дисковых операций производимых одним пользователемдля хостинг провайдера. смотреть>>>

Требуются разработки по использованию низкопотенциальной энергии смотреть >>>

Количественная оценка похожести упорядоченных конечных множеств разнотипных элементов

  Количественная оценка похожести упорядоченных  конечных 
                       множеств   разнотипных   элементов

  
                                      Поле множеств

Под полем множеств Р здесь будет пониматься конечное упорядоченное
множество элементов - ячеек , в которые могут размещаться или не
размещаться элементы сравниваемых множеств. Если обозначить элемент
буквой "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  обозначает операцию суммирования переменных членов последовательности.

 

        
                    Область применения количественной
                      оценки похожести множеств




     Эта оценка может применяться в любой области  человеческой деятельности для сравнения объектов, чья структура может быть представлена
упорядоченным конечным множеством элементов.

 Например, сравнение и измерение похожести изображений , если
сравниваемые изображения можно представить в виде одинакового числа элементов (не обязательно точек).

Сравнение и измерение похожести кодов одинаковой длины и, естественно, одинаковой природы. Например, двоичный код или  генетический код.

  Этот адрес электронной почты защищен от спам-ботов. У вас должен быть включен JavaScript для просмотра.

Добавить комментарий


Защитный код
Обновить

Комментарии