Моделирование кластеризации многомерных объектов в Visual С++
9
вано кластер записан в вертикальном списке текущего элемента го-
ризонтального списка, а все элементы, входящие в сформированный
кластер, удалены из горизонтального списка.
Процедура повторяется для следующего элемента горизонталь-
ного списка, который еще не принадлежит ни одному из сформиро-
ванных ранее кластеров.
Оценка качества кластеризации.
Для полученной цепочки кла-
стеров вычисляются средние значения и оценки среднеквадратиче-
ского отклонения по каждому кластеру. Для полученного в результа-
те кластеризации числа кластеров и структуры проводится оценка
качества кластеризации: вычисляется среднеквадратический крите-
рий качества. В зависимости от полученного значения критерия про-
цесс кластеризации осуществляется для других значений параметра
кластеризации. Критерием окончания является выполнение условия:
норма разности значений функционала качества на соседних шагах
алгоритма должна быть меньше заданной точности.
Результаты моделирования.
В программном модуле для отоб-
ражения процесса решения задачи используются два основных диа-
логовых окна: отображения входной выборки и отображения резуль-
татов кластеризации. Сначала отображается окно вывода точек вы-
борки, каждая точка обозначается номером (или именем), при вводе
выборка перемешана.
После выполнения кластеризации осуществляется разбиение то-
чек по кластерам и вычисляется среднее для каждого кластера. Точки
разных кластеров закрашиваются разным цветом, каждая точка вы-
борки выводится с соответствующим ей номером кластера, точки од-
ного кластера объединяются в сеть, и отображается средняя точка
кластера.
Результаты кластеризации объектов на плоскости приведены на
рис. 2–6. Отображаются два окна: окно просмотра точек выборки и
окно точек после кластеризации.
Заключение.
Авторами разработан гибридный алгоритм класте-
ризации, не требующей априорной информации ни о числе класте-
ров, ни о форме выборки. Кластеризация осуществляется в два этапа.
На первом этапе для каждого элемента выборки определяется ло-
кальное сгущение, центром которого является сам элемент. В свою
очередь, локальное сгущение определяется как список ближайших
соседей. На втором этапе на основе методов определения связных
графа осуществляется кластеризация путем слияния отдельных сгу-
щений в кластеры.
Алгоритм обеспечивает кластеризацию в предположении слабого
пересечения кластеров: кластеров типа слабого сгущения, типа изоли-
рованного облака, среднего сгущения с центром, сильного кластера.
В случае пересекающихся кластеров алгоритм кластеризации позволяет
получить начальное приближение для разбиения другими методами.
