Определение центроидов для повышения точности порядково-инвариантной паттерн-кластеризации

Автор(ы): Мячин А.Л.

Выпуск: 78

Рубрика: Системный анализ

Год: 2019

Библиография: Мячин А.Л. Определение центроидов для повышения точности порядково-инвариантной паттерн-кластеризации // Управление большими системами. Выпуск 78. М.: ИПУ РАН, 2019. С.6-22. URL: https://doi.org/10.25728/ubs.2019.78.1

Дата опубликования: 31.03.2019

Ключевые слова: паттерн, анализ паттернов, кластерный анализ

Аннотация: Работа продолжает исследования, направленные на создание методов анализа паттернов в системе параллельных координат с независимыми от последовательности входных данных результатов. Описаны основные операции над объектами порядково-инвариантных паттерн-кластеров. Доказано утверждение о принадлежности центроида порядково-инвариантного паттерн-кластера исходному кластеру, что позволяет проводить оценку внутрикластерных расстояний «объект – центроид» в многомерном пространстве признаков. Приведены примеры выявления структурной схожести объектов в системе параллельных координат. Отмечены основные отличия методов анализа паттернов и кластерного анализа. Описана методология выявления центроида порядково-инвариантного паттерн-кластера. Предложен алгоритм объединения групп объектов на базе их структурной схожести – с одной стороны, и минимизации внутрикластерных расстояний – с другой, что позволяет повысить точность конечных результатов и частично решить проблему поиска качественно близких объектов при наличии погрешности в исходных данных. Предложенный алгоритм использует понятие внутрикластерных расстояний «объект – центроид» и удовлетворяет следующим условиям: эндогенное определение как количества, так и состава искомых групп изучаемых объектов; невысокая (относительно) вычислительная сложность; независимость исходного разбиения от изначальной последовательности входных данных. Продемонстрирована работа предложенного алгоритма на классических наборах данных. Приведены результаты тестирования и отмечено повышение точности кластеризации.

Author(s): Myachin A.

Article title: Determination of centroids to increase the accuracy of ordinal-invariant pattern clustering

Issue: 78

Year: 2019

Keywords: pattern, pattern analysis, cluster analysis

Abstract: The work continues the research of constructing methods for analyzing patterns in parallel coordinates independent of the sequence of input data of the results. The basic operations on objects of ordinal-invariant pattern clusters are described. The assertion that the centroid of an ordinal-invariant pattern cluster belongs to the original cluster is proved, which allows one to estimate the intracluster object - centroid distances in the multidimensional feature space. Examples of revealing the structural similarity of objects in parallel coordinates are given. The main differences between the methods of analysis of patterns and cluster analysis are noted. The methodology of the centroid detection of the ordinal-invariant pattern-cluster is described. An algorithm for combining groups of objects based on their structural similarity, on the one hand, and minimizing intracluster distances, on the other, is proposed, which makes it possible to improve the accuracy of the final results and partially solve the problem of finding similar objects in the presence of error in the original data. The proposed algorithm uses the concept of intracluster distances “object - centroid” and satisfies the following conditions: endogenous determination of the number and composition of the desired groups of objects under study; low (relatively) computational complexity; independence of the original partition from the initial sequence of input data. The work of the proposed algorithm on classical data sets is demonstrated. The results of testing are presented and the clustering accuracy is increased.