Робастная модификация метода k-средних для кла- стеризации интервальных данных - Известия Санкт-Петербургской лесотехнической академии
  • Автор:

    Уткин, Л.В.,

    Utkin, L.V.

    Жук, Ю.А.,

    Zhuk, Y.A.

  • DOI: https://doi.org/10.21266/2079-4304.2016.216.255-266
  • Дата публикации: 19.09.2016
  • Дата регистрации: 2016-09-01 16:19:49
  • Альтернативный идентификатор: 2079-4304
  • Номер журнала: 216-216

Ключевые слова

кластеризация, машинное обучение, метод K-средних, интервал, робастность, clustering, machine learning, K-means method, interval, robustness

Известия Санкт-Петербургской лесотехнической академии

Робастная модификация метода k-средних для кла- стеризации интервальных данных
(A robust modification of the K-means method for clustering under interval-valued data)

Аннотация:

Предложена робастная модификация метода K-средних для решения задачи кластеризации при условии, что элементы обучающей выборки являются интер- вальными. Существующие методы кластеризации в большинстве либо основаны на замене интервальных данных их точными аналогами, например, центрами ин- тервалов, либо используют специальные метрики расстояния между гиперпря- моугольниками (многомерными интервалами) или между точкой и гиперпрямо- угольником, например расстояние Хаусдорфа. В отличие от существующих мето- дов, идеей, лежащей в основе предлагаемого алгоритма, является трансформация интервального характера неопределенности во множество распределений весов примеров и расширение обучающей выборки. При этом новые элементы обучаю- щей выборки, являющиеся точками исходных интервалов, имеют неопределен- ные веса, назначенные таким образом, чтобы не нарушить исходную структуру обучающей выборки, не внося никакой дополнительной необоснованной ин- формации. Другой идеей является использование минимаксной стратегии для обеспечения робастности. Показано, что новый алгоритм отличается от стан- дартного алгоритма K-средних этапом решения простой задачи линейного про- граммирования. Также показано, что в простейшем случае, когда элементы ис- ходной обучающей выборки имеют одинаковые веса, предлагаемый алгоритм сводится к тому, что выбираются точки гиперпрямоугольников, находящиеся от текущего центра тяжести на максимальном расстоянии. Полученные результаты можно рассматривать в рамках теории Демпстера–Шейфера. Предлагаемый ал- горитм целесообразно применять в случае больших интервалов данных или при малом объеме обучающей выборки.


A robust modification of the K-means method for solving a clustering problem under interval-valued training data is proposed. The existing methods of clustering are mainly based on the replacement of interval-valued data with their point-valued representations, for example, with centers of intervals, or they use some special distance metrics between hyper-rectangles (multi-dimensional intervals) or between points and hyper-rectangles, for example, the Hausdorff distance. In contrast to the existing methods, the first idea underlying the proposed algorithm is transferring of interval uncertainty to sets of example weights and to an extension of the training set. At that, new elements of the training set, being points approximating intervals, have imprecise weights assigned such that they do not change an initial structure of training data and do not introduce additional unjustified information. The second idea is to use the minimax strategy for providing the robustness. It is shown in the paper that the new algorithm differs from the standard K-means algorithm by a step of solving a simple linear programming problem. It is also shown in the paper that in the simplest case when all elements of the training set have identical weights, the proposed algorithm is reduced to the choice of a point inside hyper-rectangles, which are located on the largest distance from the center of a cluster. The obtained results can be considered also in the framework of Dempster–Shafer theory. The proposed algorithm is useful when the intervals of data are rather large and when the training set is small.