Similarity Metric оf Categorical Distributions for Topic Modeling Problems with Akin Categories

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 the others. Some practical problems have categories that are akin. 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 akin 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 remaining 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 memberships 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 weakly akin categories is prominent. Therefore, it is proposed to filter the noise and account only for contribution strongly akin categories.