УДК 515.12; 519.237
СЛЕДСТВИЕ ИЗ ТЕОРЕМЫ ОБ ОДНОМЕРНОМ РАНЖИРОВАНИИ
(КЛАСТЕРИАЦИЯ ПО ГАМИЛЬТОНОВЫМ ПУТЯМ)
Шушкова Юлия Bикторовна,
., *****@***ru
Пермский Государственный университет,
кафедра прикладной математики и информатики
Россия,
Описано следствие из теоремы о существовании соответcтвия односвязных непересекающихся областей интервалам одномерного параметра, с сохранением непрерывности отображения (с трансформацией метрики), интерпретируемой как сведение процедуры кластеризации (в том случае если получаемые кластеры односвязны и выпуклы) к процедуре ранжирования по некоторому одномерному параметру; рассмотрен предельный случай, когда каждой односвязной области соответствует одно наблюдение, алгоритм кластеризации в этом случае строится как поиск кратчайшего гамильтонова пути в графе, соединяющем все наблюдения (вершины графа), и удаления рёбер максимальной длины из этого пути.
Ключевые слова: теорема о ранжировании, гамильтонов путь в графе, кластеризация
© , , 2010 г.
Ранее [2] доказаны следующие две теоремы.
Теорема 1 (Об обходе областей). При условии выпуклости и односвязности областей многомерного пространства (многомерной карты), а также конечности их количества, существует, при возможном дополнении карты областями (до гамильтоновости максимальной цепи графа, соответствующего карте), обход (быть может неединственный) этих областей, задаваемый одномерным параметром (зависящим от всех координат пространства). □
Эта теорема имеет интерпретацию, относящуюся к процедуре кластеризации наблюдений.
Теорема 2 (О сведении кластеризации к одномерному ранжированию). При условии выпуклости и односвязности кластеров, а также конечности их количества, процедура кластеризации заменяема на процедуру ранжирования по одномерному параметру (зависящему от всех координат пространства). □
Рассмотрим предельный случай, пусть имеется метрическое пространство L, в нём имеется набор наблюдений X, тогда в предельном случае каждой односвязной области (теоремы 1) соответствует одно наблюдение. Тогда по теореме 1 существует обход этих областей, который по теореме 2, является процедурой ранжирования (эквивалентной процедуре кластеризации) по некоторому параметру.
Конкретизируется этот обход, например следующим образом. На точках наблюдений (их число n), как на вершинах графа, строится граф Kn, в котором каждая вершина соединена с каждой ребром, этот граф гамильтонов [1]. Каждому ребру соответствует его вес wij, равный расстоянию между вершинами xi и xj. В графе Kn ищется гамильтонов путь минимальной длины (минимального веса). Далее, когда путь Pmin найден, в нём удаляется (m–1) рёбер максимальной длины, где m — необходимое число кластеров. Оставшиеся после удаления этих рёбер m связных подграфов Pmin и есть искомые кластеры. Таким образом, имеется из теорем 1, 2 вытекает следующая теорема.
Теорема 3[1]. (О предельном случае). В предельном случае, когда односвязной области соответствует одно наблюдение, m кластерам соответствуют связные подграфы минимального гамильтонова пути Pmin графа Kn построенного на наблюдениях, после удаления из Pmin (m–1) ребёр максимальной длины. □
Вычислительное приложение этих утверждений,— это отдельная задача.
Таким образом, имеется достаточно простая процедура кластеризации в пространстве неограниченно большой размерности (поскольку размерность пространства, в котором имеются наблюдения, не являются ограничивающим условием теорем 1–3). Более того, такая процедура кластеризации независима от вращений пространства методом главных компонент, что позволяет оперировать координатами наблюдений без их перенормировки.
Библиографический список
1. Лекции по теории графов / , , М.: «Наука», гл. ред. физ.-мат. лит., 1990.— 384 с.
2. , Об одном случае сведения кластеризации к одномерному ранжированию // Университетские исследования (математика), 2009, http://www. uresearch. *****/files/articles/12_47294.doc
COROLLARY TO THEOREM ABOUT ONE-DIMENSIONAL RANKING
(CLUSTERING BY HAMILTONIAN WATERWAYS)
Shushkova Yu. V., Chechulin V. L., *****@***ru
Perm State University
Russia, st. them. Bukireva, 15
The consequence of a theorem about the existence of disjoint simply connected domains match to intervals of one-dimensional parameter was described, considered the limiting case where every simply connected region corresponds to one observation, clustering algorithm, in this case is constructed as finding the shortest Hamiltonian path in the graph, linking all the observations (top graph), and delete edges of maximum length of this path.
Keywords: theorem of ranking, Hamiltonian path in the graph, clustering.
© Shushkova Yu. V., Chechulin V. L., 2010
РЕКОМЕНДАЦИЯ СПЕЦИАЛИСТА
В статье описывается фундаментальный результат, следующий из положений теории графов к методам кластеризации. Предложенный метод кластеризации является оригинальным, и не зависит от размерности пространства наблюдений. Прикладные аспекты подлежат дальнейшей разработки в определённой предметной области. Статья может быть опубликована.
д. ф.-м. н., профессор
[1] Формулировка содержания теоремы 3 (метода кластеризации) была предложена Шушковой сдаче письменного зачёта по предмету «Теория активных систем» в декабре 2009 г.
