Как найти меру сходства

Коэффициент сходства (также мера сходства, индекс сходства) — безразмерный показатель сходства сравниваемых объектов. Также известен под названиями «мера ассоциации», «мера подобия» и др.

Применяется в биологии для количественного определения степени сходства биологических объектов (участков, районов, отдельных фитоценозов, зооценозов и т. п.). Также применяются в географии, социологии, распознавании образов, поисковых системах, сравнительной лингвистике, биоинформатике, хемоинформатике, при сравнении строк и др.

В более широком смысле говорят о мерах близости к которым относятся: меры разнообразия, меры концентрации (однородности), меры включения, меры сходства, меры различия (в том числе расстояния), меры совместимости событий, меры несовместимости событий, меры взаимозависимости, меры взаимонезависимости. Теория мер близости находится в стадии становления и потому существует множество различных представлений о формализации отношений близости.

Большинство коэффициентов нормированы и находятся в диапазоне от 0 (сходство отсутствует) до 1 (полное сходство). Сходство и различие взаимодополняют друг друга (математически это можно выразить так: Сходство = 1 − Различие).

Коэффициенты сходства можно условно разделить на три группы в зависимости от того, какое число объектов рассматривается:

• унарные — рассматривается один объект. В эту группу входят меры разнообразия и меры концентрации.
• бинарные — рассматривается два объекта. Это наиболее известная группа коэффициентов.
• n-арные (многоместные) — рассматривается n объектов. Эта группа наименее известна.

Унарные коэффициенты[править | править код]

При изучении биологических объектов широко используются меры изменчивости как отдельных признаков, так и частот распределения случайных величин. В простейшем случае инвентаризационное (в пределах изучаемой биосистемы) разнообразие можно оценить видовым богатством, или числом видов.

Наиболее часто используются меры разнообразия^[1] (коэффициент вариации, индексы параметрического семейства Реньи, включая индекс Шеннона; индексы семейства Хилла; индексы Маргалефа, Глизона и др.). Реже используются дополняющие их меры концентрации (например, семейство мер Колмогорова, мера диссонанса Розенберга).

Бинарные коэффициенты[править | править код]

Это наиболее используемые в биологии и географии коэффициенты^[2]. Самый первый коэффициент сходства был предложен П. Жаккаром (Jaccard) в 1901 г.^[3] : , где а — количество видов на первой пробной площадке, b — количество видов на второй пробной площадке, с — количество видов, общих для 1-й и 2-й площадок.
Впоследствии в самых различных областях науки предлагались различные коэффициенты (меры, индексы) сходства. Наибольшее распространение получили (обозначения те же):

Известна альтернативная система обозначений для таблицы сопряжённости от Р. Р. Сокала (Sokal) и П.Снита (Sneath)^[10][11]:

где а — количество видов, встречаемых на обеих площадках; b — количество видов, встреченных на первой пробной площадке, но без учёта встречаемости общих видов; с — количество видов, встреченных на второй пробной площадке, но без учёта встречаемости общих видов.

Эта таблица создает большую путаницу. Её часто путают с похожей статистической таблицей сопряженности ; обозначения таблицы Сокала-Снита путают с классическими обозначениями (см. выше); почти всегда не учитывают того факта, что таблица рассматривает только вероятности.
В процессе математической формализации объектов и связей между ними возникла универсальная теоретико-множественная запись для коэффициентов сходства. Впервые такого рода запись появляется в работах А. С. Константинова^[12], М. Левандовского и Д. Винтер^[13]. Так, коэффициент сходства Жаккара может быть записан следующим образом:

или .

Наиболее простым коэффициентом сходства является мера абсолютного сходства, которая по сути является числом общих признаков двух сравниваемых объектов: ^[14]. При нормировке этой меры значения меры сходства заключены между 0 и 1 и коэффициент известен как «мера процентного сходства» при использовании относительных единиц измерения (в процентах) и как меры пересечения в промежуточных расчетах относительных мер сходства (например, за рубежом известна как мера Ренконена ^[15]).

В 1973 году Б. И. Сёмкиным была предложена общая формула на основе формулы среднего Колмогорова, объединяющая большую часть известных коэффициентов сходства в непрерывный континуум мер^[16][17]:

,

где ; ; ; ; ; . Например, значения для вышеприведённых коэффициентов имеют следующий вид: [1,-1] (коэффициент Жаккара); [0,-1] (коэффициент Серенсена); [0,1] (коэффициент Кульчинского); [0,0] (коэффициент Отиаи); [0, ] (коэффициент Шимкевича-Симпсона); [0, ] (коэффициент Браун-Бланке). Обобщающая формула позволяет определить классы эквивалентных и неэквивалентных коэффициентов^[18], а также предотвратить создание новых дублирующих коэффициентов.

Специфическим типом коэффициентов сходства являются меры включения. Это несимметричные меры ( и ), которые показывают степень сходства (включение) одного объекта относительно другого. Более привычные (симметричные) коэффициенты близости можно получить путём осреднения двух взаимодополняющих несимметричных мер включения, то есть каждой симметричной мере сходства соответствуют две определённые несимметричные меры сходства. Например, для меры Сёренсена это и ), а для меры Жаккара это и . В общем, две несимметричные меры включения лучше оценивают сходство объектов чем одна усреднённая симметричная мера сходства.

Спорным и неоднозначным является вопрос о сравнении объектов по весовым показателям. В экологии это показатели, учитывающие обилие. Наиболее последовательными схемами формализации таких типов являются схема Б. И. Сёмкина на основе дескриптивных множеств и схема А.Чао (Chao) с основанными на обилии индексами (abundance-based indices)^[19]. Также в зарубежной литературе устоялось представление индексах на основе инцидентности (incidence-based index), то есть индексах для булевых данных типа присутствие/отсутствие (presence/absence) признака. По сути, и те и другие могут быть описаны как частные случаи дескриптивных множеств.

Дискуссионными остаются сравнение случайных событий (например, встречаемость) и информационных показателей. В схеме формализации отношений близости Б. И. Сёмкина предлагается выделять ряд аналитических интерпретаций для различных отношений близости: множественная, дескриптивная, вероятностная, информационная.
Формально принадлежность к мерам сходства определяется системой аксиом (здесь E — произвольное множество):

1. (неотрицательность);
2. (симметричность);
3. («целое больше части»);
4. (субаддитивность).

Системы аксиом для мер сходства предлагали: А. Реньи^[20], Ю. А. Воронин^[21][22], А.Тверски^[23], А. А. Викентьев, Г. С. Лбов^[24], Г. В. Раушенбах^[25], Б. И. Сёмкин^[26][27] и др.

Как правило, совокупность мер близости представляют в виде матриц типа «объект-объект». Это, например, матрицы сходства, матрицы расстояний (в широком смысле — различия), матрицы совместных вероятностей, матрицы информационных функций. Большинство из них могут быть построены на основе: абсолютных или относительных мер, а они в свою очередь могут быть симметричными или несимметричными (последние часто называются мерами включения).

Многоместные коэффициенты[править | править код]

Такого рода коэффициенты используются для сравнения серии объектов. К ним относятся: среднее сходство Алёхина, индекс биотической дисперсии Коха, коэффициент рассеяния (дисперсности) Шенникова, мера бета-разнообразия Уиттекера ^[28], мера гомотонности и двойственная ей мера гетеротонности Миркина-Розенберга, коэффициент сходства серии описаний Сёмкина. В зарубежной литературе меры этого типа встречаются под названиями: многомерные коэффициенты, n-мерные коэффициенты, multiple-site similarity measure, multidimensional coefficient, multiple-community measure ^[29][30][31]. Наиболее известный коэффициент был предложен Л.Кохом^[32]:

,

где , то есть сумма числа признаков каждого из объектов; , то есть общее число признаков;  — совокупность n множеств (объектов).

Программное обеспечение для расчёта мер[править | править код]

Как правило, расчёт мер близости производится в модуле кластерного анализа программы. Наиболее часто используют Statistica, но в соответствующем модуле меры сходства не представлены совсем, только расстояния. В SPSS (PASW Statistics) предлагается расчёт ряда мер сходства (меры Охаи, Жаккара, Сокала-Снита, Кульчинского, симметричная Дайса). Малых программ для расчёта мер близости и последующего графического представления зависимостей существует огромное количество^[33][34]. Меры сходства же представлены крайне редко и в основном в специализированных программах для биологов^[35]: Graphs, NTSYS, BIODIV, PAST, причём даже там их крайне мало (обычно только мера Жаккара и иногда мера Сёренсена). Также можно отметить TurboVEG и IBIS^[36], в основе которых лежит база данных с модулями обработки, причём в программе IBIS реализовано наибольшее количество мер близости, используемых в настоящее время в биологии, географии и прочих областях.

См. также[править | править код]

• Метрическое пространство
• Биоразнообразие
• Задача классификации
• Кластерный анализ
• Взаимная информация
• Условная вероятность
• Биоценометрия
• Мера схожести строк^[en]*

Примечания[править | править код]

Метрики сходства и расстояния для науки о данных и машинного обучения

  Перевод

  Ссылка на автора

from scipy import spatialdef adjusted_cos_distance_matrix(size, matrix, row_column):
    distances = np.zeros((size,size))
    if row_column == 0:
        M_u = matrix.mean(axis=1)
        m_sub = matrix - M_u[:,None]
    if row_column == 1:
        M_u = matrix.T.mean(axis=1)
        m_sub = matrix.T - M_u[:,None]
    for first in range(0,size):
        for sec in range(0,size):
            distance = spatial.distance.cosine(m_sub[first],m_sub[sec])
            distances[first,sec] = distance
    return distances

user_similarity = adjusted_cos_distance_matrix(n_users,data_matrix,0)
item_similarity = adjusted_cos_distance_matrix(n_items,data_matrix,1)

В
кластерном анализе для количественной
оценки сходства объектов вводится
понятие метрики.
Сходство или различие
между классифицируемыми объектами
устанавливается в зависимости от
метрического расстояния между ними.
Если каждый объект описывается k
признаками, то он
может быть представлен как точка в
k-мерном
пространстве и сходство с другими
объектами будет определяться как
соответствующее расстояние. В кластерном
анализе используются различные меры
расстояния между объектами (метрики):

1) евклидово
расстояние:

2) взвешенное
евклидово расстояние:

3)
расстояние city–block:

4)
расстояние Минковского:

где
d_ij
– расстояние между
i-м
и j-м
объектами;

x_ik,
х_jk
– значения k-й
переменной соответственно у i-го
и j-го
объектов;

w_k
– вес,
приписываемый k-й
переменной.

Пример
8.4.
Определить сходство
между предприятиями, если каждое из них
характеризуется тремя признаками: Х₁
– производство
продукции, млрд руб; X₂
–
стоимость основных производственных
фондов, млрд руб.; X₃
–
фонд заработной платы
промышленно-производственного персонала,
млрд руб. (табл. 8.5, 8.6).

Таблица
8.5.Матрица исходных данных

№ п/п	X1	X2	X3
1	32,5	40,3	3,5
2	38,4	46,8	4,3
3	16,7	25.7	2,0
4	42,3	44,0	4,5

Таблица
8.6.Матрица евклидовых расстояний

Оценка сходства
между объектами сильно зависит от
абсолютного значения признака и от
степени его вариации в совокупности.
Чтобы устранить подобное влияние на
процедуру классификации, можно значения
исходных переменных нормировать одним
из следующих способов:

Продемонстрируем
на нашем примере, как скажется нормирование
исходных переменных на мерах сходства
между объектами. Заменим x_ij
новыми значениями
z_ij,
полученными по формуле

и построим матрицу
стандартизованных значений признаков
и новую матрицу расстояний (табл.8.7,
8.8).

В
первой матрице расстояний (табл.8.6)
самыми «близкими» были объекты п₁
и п₂
(d₁₂₌
8,81), а самыми «дальними»
–
объекты n₃
и n₄
(d₃₄=
31,57). После нормирования значений исходных
переменных самыми «близкими» стали
объекты n₂
и n₄
(d₂₄
= 0,56), а самыми «дальними» –
объекты n₂
и n₃
(d₂₃=13,2)
(табл. 8.7).

Таблица
8.7.Матрица стандартизованных
значений признаков

Таблица
8.8. Матрица
расстояний

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

Вопрос
о придании переменным соответствующих
весов должен решаться после проведения
исследователем тщательного анализа
изучаемой совокупности и
социально-экономической сущности
классифицирующих переменных. Веса
задаются пропорционально степени
важности переменных. Например, если для
классификации предприятий используются
переменные Х₁
– прибыль предприятия,
Х₂
– выработка продукции
на одного работающего, Х₃
– среднегодовая
стоимость основных производственных
фондов, то можно переменным задать веса
пропорционально их степени важности
для эффективности работы предприятия:

w_x1=0,6;
w_x2=0,3;
w_x3=0,l.

Тогда евклидово
расстояние будет определяться по формуле

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

Если
алгоритм кластеризации основан на
измерении сходства между переменными,
то в качестве мер сходства могут быть
использованы:

• линейные коэффициенты
  корреляции;

• коэффициенты
  ранговой корреляции;

• коэффициенты
  контингенции и т. д.

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

Соседние файлы в папке Тер вер и мат стат

• #
• #
• #
• #
• #
• #
• #
• #

From Wikipedia, the free encyclopedia

“Similarity matrix” redirects here. For the linear algebra concept, see Matrix similarity.

In statistics and related fields, a similarity measure or similarity function or similarity metric is a real-valued function that quantifies the similarity between two objects. Although no single definition of a similarity exists, usually such measures are in some sense the inverse of distance metrics: they take on large values for similar objects and either zero or a negative value for very dissimilar objects. Though, in more broad terms, a similarity function may also satisfy metric axioms.

Cosine similarity is a commonly used similarity measure for real-valued vectors, used in (among other fields) information retrieval to score the similarity of documents in the vector space model. In machine learning, common kernel functions such as the RBF kernel can be viewed as similarity functions.^[1]

Use of different similarity measure formulas[edit]

Different types of similarity measures exist for various types of objects, depending on the objects being compared. For each type of object there are various similarity measurement formulas.^[2]

There are many various options available when it comes to finding similarity between two data points, some of which are a combination of other similarity methods. Some of the methods for similarity measures between two data points include Euclidean distance, Manhattan distance, Minkowski distance, and Chebyshev distance. The Euclidean distance formula is used to find the distance between two points on a plane, which is visualized in the image below. Manhattan distance is commonly used in GPS applications, as it can be used to find the shortest route between two addresses. When you generalize the Euclidean distance formula and Manhattan distance formula you are left with the Minkowski distance formula, which can be used in a wide variety of applications.

Similarity between two data points

• Euclidean distance
• Manhattan distance
• Minkowski distance
• Chebyshev distance

For comparing strings, there are various measures of string similarity that can be used. Some of these methods include edit distance, Levenshtein distance, Hamming distance, and Jaro distance. The best-fit formula is dependent on the requirements of the application. For example, edit distance is frequently used for natural language processing applications and features, such as spell-checking. Jaro distance is commonly used in record linkage to compare first and last names to other sources.

Similarity between strings

• Edit distance
• Levenshtein distance
• Lee distance
• Hamming distance
• Jaro distance

When comparing probability distributions the Mahalanobis distance formula, Bhattacharyya distance formulas, and the Hellinger distance formula are all very powerful and useful. The Mahalanobis distance formula is commonly used in statistical analysis. It measures the distance between two probability distributions that have different means and variances. This makes it useful for finding outliers across the datasets. The Bhattacharyya distance formula is generally used in image processing, comparing two probability distributions that represent different categories. For example, can be used to classify images based on their features. Hellinger distance is a powerful tool for text mining and classifying documents. Generally, it is used on probability distributions that represent the frequency of different words, allowing you to find similar documents.

Similarity between two probability distributions

• Mahalanobis distance
• Bhattacharyya distance
• Hellinger distance

A set is a collection of items with no order or repetition. They are generally used to represent relationships or associations between objects or even people. The Jaacard index formula measures the similarity between two sets based on the number of items that are present in both sets relative to the total number of items. The Jaccard index is commonly used in recommendation systems and social media analysis. For example, could recommend a new application to download based on your previous downloads. The Sorensen similarity index also compares the number of items in both sets to the total number of items present but the weight for the number of shared items is larger. The Sorensen similarity index is commonly used in biology applications, measuring the similarity between two sets of genes or species.

Similarity between two sets

• Jaccard index
• Sorensen similarity index

Use in clustering[edit]

Clustering or Cluster analysis is a data mining technique that is used to discover patterns in data by grouping similar objects together. It involves partitioning a set of data points into groups or clusters based on their similarities. One of the fundamental aspects of clustering is how to measure similarity between data points.

Similarity measures play a crucial role in many clustering techniques, as they are used to determine how closely related two data points are and whether they should be grouped together in the same cluster. similarity measure can take many different forms depending on the type of data being clustered and the specific problem being solved.

One of the most commonly used similarity measures is the Euclidean distance, which is used in many clustering techniques including K-means clustering and Hierarchical clustering. The Euclidean distance is a measure of the straight-line distance between two points in a high-dimensional space. It is calculated as the square root of the sum of the squared differences between the corresponding coordinates of the two points. For example, if we have two data points and , the Euclidean distance between them is

Another commonly used similarity measure is the Jaccard index or Jaccard similarity, which is used in clustering techniques that work with binary data such as presence/absence data ^[3] or Boolean data; The Jaccard similarity is particularly useful for clustering techniques that work with text data, where it can be used to identify clusters of similar documents based on their shared features or keywords.^[4] It is calculated as the size of the intersection of two sets divided by the size of the union of the two sets.

Similarities among 162 Relevant Nuclear Profile are tested using the Jaccard Similarity measure (see figure with heatmap). The Jaccard similarity of the nuclear profile ranges from 0 to 1, with 0 indicating no similarity between the two sets and 1 indicating perfect similarity with the aim of clustering the most similar nuclear profile.

Manhattan distance, also known as Taxicab geometry , is a commonly used similarity measure in clustering techniques that work with continuous data. It is a measure of the distance between two data points in a high-dimensional space, calculated as the sum of the absolute differences between the corresponding coordinates of the two points.

In spectral clustering, a similarity, or affinity, measure is used to transform data to overcome difficulties related to lack of convexity in the shape of the data distribution.^[5] The measure gives rise to an -sized similarity matrix for a set of n points, where the entry in the matrix can be simply the (reciprocal of the) Euclidean distance between and , or it can be a more complex measure of distance such as the Gaussian .^[5] Further modifying this result with network analysis techniques is also common.^[6]

The choice of similarity measure depends on the type of data being clustered and the specific problem being solved. For example, working with continuous data such as gene expression data, the Euclidean distance or cosine similarity may be appropriate. If working with binary data such as the presence of a genomic loci in a nuclear profile, the Jaccard index may be more appropriate. Lastly, working with data that is arranged in a grid or lattice structure, such as image or signal processing data, the Manhattan distance is particularly useful for the clustering.

Use in recommender systems[edit]

Similarity measures are tools to develop recommender systems. It observes a user’s perception and liking of multiple items. On recommender systems, the method is using a distance calculation such as Euclidean Distance or Cosine Similarity to generate a similarity matrix with values representing the similarity of any pair of targets. Then, by analyzing and comparing the values in the matrix, it is possible to match two targets to a user’s preference or link users based on their marks. In this system, it is relevant to observe the value itself and the absolute distance between two values.^[7] Gathering this data can indicate a mark’s likeliness to a user as well as how mutually closely two marks are either rejected or accepted. It is possible then to recommend to a user targets with high similarity to the user’s likes.

Recommender systems are observed in multiple online entertainment platforms, in social media and streaming websites. The logic for the construction of this systems is based on similarity measures.^[8]

Use in sequence alignment[edit]

Similarity matrices are used in sequence alignment. Higher scores are given to more-similar characters, and lower or negative scores for dissimilar characters.

Nucleotide similarity matrices are used to align nucleic acid sequences. Because there are only four nucleotides commonly found in DNA (Adenine (A), Cytosine (C), Guanine (G) and Thymine (T)), nucleotide similarity matrices are much simpler than protein similarity matrices. For example, a simple matrix will assign identical bases a score of +1 and non-identical bases a score of −1. A more complicated matrix would give a higher score to transitions (changes from a pyrimidine such as C or T to another pyrimidine, or from a purine such as A or G to another purine) than to transversions (from a pyrimidine to a purine or vice versa).
The match/mismatch ratio of the matrix sets the target evolutionary distance.^[9][10] The +1/−3 DNA matrix used by BLASTN is best suited for finding matches between sequences that are 99% identical; a +1/−1 (or +4/−4) matrix is much more suited to sequences with about 70% similarity. Matrices for lower similarity sequences require longer sequence alignments.

Amino acid similarity matrices are more complicated, because there are 20 amino acids coded for by the genetic code, and so a larger number of possible substitutions. Therefore, the similarity matrix for amino acids contains 400 entries (although it is usually symmetric). The first approach scored all amino acid changes equally. A later refinement was to determine amino acid similarities based on how many base changes were required to change a codon to code for that amino acid. This model is better, but it doesn’t take into account the selective pressure of amino acid changes. Better models took into account the chemical properties of amino acids.

One approach has been to empirically generate the similarity matrices. The Dayhoff method used phylogenetic trees and sequences taken from species on the tree. This approach has given rise to the PAM series of matrices. PAM matrices are labelled based on how many nucleotide changes have occurred, per 100 amino acids.
While the PAM matrices benefit from having a well understood evolutionary model, they are most useful at short evolutionary distances (PAM10–PAM120). At long evolutionary distances, for example PAM250 or 20% identity, it has been shown that the BLOSUM matrices are much more effective.

The BLOSUM series were generated by comparing a number of divergent sequences. The BLOSUM series are labeled based on how much entropy remains unmutated between all sequences, so a lower BLOSUM number corresponds to a higher PAM number.

See also[edit]

• Affinity propagation
• Latent space – Embedding of data within a manifold based on a similarity function
• Similarity learning – Supervised learning of a similarity function
• Self-similarity matrix
• Semantic similarity – Natural language processing
• Similarity (network science) – in network analysis, when two nodes (or other more elaborate structures) fall in the same equivalence class
• Similarity (philosophy) – Relation of resemblance between objects
• Statistical distance – Distance between two statistical objects
• String metric – metric that measures the distance between two strings of text
• tf–idf – Number that reflects the importance of a word to a document in a corpus
• Recurrence plot, a visualization tool of recurrences in dynamical (and other) systems

References[edit]

• F. Gregory Ashby; Daniel M. Ennis (2007). “Similarity measures”. Scholarpedia. 2 (12): 4116. Bibcode:2007SchpJ…2.4116A. doi:10.4249/scholarpedia.4116.