Метод WaveCluster

Сетевые алгоритмы

Алгоритм рассматривает всю совокупность данных как сигнал в N-мерном пространстве атрибутов и пытается на основании вейвлет-преобразования выделить в этом сигнале поддиапазоны частот, в которых связанные компоненты и будут кластерами.

Для применения алгоритма надо выбрать, какой именно фильтр будет применяться (какое именно из вейвлет-преобразований будет применяться).

0. Квантификация данных. Именно за это алгоритм называется сетевым. Каждое l-ное , измерение D-мерного пространства данных (то есть каждый атрибут) разделяется на m_l отрезков длиной s_l. Тогда в D-мерном пространстве существует N точек M_j = (μ₁,...,μ_l,...,μ_d), где μ - это некоторое количество отрезков длиной s_l. Тогда (если число m_l = m одинаково по всем осям, то N = m^D) .

И тогда объекту назначается в сооветствие M_j, когда для каждого l Фактически мы разбили все D-мерное пространство, в котором расположены наши объекты, на некую совокупность D-мерных прямоугольных призм (кубиков), характеризуемых наиболее дальней от начала координат точкой призмы M_j и каждому кубику назначили в соответствие все те объекты, которые попали внутрь него.

1. Применение вейвлет-преобразования. Теперь мы применяем дискретное вейвлет-преобразование к этим точкам M_j. Тогда на выходе мы получаем новую совокупность точек T_k в новом пространстве признаков. Оно в общем уже незначащее, но зато в нем точки группируются, они как бы стягиваются в области сильной связности. Это особенность вейвлет-преобразований - они увеличивают плотность кластера. Количество точек и количество кластеров в них зависит от конкретного вейвлет-преобразования и от количества его прогонов - чем оно более сложное и чем больше прогонов, тем меньше точек и кластеров.

2. Обнаружение кластеров в измененном пространстве признаков. В измененном пространстве признаков ищутся связанные компоненты </math>T_k</math>. Они являются кластерами. Более того, в общем случае многомерного пространства можно искать в подпространствах, которые также формируются вейвлет-преобразованием и в которых поиск гораздо легче в силу меньшей размерности этих пространств. В результате поиск сводится к поиску связанных компонент в двумерной картинке. В первом проходе находятся все связанные компоненты в картинке, и во втором - им назначают метки кластеров, отбрасывая уже отмеченные. Тогда мы получаем некоторое количество кластеров С и их меток c_f.

3. Создание таблицы соответствия. На этом этапе через соответствие исходных точек M_j и полученных в результате преобразования T_k создается таблица соответствия. Соотвествие этих точек для каждого из фильтров разное, но всегда прослеживается, несмотря на то, что преобразование не всегда обратимо. Простейшим соответствием явлются индексы. В результате мы получаем принадлежность M_j к определенному кластеру c_f.

4. А так как мы знаем, каким точкам соответствует M_j, мы получаем и соответствие этих кластеров конкретным точкам.