СУБКЛУ

SUBCLU — это алгоритм кластеризации многомерных данных, разработанный Карин Кайлинг, Хансом-Петером Кригелем и Пером Крёгером. ^[1] Это алгоритм кластеризации подпространства , основанный на алгоритме кластеризации на основе плотности DBSCAN . SUBCLU может находить кластеры в подпространствах , параллельных осям , и использует стратегию «снизу вверх» , жадную чтобы оставаться эффективным.

Подход

SUBCLU использует критерии монотонности : если кластер найден в подпространстве $S$ , то каждое подпространство $T\subseteq S$ также содержит кластер. Однако кластер $C\subseteq DB$ в подпространстве $S$ не обязательно является кластером в $T\subseteq S$ , поскольку кластеры должны быть максимальными, и в кластере может содержаться больше объектов в $T$ который содержит $C$ . Однако связное по плотности множество в подпространстве $S$ также является связным по плотности множеством в $T\subseteq S$ .

Это свойство закрытия вниз используется SUBCLU аналогично алгоритму Априори : сначала все одномерные подпространства кластеризуются. Все кластеры в подпространстве более высокой размерности будут подмножествами кластеров, обнаруженных в ходе этой первой кластеризации. Таким образом, SUBCLU рекурсивно производит $k+1$ -мерные подпространства-кандидаты путем объединения $k$ -мерные подпространства с общими кластерами $k-1$ атрибуты. После отсечения ненужных кандидатов к подпространству кандидатов применяется DBSCAN , чтобы выяснить, содержит ли оно еще кластеры. Если да, то подпространство-кандидат используется для следующей комбинации подпространств. Чтобы улучшить время выполнения DBSCAN , только те точки, которые, как известно, принадлежат кластерам в одном $k$ Рассматривается -мерное подпространство (которое выбирается так, чтобы оно содержало как можно меньше кластеров). Из-за свойства замыкания вниз другая точка не может быть частью $k+1$ в любом случае -мерный кластер.

Псевдокод

SUBCLU принимает два параметра: $\epsilon \!\,$ и $MinPts$ , которые выполняют ту же роль, что и DBSCAN . На первом этапе DBSCAN используется для поиска 1D-кластеров в каждом подпространстве, охватываемом одним атрибутом:

${\mathtt {SUBCLU}}(DB,eps,MinPts)$

S_{1}:=\emptyset

C_{1}:=\emptyset

{\mathtt {for\,each}}\,a\in Attributes

C^{\{a\}}={\mathtt {DBSCAN}}(DB,\{a\},eps,MinPts)\!\,

{\mathtt {if}}(C^{\{a\}}\neq \emptyset )

S_{1}:=S_{1}\cup \{a\}

C_{1}:=C_{1}\cup C^{\{a\}}

{\mathtt {end\,if}}

{\mathtt {end\,for}}

// На втором этапе

k+1

-мерные кластеры строятся из

k

-мерные:

k:=1\!\,

{\mathtt {while}}(C_{k}\neq \emptyset )

{\mathtt {CandS}}_{k+1}:={\mathtt {GenerateCandidateSubspaces}}(S_{k})\!\,

{\mathtt {for\,each}}\,cand\in {\mathtt {CandS}}_{k+1}

{\mathtt {bestSubspace:=}}\min _{s\in S_{k}\wedge s\subset cand}\sum _{C_{i}\in C^{s}}|C_{i}|

C^{cand}:=\emptyset

{\mathtt {for\,each\,cluster}}\,cl\in C^{\mathtt {bestSubspace}}

C^{cand}:=C^{cand}\cup {\mathtt {DBSCAN}}(cl,cand,eps,MinPts)

{\mathtt {if}}\,(C^{cand}\neq \emptyset )

S_{k+1}:=S_{k+1}\cup cand

C_{k+1}:=C_{k+1}\cup C^{cand}

{\mathtt {end\,if}}

{\mathtt {end\,for}}

{\mathtt {end\,for}}

k:=k+1\!\,

{\mathtt {end\,while}}

${\mathtt {end}}\!\,$

Набор $S_{k}$ содержит все $k$ -мерные подпространства, которые, как известно, содержат кластеры. Набор $C_{k}$ содержит наборы кластеров, найденных в подпространствах. $bestSubspace$ выбирается для минимизации прогонов DBSCAN (и количества точек, которые необходимо учитывать в каждом прогоне) для поиска кластеров в подпространствах-кандидатах.

Подпространства-кандидаты генерируются так же, как алгоритм Apriori генерирует частые кандидаты в наборы элементов: пары $k$ -мерные подпространства сравниваются, и если они отличаются только по одному признаку, они образуют $k+1$ -мерный кандидат. Однако обнаруживается и ряд неподходящих кандидатов; они содержат $k$ -мерное подпространство, не содержащее кластера. Следовательно, эти кандидаты удаляются на втором этапе: