Метрика схожості категоріальних розподілів, що враховує спорідненість різних категорій

Abstract

Оцінювання схожості двох об’єктів — це поширена задача в розпізнаванні образів, кластеризації та класифікації. Прикладами таких задач є підбір рецензентів наукових робіт, аналіз схожості текстових документів, ідентифікація поз людей у відеоряді, кластеризація природних ареалів, формування рекомендацій в інтернет-магазинах тощо. У випадку категоріальних атрибутів об’єкти описуються деяким розподілом ступенів належності за категоріями. Метрики схожості таких розподілів зазвичай є суперпозицією схожості об’єктів за кожною категорією. Найчастіше це сума схожості за окремими категоріями. При цьому, кожна категорія розглядається незалежно та ізольовано від інших. В деяких практичних задачах категорії є спорідненими. Тому схожість між об’єктами доцільно розраховувати не лише напряму, як схожість між еквівалентними категоріями, але враховувати і непряму, перехресну схожість через споріднені категорії. Саме така метрика схожості двох категоріальних розподілів, що враховує спорідненість різних категорій, і пропонується у статті. Метрика має дві складові. Перша складова реалізована метрикою Чекановського. Вона визначає пряму схожість розподілів за категоріями як суму перетину розподілів належностей двох об’єктів. Після перетину розподілів залишаються залишки, які і враховуються другою складовою запропонованої метрики. Друга складова метрики є сумою поелементного добутку двох матриць: матриці композиції залишків належності двох категоріальних розподілів та матриці попарної спорідненості категорій. Передбачається, що коефіцієнти спорідненості кожної пари категорій є відомими. Встановлено, що за великої кількості категорій сумарний шумовий внесок від слабо споріднених категорій є значним. Тому запропоновано цей шум фільтрувати і враховувати лише внесок від сильно споріднених категорій.

Estimating a level of similarity of two objects is a common problem in pattern recognition, clustering and classification. Among these problems can be reviewer recommendation, similar text documents analysis, human pose detection in video, species distribution clustering, recommendation in internet-shops etc. In case of categorical attributes an object is described as a distribution of membership degrees over categories. Similarity metrics of such distributions are usually defined as a superposition of objects’ similarities for each category. Most often it is a sum of similarities in separate categories. In addition to that each category is considered independently and in isolation from the others. Some practical problems have categories that are kinship. Therefore, it is expedient to consider objects’ similarity not only directly, as a similarity between equivalent categories, but it is also necessary to consider an indirect similarity, cross-similarity through kinship categories. It is such similarity metric of two categorical distributions that accounts for the kinship of different categories is proposed in this paper. The metric has two components. The first component is defined as Czekanowski metric. It defines a direct similarity of categorical distributions as a sum of intersection of distributions’ membership degrees of two objects. After the intersection the residuals are accounted for in the second component of the metric. The second metric’s component is defined as element-wise product of two matrices: matrix of residuals composition from membership degrees of two categorical distributions and matrix of categories’ paired kinship. It is assumed that kinship indices for each pair of categories are known. As a result, with a large number of categories the overall noisy contribution from weakly kinship categories is prominent. Therefore, it is proposed to filter the noise and account only for contribution from strongly kinship categories.