ساب كلو

SUBCLU هي خوارزمية لتجميع البيانات عالية الأبعاد، من تطوير كارين كايلينغ، وهانز بيتر كريغل ، وبير كروغر. ^{[ 1 ]} وهي خوارزمية تجميع في الفضاءات الفرعية ، مبنية على خوارزمية التجميع القائمة على الكثافة DBSCAN . تستطيع SUBCLU إيجاد المجموعات في الفضاءات الفرعية المتوازية مع المحاور ، وتستخدم استراتيجية جشعة من الأسفل إلى الأعلى للحفاظ على كفاءتها.

يستخدم SUBCLU معيار الرتابة : إذا تم العثور على مجموعة في فضاء فرعي${\displaystyle S}$ثم كل فضاء جزئي${\displaystyle T\subseteq S}$يحتوي أيضًا على مجموعة. ومع ذلك، فإن المجموعة${\displaystyle C\subseteq DB}$في الفضاء الفرعي${\displaystyle S}$ليس بالضرورة أن يكون تجمعًا في${\displaystyle T\subseteq S}$بما أن المجموعات يجب أن تكون قصوى، وقد تحتوي المجموعة على المزيد من العناصر في${\displaystyle T}$الذي يحتوي${\displaystyle C}$ومع ذلك، فإن المجموعة المتصلة بالكثافة في فضاء فرعي${\displaystyle S}$وهي أيضًا مجموعة متصلة بالكثافة في${\displaystyle T\subseteq S}$.

تستغل خوارزمية SUBCLU خاصية الإغلاق التنازلي هذه بطريقة مشابهة لخوارزمية Apriori : أولًا، يتم تجميع جميع الفضاءات الفرعية أحادية البعد. ستكون جميع المجموعات في فضاء فرعي ذي أبعاد أعلى مجموعات فرعية من المجموعات التي تم اكتشافها في هذا التجميع الأولي. وبالتالي، تنتج خوارزمية SUBCLU بشكل متكرر${\displaystyle k+1}$الفضاءات الفرعية المرشحة ذات الأبعاد n عن طريق الجمع${\displaystyle k}$فضاءات فرعية ذات أبعاد n مع مجموعات مشتركة${\displaystyle k-1}$بعد استبعاد المرشحين غير ذوي الصلة، تُطبَّق خوارزمية DBSCAN على فضاء المرشحين الفرعي لمعرفة ما إذا كان لا يزال يحتوي على مجموعات. إذا كان الأمر كذلك، يُستخدم فضاء المرشحين الفرعي للتركيبة التالية من الفضاءات الفرعية. ولتحسين وقت تشغيل خوارزمية DBSCAN ، تُستخدم فقط النقاط المعروفة بانتمائها إلى مجموعات في فضاء فرعي واحد.${\displaystyle k}$يتم النظر في الفضاء الجزئي ذي الأبعاد n (الذي يتم اختياره ليحتوي على أقل عدد ممكن من المجموعات). وبسبب خاصية الإغلاق التنازلي، لا يمكن أن تكون أي نقطة أخرى جزءًا من${\displaystyle k+1}$على أي حال، مجموعة ذات أبعاد متعددة.

تأخذ الدالة SUBCLU معلَمَين،${\displaystyle \epsilon \!\,}$و${\displaystyle MinPts}$والتي تؤدي نفس الدور كما في خوارزمية DBSCAN . في الخطوة الأولى، تُستخدم خوارزمية DBSCAN للعثور على مجموعات أحادية البعد في كل فضاء فرعي يمتد بواسطة سمة واحدة:

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

${\displaystyle S_{1}:=\emptyset }$

${\displaystyle C_{1}:=\emptyset }$

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

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

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

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

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

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

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

// في خطوة ثانية،${\displaystyle k+1}$تتكون المجموعات ذات الأبعاد من${\displaystyle k}$-الأبعاد:

${\displaystyle k:=1\!\,}$

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

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

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

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

${\displaystyle C^{cand}:=\emptyset }$

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

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

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

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

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

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

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

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

${\displaystyle k:=k+1\!\,}$

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

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

المجموعة${\displaystyle S_{k}}$يحتوي على كل${\displaystyle k}$الفضاءات الفرعية ذات الأبعاد n التي من المعروف أنها تحتوي على تجمعات. المجموعة${\displaystyle C_{k}}$تحتوي على مجموعات التجمعات الموجودة في الفضاءات الفرعية.${\displaystyle bestSubspace}$يتم اختيارها لتقليل عدد مرات تشغيل DBSCAN (وعدد النقاط التي يجب مراعاتها في كل تشغيل) للعثور على المجموعات في الفضاءات الفرعية المرشحة.

يتم توليد الفضاءات الفرعية المرشحة بطريقة مشابهة لتوليد خوارزمية Apriori لمجموعات العناصر المتكررة المرشحة: أزواج من${\displaystyle k}$تتم مقارنة الفضاءات الفرعية ذات الأبعاد n، وإذا اختلفت في سمة واحدة فقط، فإنها تشكل فضاءً فرعيًا.${\displaystyle k+1}$مرشح ذو أبعاد. ومع ذلك، تم العثور على عدد من المرشحين غير ذوي الصلة أيضًا؛ فهم يحتويون على${\displaystyle k}$فضاء فرعي ذو أبعاد n لا يحتوي على مجموعة. لذا، يتم استبعاد هذه المرشحين في خطوة ثانية:

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

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

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

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

${\displaystyle {\mathtt {if}}\,(s_{1}\,{\mathtt {and}}\,s_{2}\,\,{\mathtt {differ\,\,in\,\,exactly\,\,one\,\,attribute}})}$

${\displaystyle {\mathtt {CandS}}_{k+1}:={\mathtt {CandS}}_{k+1}\cup \{s_{1}\cup s_{2}\}}$

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

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

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

// تقليم المساحات الفرعية المرشحة غير ذات الصلة

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

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

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

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

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

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

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

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

يتوفر مثال لتطبيق SUBCLU في إطار عمل ELKI .