Одни из старейших алгоритмов кластеризации данных. Относятся к методам кластерного анализа ([3], [10], [13]). Особенностью этих методов, является то, что они разбивают документы на кластеры путем разбиения их на иерархичные группы, т.е. получаемое множество кластеров имеет иерархичную структуру. Они называются еще методами иерархической агломеративной кластеризации. Принцип работы иерархических агломеративных процедур состоит в последовательном объединении групп элементов, сначала самых близких, а затем всё более отдалённых друг от друга [20].
Основная суть этих методов заключается в выполнении следующих шагов ([13]):
1. вычисление значений близости между документами и получении матрицы близости;
2. определение каждого документа в свой отдельный кластер;
3. сливание в один кластер наиболее близких пар документов;
4. обновление матрицы близости путем удаления колонок и строк для кластеров, которые были слиты с другими и дальнейшего пересчета матрицы;
5. переход на шаг 3 до тех пор, пока не сработает остановочный критерий.
Эти три метода отличаются между собой в 4-м шаге. И именно благодаря способам обновления матрицы близости разные алгоритмы имеют разную точность. Проверка точности алгоритмов была проведена на специальных тестовых наборах и показала, что алгоритм Single Link имеет наименьшую точность, а остальные два - примерно одинаковую, более высокую, чем у Single Link. Результаты тестирования алгоритмов можно посмотреть в [13].
Комментариев нет:
Отправить комментарий