Меры сходства и различия

Вычисление на языке программирования Python

К вычислению мер сходства и их доверительных интервалов на Python

Количественная характеристика сходства двух произвольных множеств одна из наиболее часто встречающихся задач при обработке нечисловых данных. Довольно легко представить себе ситуацию, например, когда необходимо сравнить два списка видов, полученных с различных мест, и количественно охарактеризовать сходство этих мест по видовому составу.  В реальном мире задача сравнения и определения сходства может куда более сложной. Множества могут состоять из разнородных элементов, оценивать сходство которых можно лишь исходя из специфики рассматриваемой задачи.

Тем не менее, в общем случае, сравнения двух произвольных множеств \(A\) и \(B\),  от создаваемой меры сходства справедливо потребовать (из соображений удобства использования и интерпретации), выполнение следующих свойств:

  1. мера сходства двух множеств должна быть неотрицательной и обращаться в нуль, когда сравниваемые множества не имеют общих элементов;
  2. даже в случае "полного сходства" множеств — отсутствия у них различных элементов, данная мера не должна быть слишком большой; удобно, чтобы диапазон возможных значений меры был в границах единичного интервала, при этом максимальное значение — 1 — достигалось при совпадении сравниваемых множеств.
  3. можно потребовать также выполнение условия монотонности (грубо говоря, если число общих элементов у сравниваемых множеств при сохранении их мощностей увеличивается, то и мера сходства множеств должна увеличиваться) и\или коммутативности (независимость от порядка сравниваемых множеств, т.е. \(\rho(A, B) = \rho(B, A)\), где \(\rho\) — конструируемая мера.

В XX веке было создано множество различных мер, в том числе, удовлетворяющих данным условиям. Перечислим некоторые наиболее часто использующиеся из них:

  1. Мера Жаккара \(J=\frac{|A \cap B|}{|A \cup B|}\)
  2. Мера Сёренсена-Чекановского-Дайса \(C = \frac{2 |A\cap B|}{| A\cup B| + |A\cap B|}\)
  3. Меры Браун-Бланке-Симпсона-Шимкевича \(\frac{|A\cap B|}{\min(|A|, |B|)}, \frac{|A\cap B|}{\max(|A|, |B|)}\)
  4. Мера Кульчинского \(\frac{|A\cap B|}{|A-B| + |B-A|}\)

В данных выражениях для коэффициентов сходства \(|X|\) — означает мощность множества (для множеств с конечным числом элементов, а именно такие и встречаются в прикладных задачах, это число элементов множества).

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

В среде статистического моделирования R для этих целей имеется удобный пакет sets, который помимо возможности работы с множествами включает в себя функционал для вычисления разнообразных мер сходства.

Здесь мы рассмотрим реализацию некоторых мер сходства на языке программирования Python.  Для этих целей мы создадим специальный класс, при инициализации которого будут подсчитываться: количество общих элементов в сравниваемых множеств, количество элементов в обоих множествах, количество элементов только в одном множестве и пр.

from collections import Counter


class Similarities:
    '''
    Base class for similarity coefficients computation

    Parameters
    ----------

        x, y -- an array like objects (multiset) to be compared

    Returns
    -------

       An instance of the class with properites `jaccard` and `dice`
       to access corresponding measures.
    '''

    def __init__(self, x, y):
        self._x = set(x)
        self._y = set(y)
        self._intersection = self._x.intersection(self._y)
        self._union = self._x.union(self._y)
        self._only_x = self._x - self._y
        self._only_y = self._y - self._x
        self._ca_x = Counter(x)
        self._ca_y = Counter(y)
        self.n_common = sum([min(self._ca_x[key], self._ca_y[key]) for key in self._intersection])
        self.n_x = sum([self._ca_x[key] for key in self._x])
        self.n_y = sum([self._ca_y[key] for key in self._y])
        self.n_only_x = self.n_x - self.n_common
        self.n_only_y = self.n_y - self.n_common
        self.n_union = self.n_only_x + self.n_only_y + self.n_common

    @property
    def jaccard(self):
        '''Computes Jaccard similatiry coefficient'''

        return float(self.n_common) / self.n_union

    @property
    def dice(self):
        '''Computes Dice similarity coefficient '''

        return 2.0 * self.n_common / (self.n_union + self.n_common)

Чтобы найти пересечения в случае мультимножеств (множеств элементов с повторениями) мы используем счетчик из стандартных коллекций Python: collections.Counter.  Найдя мощности пересечения, объединения множеств, вычислить меры сходства уже не составит труда (они оформлены в данном классе как свойства (properties) класса).

Рабочик код (с примером) можно загрузить  по ссылке:

Класс для вычисления мер сходства на Python (2,0 KB)

Доверительные интервалы для мер сходства

Работа с конечными множествами в свете теории вероятностей приводит к появлению дискретных распределений, что и происходит при попытке дать оценку значимости мер сходства. В своей книге по математическим методам в фаунистических исследованиях Песенко (1982) приводит отдельные (приближенные) формулы для оценки значимости подобного рода коэффициентов. Однако, имея в распоряжении такой "трактор" как персональный компьютер, нетрудно организовать процедуру bootstrap-построения доверительных интервалов для коэффициентов сходства. Для этого, достаточно рассмотреть дополнительную функцию, которая производит формирование имитационных сравниваемых множеств:

 

def bootstrap_similarities(set1, set2, nsamples = 1000, similarity = 'jaccard'):
    import scipy.stats as st
    import numpy as np 
    X = []
    for i in range(nsamples):
        resample1 = [set1[j] for j in st.randint.rvs(0, len(set1)-1, size=len(set1))]
        resample2 = [set2[j] for j in st.randint.rvs(0, len(set2)-1, size=len(set2))]
        sim = Similarities(resample1, resample2)
        X.append(getattr(sim, similarity))
    return np.median(X), np.percentile(X, 5), np.percentile(X, 95)

Теперь, для нахождения 95% доверительного интервала достаточно вызвать bootstrap_similarities(x, y), чтобы получить требуемые оценки.

Параметризация мер сходства

Меры сходства удобный инструмент, позволяющий внести объективность при сравнении произвольных множеств. В основе конструирования мер лежат общие требования об их желаемых свойствах. Но кроме общих постулируемых свойств, многие из мер сходства, могут быть получены как частные случаи одного общего выражения.

Рассмотрим двухпараметрическое семейство мер сходства, которое предложил Б.И. Семкин (2010): $$
\begin{array}{l} K_{\tau;\eta} =\left( \dfrac{K_{\tau}^{\eta}(A,B)+K_{\tau}^{\eta}(B,A)}{2}\right)^{1/\eta}, \\ K_{\tau}(A,B) = \dfrac{|A\cap B|}{(1+\tau)|A|-\tau|A\cap B|}, K_{\tau}(B,A) = \dfrac{|A\cap B|}{(1+\tau)|B|-\tau|A\cap B|} \\ -1<\tau<\infty, -\infty<\eta<\infty \end{array}
$$

В этом случае \(K_{0;-1}\) и \(K_{1;-1}\) совпадают с коэффициентами Сёренсена-Дайса и Жаккара соответственно. Данная параметризация указывает на определенную эквивалентность  мер сходства и наталкивает на необходимость дополнения одним двухпараметрическим методом класс Similarities:

    def semkin(self, tau, eta):
        ktau_ab = self.n_common / ((1.0 + tau) * self.n_x - tau * self.n_common)
        ktau_ba = self.n_common / ((1.0 + tau) * self.n_y - tau * self.n_common)
        return (0.5 * (ktau_ab ** eta + ktau_ba ** eta)) ** (1.0 / eta)

В отличие от свойств jaccard и dice, метод semkin следует вызывать с параметрами; в случае вызова instance.semkin(1,-1)  результат будет совпадать c instance.jaccard.
 

blog comments powered by Disqus