SUBCLU

SUBCLU är en algoritm för klustring av högdimensionell data av Karin Kailing, Hans-Peter Kriegel och Peer Kröger. Det är en subrymdklustringsalgoritm som bygger på den densitetsbaserade klustringsalgoritmen DBSCAN . SUBCLU kan hitta kluster i axelparallella delrum och använder en nedifrån och upp, girig strategi för att förbli effektiv.

Närma sig

SUBCLU använder ett monotoniskt kriterium: om ett kluster hittas i ett delområde $S$ , så innehåller varje delutrymme $T\subseteq S$ också ett kluster. Ett kluster $C\subseteq DB$ i delutrymmet $S$ är dock inte nödvändigtvis ett kluster i $T\subseteq S$ , eftersom kluster måste vara maximala, och fler objekt kan finnas i klustret i $T$ som innehåller $C$ . En densitetsansluten mängd i ett delrum $S$ är emellertid också en densitetsansluten mängd i $T\subseteq S$ .

Denna nedåtstängningsegenskap används av SUBCLU på ett sätt som liknar Apriori-algoritmen : för det första är alla 1-dimensionella delrum klustrade. Alla kluster i ett högredimensionellt delrum kommer att vara delmängder av klustren som detekteras i denna första klustring. SUBCLU producerar därför rekursivt $k+1$ -dimensionella kandidatunderrymder genom att kombinera $k$ -dimensionella underutrymmen med kluster som delar $k-1$ attribut. Efter beskärning av irrelevanta kandidater, DBSCAN på kandidatunderutrymmet för att ta reda på om det fortfarande innehåller kluster. Om den gör det, används kandidatunderutrymmet för nästa kombination av underutrymmen. För att förbättra körtiden för DBSCAN beaktas endast de punkter som är kända för att tillhöra kluster i ett ${\displaystyle k} -dimensionellt delrum (som är valt att innehålla så lite kluster som möjligt).$ På grund av egenskapen nedåtstängning kan inte andra punkter vara en del av ett $k+1$ -dimensionellt kluster ändå.

Pseudokod

SUBCLU tar två parametrar, $\epsilon \!\,$ och $MinPts$ , som har samma roll som i DBSCAN . I ett första steg används DBSCAN för att hitta 1D-kluster i varje delutrymme som sträcks av ett enda attribut:

${\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\}}$

${ \displaystyle {\mathtt {end\,if}}}$

${\mathtt {end\,for}}$

// I ett andra steg, $k+1$ -dimensionella kluster byggs av $k$ -dimensionella:

$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 {bästaSubspace:=}}\min _{s\in S_{k}\wedge s\subset cand}\summa _{C_{i}\in C^{s}}|C_{i }|$

$C^{cand}:=\emptyset$

${\displaystyle {\mathtt {for\,each\,cluster}}\,cl\in C^{\mathtt {bästaSubspace}}} C$

$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}}\!\,$

Uppsättningen $S_{k}$ innehåller alla $k$ -dimensionella delrum som är kända för att innehålla kluster Mängden $C_{k}$ innehåller uppsättningarna av kluster som finns i underrymden. Den $bestSubspace$ är vald för att minimera körningarna av DBSCAN (och antalet poäng som måste beaktas i varje körning) för att hitta klustren i kandidatunderrymden.

Kandidatunderrymden genereras ungefär likadant. Apriori-algoritmen genererar de frekventa objektuppsättningskandidaterna: Par av $k$ -dimensionella underrymden jämförs, och om de skiljer sig i endast ett attribut, bildar de en $k+ 1$ -dimensionell kandidat. Men ett antal irrelevanta kandidater hittas också; de innehåller ett $k$ -dimensionellt delrum som inte innehåller ett kluster. Därför tas dessa kandidater bort i ett andra steg:

${\mathtt {GenerateCandidateSubspaces}}(S_{k})$

${\mathtt {CandS}}_{k+1}:=\emptyset$

${\mathtt {for\,each}}\,s_{1}\in S_{k}$

${k}}$${\displaystyle {\mathtt {for\,each}}\,s_{2 }\in$

${ \mathtt {if}}\,(s_{1}\,{\mathtt {och}}\,s_{2}\,\,{\mathtt {skiller\,\,in\,\,exakt\,\ ,ett\,\,attribut}})$

${\displaystyle {\mathtt {CandS}}_{k +1}:={\mathtt {CandS}}_{k+1}\cup \{s_{1}\cup s_{2}\}} e n d i f {\displaystyle {$

$, if}}}$

${\mathtt {end\,for}}$

${\mathtt {end\,for}}$

// Beskärning av irrelevant kandidat delrymden

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

${\displaystyle {\mathtt {for\,each}}\,k{\texttt {-element}}\,s\subset cand$

${\mathtt {if}}\,(s\not \in S_{k})$

${\mathtt {CandS}}_{k+1}={\mathtt {CandS}}_{k+1}\setminus \{cand\}$

${ \displaystyle {\mathtt {end\,if}}}$

${\mathtt {end\,for}}$

${\mathtt {end\,for }}$

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

Tillgänglighet

Ett exempel på implementering av SUBCLU är tillgängligt i ELKI-ramverket .