| Эта статья требует внимания специалиста по статистике. Пожалуйста, добавьте причина или разговаривать в этот шаблон, чтобы объяснить проблему со статьей. Статистика WikiProject может помочь нанять эксперта. (Февраль 2010 г.) |
SUBCLU это алгоритм для кластеризация многомерных данных Карин Кайлинг, Ханс-Петер Кригель и Пер Крёгер.[1] Это кластеризация подпространств алгоритм, основанный на алгоритме кластеризации на основе плотности DBSCAN. SUBCLU может найти кластеры в параллельно оси подпространств и использует вверх дном, жадный стратегия оставаться эффективной.
Подход
SUBCLU использует монотонность критерии: если кластер найден в подпространстве
, то каждое подпространство
также содержит кластер. Однако кластер
в подпространстве
не обязательно кластер в
, поскольку кластеры должны быть максимальными, и в кластере может содержаться больше объектов.
который содержит
. Однако плотно связанный набор в подпространстве
также является плотносвязным множеством в
.
Этот свойство закрытия вниз используется SUBCLU аналогично Алгоритм априори: сначала все одномерные подпространства сгруппированы. Все кластеры в подпространстве более высокого измерения будут подмножествами кластеров, обнаруженных в этой первой кластеризации. SUBCLU, следовательно, рекурсивно производит
-мерные подпространства кандидатов путем объединения
-мерные подпространства с разделением кластеров
атрибуты. После удаления нерелевантных кандидатов DBSCAN применяется к подпространству-кандидату, чтобы узнать, содержит ли оно еще кластеры. Если это так, то подпространство-кандидат используется для следующей комбинации подпространств. Чтобы улучшить время работы DBSCAN, только точки, о которых известно, что они принадлежат кластерам в одном
-мерное подпространство (выбранное таким образом, чтобы кластеров было как можно меньше). Из-за свойства закрытия вниз другая точка не может быть частью
-мерный кластер в любом случае.
Псевдокод
SUBCLU принимает два параметра,
и
, которые выполняют ту же роль, что и в DBSCAN. На первом этапе DBSCAN используется для поиска одномерных кластеров в каждом подпространстве, охватываемом одним атрибутом:
![{ displaystyle { mathtt {SUBCLU}} (БД, eps, MinPts)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05f00ccd20af3a2928255817d068299c85939de6)
![{ Displaystyle S_ {1}: = emptyset}](https://wikimedia.org/api/rest_v1/media/math/render/svg/21d093234cba6eefc957e4f898e43afb7c3e7614)
![{ Displaystyle C_ {1}: = emptyset}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d6a2e269d0b15c34e05f3d72a37298adfa920b7)
![{ displaystyle { mathtt {for , each}} , a in Attributes}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c4f8f2dadbde739c1c24b3d9a87ce55b361d8fd)
![{ Displaystyle C ^ { {a }} = { mathtt {DBSCAN}} (DB, {a }, eps, MinPts) ! ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/78898269f36499b56bca87394a783cd6bf71bf12)
![{ Displaystyle { mathtt {если}} (С ^ { {а }} neq emptyset)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c50b014cb67b2d141ae4d095b5375860674a810)
![{ Displaystyle S_ {1}: = S_ {1} чашка {а }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/473f9e88d5a0075826a2e37fafc568a412643304)
![{ Displaystyle C_ {1}: = C_ {1} чашка C ^ { {а }}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/56ac7e28f101188b4265f50ec613cf7d7b1cb084)
![{ Displaystyle { mathtt {конец , если}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75cf46574a2d24f8b53d10a2ba7c077dd5339700)
![{ Displaystyle { mathtt {конец , для}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97699bc50a8bc5c94015c328b1a652ca165d6c43)
- // На втором этапе
-мерные кластеры строятся из
-мерные:
![{ Displaystyle к: = 1 ! ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de13fe9e464bde96c9e1ef98991a5cd25a53e817)
![{ displaystyle { mathtt {while}} (C_ {k} neq emptyset)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65a5bb202f0caaa988a4c8a903f9cf0fe4375b90)
![{ displaystyle { mathtt {CandS}} _ {k + 1}: = { mathtt {GenerateCandidateSubspaces}} (S_ {k}) ! ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/33c28126f21aa05fe8241323235f6ad1a3937146)
![{ displaystyle { mathtt {for , each}} , cand in { mathtt {CandS}} _ {k + 1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5cdb4b6c0df464dd022ac2b760ce7c92686bab60)
![{ displaystyle { mathtt {bestSubspace: =}} min _ {s in S_ {k} wedge s subset cand} sum _ {C_ {i} in C ^ {s}} | C_ {i } |}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b2220d7a8292c4e5cc5bd99f6b885b88eb6151ec)
![{ displaystyle C ^ {cand}: = emptyset}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11449a0b16dd9193d4fe51a210cd2e0628f62eb7)
![{ displaystyle { mathtt {для , each , cluster}} , cl in C ^ { mathtt {bestSubspace}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b373d0e094f0c4dd745dbeb86b8a354642d1ecd4)
![{ displaystyle C ^ {cand}: = C ^ {cand} cup { mathtt {DBSCAN}} (cl, cand, eps, MinPts)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b9cdc214ae711d59c84dc4f7183afe74601db68b)
![{ displaystyle { mathtt {if}} , (C ^ {cand} neq emptyset)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/82417f42537dcf988c3112c00dc0e6a99bdd4517)
![{ Displaystyle S_ {k + 1}: = S_ {k + 1} чашка свечи}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4f91e91bdae42d19ccafe80f36267fda7719fecf)
![{ Displaystyle C_ {k + 1}: = C_ {k + 1} чашка C ^ {Cand}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e4042b07a3201f1425f6b3ab0f49b3ef5c11407)
![{ Displaystyle { mathtt {конец , если}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75cf46574a2d24f8b53d10a2ba7c077dd5339700)
![{ Displaystyle { mathtt {конец , для}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97699bc50a8bc5c94015c328b1a652ca165d6c43)
![{ Displaystyle { mathtt {конец , для}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97699bc50a8bc5c94015c328b1a652ca165d6c43)
![{ Displaystyle к: = к + 1 ! ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2d084f813bfb25d9ce438e5476a29fa7f12164a)
![{ Displaystyle { mathtt {конец , а}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/891295248e1ea8b177e38901f83159ee4fe0d795)
![{ Displaystyle { mathtt {конец}} ! ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65736c829c370b59e43ee6b47811897c217586d8)
Набор
содержит все
-мерные подпространства, о которых известно, что они содержат кластеры. Набор
содержит наборы кластеров, найденных в подпространствах. В
выбирается для минимизации запусков DBSCAN (и количества точек, которые необходимо учитывать при каждом запуске) для поиска кластеров в подпространствах-кандидатах.
Подпространства-кандидаты генерируются очень похоже на Алгоритм априори генерирует частые кандидаты в наборы элементов: пары
-мерные подпространства сравниваются, и если они отличаются только одним атрибутом, они образуют
-мерный кандидат. Однако обнаруживается и ряд нерелевантных кандидатов; они содержат
-мерное подпространство, не содержащее кластера. Следовательно, эти кандидаты удаляются на втором этапе:
![{ displaystyle { mathtt {GenerateCandidateSubspaces}} (S_ {k})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/850576b3fd86665e9b79b5cdd59931f45e83dfa1)
![{ displaystyle { mathtt {CandS}} _ {k + 1}: = emptyset}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c0c91809a30d0746d52882ecaa0a2fd9aecb530)
![{ displaystyle { mathtt {для , each}} , s_ {1} in S_ {k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f733b15e64f66e179a6e6ba857ae2ebb4c8ebeb5)
![{ displaystyle { mathtt {для , each}} , s_ {2} in S_ {k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9a42fe381849909a45ee327d51deef352779b7b)
![{ displaystyle { mathtt {if}} , (s_ {1} , { mathtt {and}} , s_ {2} , , { mathtt {Different , , in , , точно , , один , , атрибут}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dba350f397f2a8930ee93517053d2763da152aa9)
![{ displaystyle { mathtt {CandS}} _ {k + 1}: = { mathtt {CandS}} _ {k + 1} cup {s_ {1} cup s_ {2} }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd2dc79ba0567c4121e721f61f62800a4999a167)
![{ Displaystyle { mathtt {конец , если}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75cf46574a2d24f8b53d10a2ba7c077dd5339700)
![{ Displaystyle { mathtt {конец , для}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97699bc50a8bc5c94015c328b1a652ca165d6c43)
![{ Displaystyle { mathtt {конец , для}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97699bc50a8bc5c94015c328b1a652ca165d6c43)
- // Обрезка нерелевантных подпространств-кандидатов
![{ displaystyle { mathtt {for , each}} , cand in { mathtt {CandS}} _ {k + 1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5cdb4b6c0df464dd022ac2b760ce7c92686bab60)
![{ displaystyle { mathtt {для , each}} , k { texttt {-element}} , s subset cand}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f43b520f7ce2c37886c2b1557475066429448a32)
![{ displaystyle { mathtt {if}} , (s not in S_ {k})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9b8a32aacbfdbe0909db358432c0fd831670b82)
![{ displaystyle { mathtt {CandS}} _ {k + 1} = { mathtt {CandS}} _ {k + 1} setminus {cand }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/936b7e7db25334a4e994868a938bfd3957d09fab)
![{ Displaystyle { mathtt {конец , если}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75cf46574a2d24f8b53d10a2ba7c077dd5339700)
![{ Displaystyle { mathtt {конец , для}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97699bc50a8bc5c94015c328b1a652ca165d6c43)
![{ Displaystyle { mathtt {конец , для}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97699bc50a8bc5c94015c328b1a652ca165d6c43)
![{ Displaystyle { mathtt {конец}} , !}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25c18f70d2be426ee552208146059724988f9e8b)
Доступность
Пример реализации SUBCLU доступен в Фреймворк ELKI.
Рекомендации