Участник:Артем Карпухин/Алгоритм CLOPE кластеризации категориальных данных: различия между версиями
| Строка 15: | Строка 15: | ||
Алгоритм '''CLOPE (Clustering with sLOPE)''' - неиерархический итеративный метод кластерного анализа, предназначенный для обработки больших наборов категориальных данных. Алгоритм был предложен группой исследователей из Шанхайского университета (Yiling Yang, Xudong Guan, Jinyuan You) в статье "''CLOPE: A Fast and Effective Clustering Algorithm for Transactional Data''" <ref> Y.Yang, X.Guan J.You. CLOPE: A Fast and Effective Clustering Algorithm for Transactional Data</ref> на конференции [http://www.kdd.org SIGKDD (Special Interest Group on Knowledge Discovery and Data Mining)] в 2002 году. | Алгоритм '''CLOPE (Clustering with sLOPE)''' - неиерархический итеративный метод кластерного анализа, предназначенный для обработки больших наборов категориальных данных. Алгоритм был предложен группой исследователей из Шанхайского университета (Yiling Yang, Xudong Guan, Jinyuan You) в статье "''CLOPE: A Fast and Effective Clustering Algorithm for Transactional Data''" <ref> Y.Yang, X.Guan J.You. CLOPE: A Fast and Effective Clustering Algorithm for Transactional Data</ref> на конференции [http://www.kdd.org SIGKDD (Special Interest Group on Knowledge Discovery and Data Mining)] в 2002 году. | ||
| − | Основной идеей данного метода является использование глобального критерия оптимизации на основе максимизации | + | Алгоритм CLOPE в изначальной формулировке является алгоритмом кластеризации транзакционных данных (под транзакцией понимается некоторый произвольный набор объектов конечной длины). Основной идеей данного метода является использование глобального критерия оптимизации на основе максимизации функции стоимости применительно к задачам кластеризации. Во время выполнения алгоритма |
| − | |||
в оперативной памяти требуется хранить относительно малое количество информации о каждом кластере и производится минимальное число | в оперативной памяти требуется хранить относительно малое количество информации о каждом кластере и производится минимальное число | ||
| − | проходов по набору данных. При использовании метода CLOPE количество кластеров подбирается автоматически и зависит от коэффициента отталкивания - параметра, | + | проходов по набору данных. При использовании метода CLOPE количество кластеров подбирается автоматически и зависит от коэффициента отталкивания - параметра, определяющего уровень сходства транзакций внутри кластера. Коэффициент отталкивания задается пользователем: чем больше данный параметр, тем ниже уровень сходства транзакций и, как следствие, большее количество кластеров будет создано. |
https://basegroup.ru/community/articles/clope | https://basegroup.ru/community/articles/clope | ||
Версия 00:37, 16 октября 2016
| Алгоритм CLOPE | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]O(N*K*A)[/math] |
| Объём входных данных | [math]N*A[/math] |
| Объём выходных данных | [math]2N[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]O( \log (N*K*A))[/math] |
| Ширина ярусно-параллельной формы | [math]O(N*K*A)[/math] |
Основные авторы описания: А.В.Карпухин, А.А.Желтков
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Алгоритм CLOPE (Clustering with sLOPE) - неиерархический итеративный метод кластерного анализа, предназначенный для обработки больших наборов категориальных данных. Алгоритм был предложен группой исследователей из Шанхайского университета (Yiling Yang, Xudong Guan, Jinyuan You) в статье "CLOPE: A Fast and Effective Clustering Algorithm for Transactional Data" [1] на конференции SIGKDD (Special Interest Group on Knowledge Discovery and Data Mining) в 2002 году.
Алгоритм CLOPE в изначальной формулировке является алгоритмом кластеризации транзакционных данных (под транзакцией понимается некоторый произвольный набор объектов конечной длины). Основной идеей данного метода является использование глобального критерия оптимизации на основе максимизации функции стоимости применительно к задачам кластеризации. Во время выполнения алгоритма в оперативной памяти требуется хранить относительно малое количество информации о каждом кластере и производится минимальное число проходов по набору данных. При использовании метода CLOPE количество кластеров подбирается автоматически и зависит от коэффициента отталкивания - параметра, определяющего уровень сходства транзакций внутри кластера. Коэффициент отталкивания задается пользователем: чем больше данный параметр, тем ниже уровень сходства транзакций и, как следствие, большее количество кластеров будет создано.
https://basegroup.ru/community/articles/clope http://www.fundamental-research.ru/ru/article/view?id=33381 http://www.olap.ru/home.asp?artId=155
Задачи кластеризации больших массивов категорийных данных весьма актуальна для систем анализа данных.
- ↑ Y.Yang, X.Guan J.You. CLOPE: A Fast and Effective Clustering Algorithm for Transactional Data
