Участник:Viktorrulev/Алгоритм устойчивой кластеризации с иcпользованием связей
| Файл:Symbol wait.svg | Эта работа ждет рассмотрения преподавателем Дата последней правки страницы: 16.10.2016 Авторы этой статьи считают, что задание выполнено. |
| Алгоритм устойчивой кластеризации с иcпользованием связей | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O(M^2 + M^2m_{nbr} + M^{2}logM) }[/math] |
| Объём входных данных | [math]\displaystyle{ M \times N }[/math] |
| Объём выходных данных | [math]\displaystyle{ M }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ O(MlogM) }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ O(M^2) }[/math] |
Автор описания: В.А. Рулев.
Свойства и структура алгоритма
Общее описание алгоритма
Кластеризация (кластерный анализ) — задача разбиения заданной выборки объектов на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались. Каждый объект из выборки характеризуется рядом признаков, которые могут быть вещественными, целочисленными, категорийными (то есть принимающими значения из какого-либо множества) и другими. Множество значений, которые может принимать признак, называется доменом этого признака. Так, например, у объекта кошка может быть категорийный признак порода, доменом которого является множество [персидская, бенгальская, сфинкс, мейн-кун, ...].
Алгоритм устойчивой кластеризации с иcпользованием связей (robust clustering using links, ROCK) был предложен в 2000 году Sudipto Guha (Stanford University), Rajeev Rastogi (Bell Laboratories) и Kyuseok Shim (Bell Laboratories) [1] для кластеризации объектов с категорийными признаками.
Алгоритм устойчивой кластеризации с использованием связей предназначен для работы с объектами типа "транзакция" ("покупательская корзина"). Транзакция представляет собой множество товаров, приобретенных покупателем у поставщика. Каждому товару, который есть в наличии у поставщика, в транзакции соответствует отдельный признак, который принимает значение true, если товар присутствует в транзакции, и false, если товар в транзакции отсутствует.
Математическое описание алгоритма
В ходе кластеризации [math]\displaystyle{ M }[/math] имеющихся транзакций [math]\displaystyle{ P=\{p_1,...,p_M\} }[/math] (каждая транзакция имеет [math]\displaystyle{ N }[/math] признаков) должны быть разделены на [math]\displaystyle{ K }[/math] непересекающихся подмножеств (кластеров) [math]\displaystyle{ C_1, ..., C_K }[/math] таким образом, чтобы полученные кластеры максимизировали некоторую критериальную функцию [math]\displaystyle{ E(C_1, ..., C_K) }[/math].
Будет называть две транзакции [math]\displaystyle{ p_1 }[/math] и [math]\displaystyle{ p_2 }[/math] соседями, если мера сходства этих транзакций больше некоторого заранее заданного порогового значения [math]\displaystyle{ \theta }[/math], то есть
[math]\displaystyle{ neighbour(p_1,p_2)=(sim(p_1,p_2)\gt \theta) }[/math]
В качестве меры сходства в алгоритме устойчивой кластеризации с использованием связей используется основанная на коэффициенте Жаккара мера сходства
[math]\displaystyle{ sim(p_1,p_2)=\frac{N(p_1 \cap p_2)}{N(p_1 \cup p_2)} }[/math]
Количеством связей между двумя транзакциями будем называть количество общих соседей этих транзакций, то есть
[math]\displaystyle{ link(p_1,p_2)=N \Big( \{ p \in P | sim(p_1,p) \lt \theta \} \cap \{ p \in P | sim(p_2,p) \lt \theta \} \Big) }[/math]
В качестве критериальной функции используется функция вида
[math]\displaystyle{ E(C_1,...,C_K)=\sum_{i=1}^{K}N(C_i) \ast \sum_{p_q,p_r \in C_i}\frac{link(p_q,p_r)}{N(C_i)^{1+2f(\theta)}} }[/math]
Здесь [math]\displaystyle{ N(C_i)^{1+2f(\theta)} }[/math] имеет смысл ожидаемого (среднего) количества связей внутри одного кластера. Функция [math]\displaystyle{ f(\theta) }[/math] имеет вид
[math]\displaystyle{ f(\theta)=\frac {1-\theta}{1+\theta} }[/math]
Для того, чтобы сформировать кластеры, удовлетворяющие поставленному условию, необходимо последовательно объединять среди имеющихся кластеров такие пары кластеров, для которых метрика
[math]\displaystyle{ goodness(C_i,C_j)=\frac {\sum_{p_r \in C_i, p_q \in C_j}{link(p_r,p_q)}} {(N(C_i) + N(C_j))^{1+2f(\theta)} - N(C_i)^{1+2f(\theta)} - N(C_j)^{1+2f(\theta)}} }[/math]
достигает максимального значения среди всех пар кластеров. На начальном этапе каждая транзакция считается отдельным кластером.
Вычислительное ядро алгоритма
Вычислительное ядро алгоритма можно разделить на два основных этапа:
- Вычисление количества связей между каждой парой транзакций ([math]\displaystyle{ \frac {M \times M} {2} }[/math] вычислений количества связей)
- Последовательные объединения пар наиболее подходящих кластеров ([math]\displaystyle{ M-K }[/math] поисков пар и объединений)
Подробнее оба этапа будут описаны ниже.
Макроструктура алгоритма
На макроуровне можно выделить следующие шаги алгоритма:
Шаг 1: вычисление соседних транзакций.
Шаг 2: вычисление количества связей между всеми транзакциями.
Шаг 3: построение для каждого кластера упорядоченного списка значений метрики goodness со всеми остальными кластерами
Шаг 4: построение общего упорядоченного списка значений метрики goodness
Шаг 5 (повторяется то тех пор, пока количество кластеров не достигнет желаемого)
Шаг 5.1: объединение двух кластеров с наилучшим goodness
Шаг 5.2: обновление списков кластеров
Схема реализации последовательного алгоритма
Схема реализации последовательного алгоритма выглядит следующим образом:
procedure compute_links(P)
begin
for each p[i], p[j] in P do
if sim(p[i], p[j]) > theta
is_neighbour[i, j] = true
else
is_neighbour[i, j] = false
links[i, j] = 0
for each p[i], p[j] in P do
for p[k] in P do
if is_neighbour[i, k] && is_neighbour[j, k]
links[i, j] = links[i, j] + 1
end
procedure cluster(P, k)
begin
links := compute_links(P)
for each p in P do
q[p] := build_local_list(links, p)
Q := build global_list(P, q)
while size(Q) > k do
begin
u := extract_max(Q)
v := extract_max(q[u])
w := merge(u, v)
delete(Q, v)
for each x in (q[u] or q[v]) do
begin
delete(q[x], u);
delete(q[x], v)
insert(q[x], w, goodness(x, w))
insert(q[w], x, goodness(x, w))
update(Q, x, q[x])
end
insert(Q, w, q[w])
deallocate(q[u])
deallocate(q[v])
end
end
Последовательная сложность алгоритма
Рассмотрим сложности шагов алгоритма из раздела 1.4.
Шаг 1: выполняется с помощью двух вложенных циклов и содержит [math]\displaystyle{ O(M^2) }[/math] операций
Шаг 2: задача сводится к умножению полученной на предыдущем шаге матрицы соседства на саму себя. Это действие быть выполнено с помощью наивного метода за [math]\displaystyle{ O(M^3) }[/math] операций. С помощью алгоритма Копперсмита — Винограда это можно сделать за [math]\displaystyle{ O(M^{2.37}) }[/math] операций.[2] В случае, если среднее количество соседей каждой транзакции значительно меньше общего количества транзакций, связи могут быть вычислены за [math]\displaystyle{ O(M^2m_{nbr}) }[/math], где [math]\displaystyle{ m_{nbr} }[/math] - среднее количество соседей транзакции.
Шаг 3: имеет сложность [math]\displaystyle{ O(M) }[/math].[3]
Шаг 4: имеет такую же вычислительную сложность, как и предыдущий шаг.
Шаг 5: вычислительная сложность каждой итерации цикла составляет [math]\displaystyle{ O(MlogM) }[/math], так как в худшем случае в ходе итерации выполняется [math]\displaystyle{ M }[/math] вставок элемента в упорядоченный список. Желаемое количество кластеров [math]\displaystyle{ K }[/math] мало по сравнению с [math]\displaystyle{ M }[/math], следовательно можно считать, что нужно выполнить [math]\displaystyle{ M }[/math] итераций цикла. Таким образом, общая вычислительная сложность цикла равна [math]\displaystyle{ O(M^{2}logM) }[/math].
Таким образом, общую последовательную сложность алгоритма можно оценить, как [math]\displaystyle{ O(M^2 + M^{2.37} + M^{2}logM) }[/math] или [math]\displaystyle{ O(M^2 + M^2m_{nbr} + M^{2}logM) }[/math].
Информационный граф
Информационный граф перемножения матриц с подробным описанием представлен в статье перемножение плотных матриц
Ниже представлен информационный граф наиболее интересного этапа алгоритма устойчивой кластеризации с использованием связей - тела цикла (полупрозрачным показана следующая итерация цикла).
Ресурс параллелизма алгоритма
Шаг 1: каждая итерация цикла может быть выполнена независимо от всех остальных. Таким образом, в этом случае ширина ЯПФ равна [math]\displaystyle{ O(M^2) }[/math], а высота - [math]\displaystyle{ O(1) }[/math].
Шаг 2: высота ЯПФ равна [math]\displaystyle{ O(M) }[/math], а ширина - [math]\displaystyle{ O(M^2) }[/math] (см. перемножение плотных матриц)
Шаг 3: имеет небольшую асимптотическую сложность, может быть выполнен последовательно.
Шаг 4: аналогично шагу 3.
Шаг 5: каждая итерация цикла может быть выполнена только после полного завершения предыдущей, а внутри каждой отдельной итерации все вставки могут быть выполнены независимо друг от друга. Следовательно ширина ЯПФ в этом случае равна [math]\displaystyle{ O(M) }[/math], а высота ЯПФ равна [math]\displaystyle{ O(MlogM) }[/math].
Таким образом, высота ЯПФ зависит от размерности задачи линейно, а ширина ЯПФ - квадратично.
Входные и выходные данные алгоритма
Входные данные: информация об [math]\displaystyle{ M }[/math] транзакциях, каждая их которых имеет [math]\displaystyle{ N }[/math] бинарных атрибутов.
Объём входных данных: [math]\displaystyle{ M \times N }[/math] бинарных переменных. В силу того, что обычно в большинстве случаев лишь небольшое количество атрибутов транзакции имеет значение "1", каждую транзакцию можно хранить в виде списка номеров атрибутов, значения которых равны "1".
Выходные данные: [math]\displaystyle{ K }[/math] кластеров.
Объём выходных данных: [math]\displaystyle{ M }[/math] индексов транзакций, распределенных в [math]\displaystyle{ K }[/math] списков.
Свойства алгоритма
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как показано выше, является квадратичным.
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Алгоритм устойчивой кластеризации с иcпользованием связей реализован в пакете CBA языка R.
Литература
<references \>
- ↑ Sudipto Guha, Rajeev Rastogi, Kyuseok Shim ROCK: A robust clustering algorithm for categorical attributes. 2000. Information Systems. Vol 25, Issue 5, Pages 345-366
- ↑ Donald Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. In Proc. of the 19th Annual ACM Symposium on Theory of Computing. 1987.
- ↑ Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. The MIT Press, Massachusetts, 1990.