Участник:Smirnov.maxim/BIRCH: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показано 113 промежуточных версий 4 участников)
Строка 1: Строка 1:
 +
{{Assignment|{{REVISIONUSER}}}}
 +
Авторы: [[Участник:Светлана Морозова|Морозова Светлана]], [[Участник:Smirnov.maxim|Смирнов Максим]].
 +
Вклад авторов:
  
 +
Смирнов Максим:
 +
*п.1.5
 +
*п.1.7
 +
*п.1.8
 +
*п.1.9
 +
*п.2.7
  
= ЧАСТЬ. Свойства и структура алгоритмов =
+
Морозова Светлана
 +
*п.1.1
 +
*п.1.2
 +
*п.1.3
 +
*п.1.4
 +
*п.1.6
 +
*п.1.10
 +
*п.3
 +
 
 +
= Свойства и структура алгоритмов =
  
  
Строка 11: Строка 29:
 
Решением этих проблем стал алгоритм, известный как BIRCH.
 
Решением этих проблем стал алгоритм, известный как BIRCH.
  
'''BIRCH''' (balanced iterative reducing and clustering using hierarchies)- алгоритм, применяемый в области [https://ru.wikipedia.org/wiki/Data_mining Data mining] и использующий принципы [https://ru.wikipedia.org/wiki/%D0%98%D0%B5%D1%80%D0%B0%D1%80%D1%85%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BA%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F иерархической кластеризации].
+
'''BIRCH'''<ref>Нейский И.М. Классификация и сравнение методов кластеризации // Интеллектуальные технологии и системы. Сборник учебно-методических работ и статей аспирантов и студентов. – М.: НОК «CLAIM», 2006. – Выпуск 8. – С. 130-142.</ref><ref>T Zhang, R Ramakrishnan, M Livny. BIRCH: An Efficient Data Clustering Method for Very Large Databases - 1996. - С.103-114)</ref> - алгоритм, применяемый в области [https://ru.wikipedia.org/wiki/Data_mining Data mining] и использующий принципы [https://ru.wikipedia.org/wiki/%D0%98%D0%B5%D1%80%D0%B0%D1%80%D1%85%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BA%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F иерархической кластеризации].
  
 
Если имеется очень большой набор данных, то в пространстве он распределен, как правило, неравномерно. Кластерный анализ определяет места наибольшего и наименьшего скоплений, чтобы таким образом понять всю картину целиком. Кроме того, полученные кластеры визуализируются гораздо нагляднее, чем начальные "сырые" данные.
 
Если имеется очень большой набор данных, то в пространстве он распределен, как правило, неравномерно. Кластерный анализ определяет места наибольшего и наименьшего скоплений, чтобы таким образом понять всю картину целиком. Кроме того, полученные кластеры визуализируются гораздо нагляднее, чем начальные "сырые" данные.
Строка 17: Строка 35:
  
 
Для наилучшего решения этих проблем BIRCH распределяет входящие данные по кластерам динамически. Для эффективной кластеризации алгоритму требуется всего одно сканирование данных (т.е. с увеличением количества данных сложность увеличивается линейно). А при помощи одной (или более) дополнительных итераций можно и далее улучшать эффективность. BIRCH также является первым алгоритмом, предложенным для эффективного управления "шумами" (данными, которые не вписываются в общее представление модели).
 
Для наилучшего решения этих проблем BIRCH распределяет входящие данные по кластерам динамически. Для эффективной кластеризации алгоритму требуется всего одно сканирование данных (т.е. с увеличением количества данных сложность увеличивается линейно). А при помощи одной (или более) дополнительных итераций можно и далее улучшать эффективность. BIRCH также является первым алгоритмом, предложенным для эффективного управления "шумами" (данными, которые не вписываются в общее представление модели).
 
 
  
 
== Математическое описание алгоритма ==
 
== Математическое описание алгоритма ==
Строка 43: Строка 59:
  
 
<math>D_1 = |\vec{X_{01}}-\vec{X_{02}}| = \sum_{i=1}^d |{\vec{X_{01}}}^{(i)}-{\vec{X_{02}}}^{(i)}| </math>
 
<math>D_1 = |\vec{X_{01}}-\vec{X_{02}}| = \sum_{i=1}^d |{\vec{X_{01}}}^{(i)}-{\vec{X_{02}}}^{(i)}| </math>
 
  
 
Пусть имеются два кластера, содержащих соответственно  <math>N_1</math> и <math>N_2</math> точек размерности <math>d</math>: <math>\{\vec{X_i}\}</math>, где <math>i= 1,2, ...,N_1</math> и <math>\{\vec{X_j}\}</math>, где <math>j= N_1+1,N_1+2, ...,N_1+N_2</math>.
 
Пусть имеются два кластера, содержащих соответственно  <math>N_1</math> и <math>N_2</math> точек размерности <math>d</math>: <math>\{\vec{X_i}\}</math>, где <math>i= 1,2, ...,N_1</math> и <math>\{\vec{X_j}\}</math>, где <math>j= N_1+1,N_1+2, ...,N_1+N_2</math>.
Строка 59: Строка 74:
 
Таким образом, величины <math>\vec{X_0}</math>, <math>R</math> и <math>D</math> относятся к отдельным кластерам, а <math>D_0</math>, <math>D_1</math>, <math>D_2</math>, <math>D_3</math> и <math>D_4</math> - к объединению двух кластеров.
 
Таким образом, величины <math>\vec{X_0}</math>, <math>R</math> и <math>D</math> относятся к отдельным кластерам, а <math>D_0</math>, <math>D_1</math>, <math>D_2</math>, <math>D_3</math> и <math>D_4</math> - к объединению двух кластеров.
  
=== Кластерные элементы и кластерное дерево ===
+
=== Кластерный элемент и кластерное дерево ===
  
 
В основе концепции алгоритма BIRCH лежат понятия '''кластерного элемента''' и '''кластерного дерева (CF Tree)'''.
 
В основе концепции алгоритма BIRCH лежат понятия '''кластерного элемента''' и '''кластерного дерева (CF Tree)'''.
Строка 65: Строка 80:
 
====Кластерный элемент ====
 
====Кластерный элемент ====
  
''Определение.'' Пусть в кластере содержатся  <math>N</math> точек размерности  <math>d</math>:<math>\vec{X_i}</math>, где  <math>i=1,2,...,N</math>.  
+
''Определение.'' Пусть в кластере содержатся  <math>N</math> точек размерности  <math>d</math>:<math>\{\vec{X_i}\}</math>, где  <math>i=1,2,...,N</math>.  
 
'''Кластерный элемент (CF)''' - тройка чисел, характеризующая информацию о кластере:  
 
'''Кластерный элемент (CF)''' - тройка чисел, характеризующая информацию о кластере:  
 
<math>CF = (N, \vec{LS}, SS)</math>, где <math>N</math> - количество элементов входных данных, содержащихся в кластере, <math>\vec{LS}</math> - линейная сумма входных данных (т.е. <math>\sum_{i=1}^{N}\vec{X_i}</math>), <math>SS</math> - сумма квадратов входных данных (т.е. <math>\sum_{i=1}^{N}{\vec{X_i}}^2</math>)
 
<math>CF = (N, \vec{LS}, SS)</math>, где <math>N</math> - количество элементов входных данных, содержащихся в кластере, <math>\vec{LS}</math> - линейная сумма входных данных (т.е. <math>\sum_{i=1}^{N}\vec{X_i}</math>), <math>SS</math> - сумма квадратов входных данных (т.е. <math>\sum_{i=1}^{N}{\vec{X_i}}^2</math>)
Строка 80: Строка 95:
 
==== Кластерное дерево ====
 
==== Кластерное дерево ====
  
''Определение.'' '''Кластерное дерево (CF Tree)''' - это взвешенно сбалансированное дерево с двумя параметрами: <math>B</math> - коэффициент разветвления, <math>T</math> - пороговая величина. Каждый нелистьевой узел дерева имеет не более чем <math>B</math> вхождений узлов следующей формы: <math>[CF_i,child_i]</math>, где <math>i=1,2,...,B</math>, ''child'' - указатель на i-й дочерний узел, <math>CF_i</math> - CF вектор соответствующего подкластера.
+
''Определение.'' '''Кластерное дерево (CF Tree)''' - это взвешенно сбалансированное дерево с двумя параметрами: <math>B</math> - коэффициент разветвления, <math>T</math> - пороговая величина.
 +
 
 +
Каждый нелистьевой узел дерева имеет не более чем <math>B</math> вхождений узлов следующей формы: <math>[CF_i,child_i]</math>, где <math>i=1,2,...,B</math>, ''child'' - указатель на i-й дочерний узел, <math>CF_i</math> - CF вектор соответствующего подкластера.
  
 
Каждый листьевой узел имеет ссылку на два соседних узла (''prev'' и ''next'') для того, чтобы связать все узлы для эффективного сканирования.
 
Каждый листьевой узел имеет ссылку на два соседних узла (''prev'' и ''next'') для того, чтобы связать все узлы для эффективного сканирования.
 
Все листьевые узлы должны удовлетворять пороговому ограничению <math>T</math>, т.е. диаметр (радиус) не должен превосходить <math>T</math>.
 
Все листьевые узлы должны удовлетворять пороговому ограничению <math>T</math>, т.е. диаметр (радиус) не должен превосходить <math>T</math>.
В процессе вставки новых данных CF дерево строится динамически. Оно использует вставку данных для кластеризации точно также как <math>B+</math> дерево использует её для поиска.
+
В процессе вставки новых данных CF дерево строится динамически. Оно использует вставку данных для кластеризации точно также как <math>B+</math> [https://ru.wikipedia.org/wiki/B%2B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE дерево] использует её для поиска.
 
CF дерево очень компактно, поскольку каждый листьевой узел - это не просто точка, а подкластер (который объединяет множество точек с учётом ограничения <math>T</math>).
 
CF дерево очень компактно, поскольку каждый листьевой узел - это не просто точка, а подкластер (который объединяет множество точек с учётом ограничения <math>T</math>).
  
 
==== Операция вставки в '''CF''' дерево ====
 
==== Операция вставки в '''CF''' дерево ====
  
Опишем алгоритм вставки записи <math>Ent</math> в CF дерево:
+
Опишем алгоритм вставки элемнта <math>Ent</math> в CF дерево:
 +
 
 +
1) ''Определение подходящего листа'': Начиная с корня, алгоритм рекурсивно спускается по CF дереву, выбирая '''ближайший''' дочерний узел в соответствии с выбранной метрикой <math>D0</math>, <math>D1</math>, <math>D2</math>, <math>D3</math> или <math>D4</math>.
 +
 
 +
2) ''Преобразование листа'': Когда алгоритм доходит до листа, он находит ближайшую листьевой элемент, скажем, <math>L_1</math>, а затем проверяет, можно ли добавить ''Ent'' к <math>L_1</math> без нарушения порогового условия. Если да, то с учётом этого изменяется CF вектор для <math>L_1</math>; если нет, то ''Ent'' становится новым элементом листа. Если в листе для этого достаточно места, то шаг окончен, иначе он должен "расщепиться". Расщепление узла производится при помощи выбора за основу наиболее удалённой друг от друга пары элементов и перераспределение оставшихся элементов в соответствии с выбранным критерием близости.
 +
 
 +
3) ''Преобразование пути к листу'': После вставки ''Ent'' в лист мы должны обновить информацию о CF для каждого нелистьевого элемента на пути к листу. При отсутствии расщепления это означает простое сложение CF векторов для отражения факта добавления ''Ent''. Расщепление листа же требует вставки нового нелистьевого элемента в родительский узел для задания только что созданного листа. Если у родителя есть место для этого элемента, то необходимо просто преобразовать CF векторы на всех более высоких уровнях. В общем случае, однако, нам также придётся расщепить родительский узел, и так далее до корня. Если расщеплён корень, то высота дерева увеличивается на единицу.
 +
 
 +
4) ''Улучшение слияния'': Расщепление вызвано ограничением на размер узла, который не зависит от кластеризационных свойств данных. Если во входящем потоке присутствуют "искажённые" (из областей с низкой плотностью) данные, это может повлиять на качество кластеризации, а также уменьшить эффективность использования памяти. Дополнительный шаг алгоритма помогает решить эти проблемы: предположим, что произошло расщепление листа, и распространение этого процесса остановилось на некотором нелистьевом узле <math>N_j</math>, то есть <math>N_j</math> может вместить дополнительный элемент, полученный после расщепления. Теперь мы сканируем узел <math>N_j</math> для нахождения двух наиболее близких элементов. Если это не пара, отвечающая расщеплению, мы пытаемся объединить их и поставить в соответствие два дочерних узла. Если количество элементов в дочерних узлах  больше B, мы снова расщепляем результат объединения.
 +
В процессе повторного расщепления, в случае, если один источник собирает достаточно элементов для того, чтобы полностью заполнить узел, оставшиеся элементы передаются другом источнику. В итоге, если объединённые элементы помещаются в одном узле, в нём освобождается место для ещё одного элемента. Тем самым увеличивается степень использования свободного пространства и откладывается дальнейшее расщепление. В ином случае мы улучшаем распределение элементов в двух ближайших подкластерах.
  
1) ''Определение подходящего листа'': Начиная с корня, алгоритм рекурсивно спускается по CF дереву, выбирая '''ближайший''' дочерний узел в соответствии с выбранной метрикой <math>D0</math>, <math>D1</math>, <math>D2</math>, <math>D3</math> или <math>D4</math>
+
== Вычислительное ядро алгоритма ==
  
2) ''Преобразование листа'': Когда алгоритм достигает листьевого узла, он находит ближайшую листьевую запись, скажем, <math>L_1</math>, а затем проверяет, может ли <math>L_1</math>, "присоединить" ''Ent'', без нарушения порогового условия. Если это так, то CF вектор для <math>L_1</math>, изменяется с отражением этого факта. Если нет, то к листу добавляется новая запись для ''Ent''. Если в листе есть место для этой новой записи, то шаг окончен, иначе листьевой узел должен "расщепиться". Расщепление узла производится при помощи выбора наиболее удалённой друг от друга пары записей как источника и перераспределение оставшихся записей в соответствии с выбранным "критерием близости".
+
Вычислительное ядро алгоритма заключается в многократном выполнении операции вставки нового элемента в дерево, в процессе чего требуется вычисление следующих величин:
  
3) ''Преобразование пути к листу'': После вставки ''Ent'' в лист мы должны обновить информацию о CF для каждой нелистьевой записи по дороге к листу. При отсутствии разделения это означает простое сложение CF векторов для отражения факта добавления ''Ent''. Расщепление же листа требует вставки новой нелистьевой записи в родительский узел для описание только что созданного листа. Если у родителя есть место для этой записи, то нам нужно просто преобразовать CF векторы на всех более высоких уровнях. В общем случае, однако, нам также придётся расщепить родительский узел, и так далее до корня. Если расщеплён корень, то высота дерева увеличивается на единицу.
+
* радиуса <math>R</math> или диаметра <math>D</math> кластерного элемента. Выполняется при попытке вставить новый элемент в один из подкластеров листьевого узла дерева.
  
4) ''Улучшение слияния'': Разделение вызвано ограничением на размер узла, который не зависит от кластеризационных свойств данных. Если во входящем потоке присутствуют "искажённые" (из областей с низкой плотностью) данные, это может повлиять на качество кластеризации, а также уменьшить эффективность использования памяти. Дополнительный шаг алгоритма помогает решить эти проблемы: предположим, что произошло расщепление листа, и распространение этого процесса остановилось на некотором нелистьевом узле <math>N_j</math>, то есть <math>N_j</math> can accomodate the additional entry resulting from the split. Теперь мы сканируем узел <math>N_j</math> для нахождения двух наиболее близких записей. Если это не пара, отвечающая разделению, мы пытаемся объединить их и поставить в соответствие два дочерних узла. Если в двух дочерних узлах записей больше, чем может содержать одна страница, мы снова разделяем результат объединения. В процессе перерасщепления, в том случае, если одна seed притягивает записей достаточно для того, чтобы заполнить таблицу, мы можем просто положить оставшиеся записи в другой ssed. В итоге, если мы объединяем подходящие записи на одной странице, м освобождаем в узле место для дальнейшего использования, создаём в узле <math>N_j</math> место для дополнительной записи, тем самым увеличивая степень использования свободного пространства и откладывая дальнейшее расщепление; в ином случае мы улучшаем распределение записей в двух ближайших детях.
+
* расстояния между двумя элементами. Выполняется при поиске ближайшего по отношению к новому элементу подкластера в узле дерева по одной из рассмотренных в разд. 1.2.1 метрик <math>D_0</math>, <math>D_1</math>, <math>D_2</math>, <math>D_3</math> или <math>D_4</math>.  
  
Так как каждый узел в соответствии со своим размером может содержать ограниченное число записей, он всегда соответствует обычному кластеру. Иногда два подкластера, которые должны были быть в одном кластере, разделяются между узлами. В зависимости от порядка входных данных и степени их разброса, также возможна ситуация, когда два подкластера, которые не должны находиться в одном кластере, хранятся в одном узле. Эти нечастые, но нежелательные аномалии, спровоцированные размером страницы, можно исправить при помощи глобального (или полуглобального)агоритма, который собирает лист между узлами. Другой нежелательный случай, это ситуация, когда две одинаковые точки вставляются дважды, но в разное время, две их копии могут входить в отдельные листьевые записи. Или, другими словами, иногда в ситуации разброса входных данных, точка может входить в ту листьевую запись, в которую она не должна входить. Эту проблему можно решить при помощи дальнейшего улучшения данных.
+
Зная характеристики кластерных элементов <math>N</math>, <math>\vec{LS}</math> и <math>S</math>, в результате алгебраических преобразований можно получить следующие упрощенные формулы вычисления необходимых значений:
  
== Вычислительное ядро алгоритма ==
+
<math>\vec{X_0} = \frac{\vec{LS}}{N}</math>
  
Рисунок 1 представляет обзор алгоритма BIRCH. Главной задачей фазы 1 является сканирование всех данных и построение в памяти исходного CF дерева, используя заданное количество памяти. Это дерево старается отразить информацию о кластеризации данных настолько хорошо, насколько это позволяют ограничения по памяти. Тогда как плотно распределённые данные хорошо группируются в подкластеры, более разрозненные данные удаляются. После Фазы 1 вспомогательные вычисления в дальнейших фазах будут:
+
<math>R = (\frac{SS - 2\vec{X_0}\vec{LS} + N(\vec{X_0})^2}{N})^{1/2}</math>
  
1) быстрее, потому что (а) больше не нужны операции ввода-вывода, (b) проблема кластеризации начальных данных упрощается до проблемы кластеризации подкластеров в листьевых записях;
+
<math>D = (\frac{2(N \cdot SS - (\vec{LS})^2)}{N(N-1)})^{1/2}</math>
  
2) точнее, потому что (а) большинство данных с низкой плотностью удалены, (b) оставшиеся данные распределены оптимально в соответствии с доступным количеством памяти
+
<math>D_2 = (\frac{N_1 \cdot SS_2 + N_2 \cdot SS_1 - 2\vec{LS_1}\vec{LS_2}}{N_1 \cdot N_2})^{1/2}</math>
  
3) менее чувствительны к порядку, потому что листьевые записи исходного дерева
+
<math>D_3 = (\frac{2((N_1+N_2)(SS_1+SS_2)-(\vec{LS_1}+\vec{LS_2})^2)}{(N_1+N_2)(N_1+N_2-1)})^{1/2}</math>
  
 +
== Макроструктура алгоритма ==
  
  
=== Фаза 1 ===
+
Реализация алгоритма BIRCH состояит из следующих четырёх фаз:
  
Рисунок 2 детализирует Фазу 1. Она начинается с определения порогового значения, сканирования данных и добавления данных в дерево. Если память заканчивается до окончания сканирования данных, увеличивается пороговое значение и строится новое, меньшее CF дерево при помощи повторной вставки листьевых записей в старое дерево. После того как старые листьевые записи добавлены повторно, сканирование данных (и вставка в новое дерево) продолжается с той точки, где процесс был приостановлен.
+
* '''Фаза 1'''. Главной задачей фазы 1 является сканирование всех данных и построение в памяти исходного CF дерева, используя заданное количество памяти. Это дерево стремится отразить информацию о кластеризации данных настолько хорошо, насколько это позволяют ограничения по памяти. При этом плотно распределённые данные группируются в подкластеры, а более разрозненные данные удаляются. После завершения фазы 1 вспомогательные вычисления в дальнейших фазах будут:
  
=== Уменьшаемость ===
+
1) быстрее, потому что (а) больше не нужны операции ввода-вывода, (b) проблема кластеризации начальных данных упрощается до проблемы кластеризации подкластеров в листьях;
  
Пусть <math>t_i</math> - это CF дерево с пороговым значением <math>T_i</math>. Его высота равна <math>h</math>, а размер (количество узлов) равен <math>S_i</math>. Задавая <math>T_{i+1}\geq T_i</math>, мы хотим использовать все листьевые записи <math>t_i</math> для построения нового CF дерева <math>t_{i+1}</math> с пороговым значением <math>T_{i+1}</math> так, чтобы размер <math>t_{i+1}</math> был не больше чем <math>S_i</math>. Далее описан алгоритм повторного построения, а также последовательность теорем уменьшаемости.
+
2) точнее, потому что (а) большинство данных с низкой плотностью удалены, (b) оставшиеся данные распределены оптимально (в соответствии с доступным количеством памяти);
  
Предположим, что внутри каждого CF дерева <math>t_i</math> все соседние записи пронумерованы от <math>0</math> до <math>n_k-1</math>, где <math>n_k</math> - это число записей в данном узле. Тогда '''путь''' из корневой записи (уровень 1) до листьевого узла (уровень ''h'') уникально представляется вектором <math>(i_1, i_2, ..., i_{h-1})</math>, где <math>i_j, j=1,...,h-1</math> - это номера записей j-го уровня. Поэтому естественно принять, что путь <math>({i_1}^(1), {i_2}^(1), ..., {i_{h-1}}^(1))</math> '''меньше''' пути <math>({i_1}^(2), {i_2}^(2), ..., {i_{h-1}}^(2))</math>, если <math>{i_1}^{(1)}={i_1}^{(2)}, ..., {i_{j-1}}^{(1)}={i_{j-1}}^{(2)}</math> и  <math>{i_j}^{(1)}<{i_j}^{(2)}</math> <math>(0 \leq j \leq h-1) </math>. Очевидно, что между понятиями листа и пути существует точное соответствие, поэтому в дальнейшем мы будет использовать эти понятия взаимозаменяемо.
 
  
 +
* '''Фаза 2'''. Данная фаза является опциональной. Известно, что существующие методы глобальной кластеризации, используемые в рамках фазы 3, имеют различные диапазоны входных значений, при которых их реализация наиболее эффективна. Поэтому потенциально существует пробел между размером фазы 1 и входными значениями фазы 3. И фаза 2 как раз является недостающим связующим звеном: так же как и фаза 1, она сканирует листьевые элементы начального CF дерева для того, чтобы построить меньшее дерево, удаляя ещё больше элементов с низкой плотностью и группируя переполненные подкластеры в большие кластеры.
  
Алгоритм показан на рмсунке 3. Имея определение пути, указанное выше, он сканирует и освобождает старое дерево путь за путём и в то же время путь за путём создаёт новое дерево. Новое дерево начинается с NULL, а "OldCurrentPath" начинается с крайнего левого пути старого дерева. Для "OldCurrentPath" алгоритм работает следующим образом:
 
  
1) ''Создание соответствующей "NewCurrentPath" в новом дереве'': узлы добавляются в новое дерево точно так же как и в старое, так что новое дерево никак не может стать больше старого
+
* '''Фаза 3'''. В данной фазе для листьевых элементов применяется (любой подходящий) алгоритм глобальной кластеризации. Существующие алгоритмы кластеризации наборов точек могут также работать с наборами подкластеров, каждый из которых представлен своим CF вектором. Зная CF вектор, можно вычислить центроид и в дальнейшем заменить всю информацию о кластере этим значением (этого достаточно для вычисления большинства необходимых метрик). После фазы 3 мы получаем набор кластеров, который отражает основные характеристики распределяемых данных.
 +
Однако, всё ещё могут оставаться некоторые неточности, для устранения которых существует фаза 4.
  
2) ''Вставка листьевых записей "OldCurrentPath" в новое дерево'': каждый лист в "OldCurrentPath" проверяется заново в соответствием с новым пороговым значением (???? АААА НАДОЕЛО)
+
* '''Фаза 4'''. Данная фаза является опциональной и влечёт за собой затраты на дополнительное сканирование данных для корректировки неточностей и дальнейшего улучшения кластеризации. Фаза 4 использует центроиды кластеров, полученные в фазе 3 для как основы и перераспределяет точки входных данных в ближайшие для них основы для получения нового списка кластеров. Фаза 4, если это необходимо пользователю, может быть расширена дополнительными проходами для уверенности в том, что результат приближается к оптимальному.
  
3) ''Освобождение места в "OldCurrentPath" и "NewCurrentPath"'': после обработки всех листьев в "OldCurrentPath", неиспользуемые узлы могут быть освобождены. Также может оказаться, что некоторые узлы "NewCurrentPath" пусты из-за того, что листьевые записи, которые изначально соответствовали этому пути, теперь "продвинуты вперёд" (???). В этом случае пустые узлы также необходимо удалить.
+
== Схема реализации последовательного алгоритма ==
 +
Последовательную реализацию основных операций алгоритма BIRCH можно продемонстрировать на примере следующего фрагмента кода на языке C++:
  
4) ''"OldCurrentPath" устанавливается на следующий путь старого дерева (если такой существует), и шаги выше повторяются''.
+
<source lang="c++">
 +
void CF_Node::insert(const CF_Cluster &entry)
 +
{
 +
    //Находим ближайший к новому элементу подкластер в узле
 +
    СF_Vector_it closest = entry.findClosest(subclusters);
 +
    //Если узел пустой, добавляем в него новый подкластер
 +
    if (closest == subclusters.end()) {
 +
        subclusters.push_back(entry);
 +
        return;
 +
    }
 +
    closest->add(entry);
 +
    //Если узел является листьевым, и ближайший подкластер не может вместить
 +
    //новый элемент, добавляем в узел новый подкластер
 +
    if (leaf) {
 +
        if (closest->D > threshold) {
 +
            closest->remove(entry);
 +
            subclusters.push_back(entry);
 +
        }
 +
    }
 +
    else {
 +
        CF_Node *node = closest->child;
 +
        node->insert(entry);
 +
        //Если при добавлении нового элемента в дочерний узел тот переполнился,
 +
        //расщепляем его       
 +
        if (node->getSubclusters().size() > bFactor) {
 +
            CF_Vector newClusters = node->splitNode();
 +
            delete node;
 +
            subclusters.erase(closest);
 +
            subclusters.insert(subclusters.end(), newClusters.begin(), newClusters.end());
 +
        }
 +
    }
 +
    //Если узел является корневым и он переполнен, расщепляем его
 +
    if (root && subclusters.size() > bFactor) {
 +
        subclusters = splitNode();
 +
        leaf = false;
 +
    }
 +
}
  
'''Теорема (уменьшаемости)''': Пусть по указанному выше алгоритму CF дерево <math>t_{i+1}</math> с пороговым значением <math>T_{i+1}</math> построено из CF дерева <math>t_i</math> с пороговым значением <math>T_i</math> и пусть <math>S_i</math> и <math>S_{i+1}</math> - их соответствующие размеры. Если <math>T_{i+1} \geq T_i</math>, то <math>S_{i+1} \leq S_i</math> и преобразованию <math>t_i</math> в <math>t_{i+1}</math> необходимы как минимум h дополнительных страниц памяти, где h - это высота <math>t_i</math>.
+
CF_Vector CF_Node::splitNode()
 +
{
 +
    if (subclusters.size() < 2)
 +
        return (root) ? subclusters : CF_Vector{CF_Cluster(this)};
 +
    //Находим пару наиболее удаленных друг от друга подкластеров
 +
    CF_Vector_it pole1, pole2;
 +
    data_t longestDist = 0.0;
 +
    for (auto lhs = subclusters.begin(); lhs != subclusters.end() - 1; ++lhs) {
 +
        for (auto rhs = lhs + 1; rhs != subclusters.end(); ++rhs) {
 +
            auto distance = getDistance(*lhs, *rhs);
 +
            if (distance > longestDist) {
 +
                longestDist = distance;
 +
                pole1 = lhs;
 +
                pole2 = rhs;
 +
            }
 +
        }
 +
    }
 +
    //Разделяем множество всех подкластеров узла на две части
 +
    CF_Vector subclusters1, subclusters2;
 +
    for (auto it = subclusters.begin(); it != subclusters.end(); ++it) {
 +
        if (getDistance(*it, *pole1) < getDistance(*it, *pole2))
 +
            subclusters1.push_back(*it);
 +
        else
 +
            subclusters2.push_back(*it);
 +
    }
 +
    //Создаем два новых узла
 +
    CF_Node *node1 = new CF_Node(threshold, bFactor, count, leaf, subclusters1),
 +
            *node2 = new CF_Node(threshold, bFactor, count, leaf, subclusters2);
 +
    //Связываем листья
 +
    if (leaf) {
 +
        if (prevLeaf) {
 +
            node1->setPrevLeaf(prevLeaf);
 +
            prevLeaf->setNextLeaf(node1);
 +
        }
 +
        if (nextLeaf) {
 +
            node2->setNextLeaf(nextLeaf);
 +
            nextLeaf->setPrevLeaf(node2);
 +
        }
 +
        node1->setNextLeaf(node2);
 +
        node2->setPrevLeaf(node1);
 +
    }
 +
    CF_Cluster cluster1(node1), cluster2(node2);
 +
    return CF_Vector{cluster1, cluster2};
 +
}
 +
</source>
  
=== Пороговые значения ===
+
== Последовательная сложность алгоритма ==
  
Правильный выбор порогового значения может значительно уменьшить количество перепостроений дерева. Так как начальное пороговое значение <math>T_0</math> увеличивается динамически, мы можем установить его значение слишком маленьким. Но если начальное значение <math>T_0</math> слишком большое, мы получим менее детализированное CF дерево, чем это возможно при доступной памяти. BIRCH по умолчанию устанавливает значение, равное 0. Пользователь может его менять.
+
Для начала проанализируем вычислительную сложность фазы 1.
 +
Максимальный размер дерева <math>\frac{M}{P}</math>, где <math>P</math> - ограничение по памяти на размер узла, а <math>M</math> - общий объем памяти. Для того чтобы вставить элемент, мы должны пройти путь от корня до листа (это около <math>1+log_B\frac{M}{P}</math> узлов). В каждом узле в поисках "ближайшего" нам необходимо просмотреть B элементов; сложность для каждого элемента пропорциональна размерности ''d''.
  
Пусть значение <math>T_i</math> оказалось слишком маленьким, и мы вышли за пределы памяти после сканирования <math>N_i</math> точек и формирования <math>C_i</math> листьевых записей (каждая из которых удовлетворяет пороговому значению <math>T_i</math>). Основываясь на части данных, которые мы просканировали и той части дерева, которое мы уже построили, необходимо оценить следующее пороговое значение <math>T_{i+1}</math>. Эта оценка является сложной проблемой, а её решение выходит за пределы данной статьи.  
+
Поэтому сложность вставки всех входных точек <math>O(d \cdot N \cdot B(1+log_B\frac{M}{P}))</math>.
  
В настоящее время используется следующий подход:
+
В случае, когда необходимо перестроить дерево, предположим, что ES - это размер CF элемента. Существует максимум <math>\frac{M}{ES}</math> листьевых элементов для вставки, поэтому сложность повторной вставки листьевых элементов <math>O(d \cdot \frac{M}{ES} \cdot B(1+log_B\frac{M}{P}))</math>.
  
1) Мы пытаемся выбрать <math>T_{i+1}</math> так, чтобы <math>N_{i+1}=Min(2N_i,N)</math>. (????)
+
Количество итераций перестройки дерева зависит от пороговой величины. На самом деле, это около <math>log_2\frac{N}{N_0}</math> (двоичное основание появилось из-за того, что мы не можем провести оценку более чем в 2 раза отличающуюся от текущего размера). <math>N_0</math> - это число входных точек, загруженных в память с пороговым ограничением <math>T_0</math>.
  
2) Интуитивно мы хотим увеличить пороговое значение, основываясь на некоторой мере ''объёма''. Существует два различных обозначений объём, которые мы используем, оценивая пороговую величину. Первое - средний объём, который определяется как <math>V_\alpha=r^d</math>, где r - это средний радиус корневого кластера в CF дереве, а d - размерность пространства. Интуитивно понятно, что это мера места, занятого данными, проссканироанными до этого момента.
+
Соответственно, итоговая сложность фазы 1 <math>O(d \cdot N \cdot B(1+log_B\frac{M}{P})+log_2\frac{N}{N_0} \cdot d \cdot \frac{M}{ES} \cdot B(1+log_B\frac{M}{P}))</math>.
Следующее обозначение - упакованный объём, который определяется как <math>V_p = C_i*{T_i}^d</math>, где <math>C_i</math> - это количество листьевых записей, а <math>{T_i}^d</math> - максимальный объём листьевой записи. Интуитивно понятно, что это текущий объём, занятый листьевыми кластерами. Так как <math>C_i</math> остаётся прежней, даже если мы выходим за пределы памяти (так как мы работаем с фиксированным объёмом памяти), то мы можем приблизить <math>V_p</math> при помощи <math>{T_i}^d</math>.
 
  
Мы делаем предположение, что <math>r</math> растёт с числом точек <math>N_i</math>. Зная <math>r</math> и <math>N_i</math>, мы можем оценить <math>r_{i+1}</math>, используя метод наименьших квадратов (что за линейная регрессия??).  
+
Анализ фазы 2 проводится аналогично.
  
Определим коэффициент расширения <math>f = Max(1.0, \frac{r_{i+1}}{r_i}</math>, и используем это как эвристическую меру 
+
Что касается операций ввода-вывода, то в фазе 1 данные сканируются один раз, а в фазе 2 не сканируются вовсе.
 +
Некоторое количество вычислений связано с удалением точек из областей с низкой плотностью.
 +
Если количество доступной для этой операции памяти не больше ''M'' и проведено порядка <math>log_2\frac{N}{N_0}</math> перестроек дерева, то сложность ввода-вывода для фазы 1 существенно не отличается от сложности чтения из файла. Основываясь рассуждениях выше, сложность фаз 1 и 2 будет линейно увеличиваться с ростом N.
  
 +
В фазе 3 нет операций ввода-вывода. Её сложность ограничена константой, которая зависит от максимального размера входных данных, и варианта выбранного алгоритма для кластеризации.
 +
 +
Фаза 4 снова сканирует данные и записывает каждую точку в подходящий кластер; время работы пропорционально <math>N \cdot K</math>. 
  
  
 
<math></math>
 
<math></math>
  
 +
== Информационный граф ==
 +
 +
=== Вычисление расстояния ===
 +
 +
<math>D_2=\frac{N_1\cdot SS_2+N_2\cdot SS_1-2 \cdot \vec{LS_1}\cdot \vec{LS_2}}{N_1\cdot N_2}</math>, где
 +
 +
<math>CF_1=[N_1,\vec{LS_1},SS_1]</math>
 +
 +
<math>CF_2=[N_2,\vec{LS_2},SS_2]</math>
 +
 +
[[File:ZgYL51QJsQk.jpg|600px|thumb|center]]
 +
 +
=== Поиск ближайшего подкластера ===
 +
 +
<math>E</math> - новый элемент
 +
 +
<math>CF_i, i = 1,...,B</math> - подкластеры узла
 +
 +
<math>m</math> - операция min
 +
 +
<math>\rho</math> - нахождение расстояния
 +
 +
 +
[[File:PFA16KHUQ3I.jpg|600px|thumb|center]]
  
== Макроструктура алгоритма ==
 
  
== Схема реализации последовательного алгоритма ==
+
=== Скалярное произведение ===
 +
 
 +
<math>s = \vec{x}\cdot\vec{y}=\sum_{i=1}^d x_i\cdot y_i</math>
  
== Последовательная сложность алгоритма ==
+
[[File:Xb7FYXVMPpQ.jpg|600px|thumb|center]]
  
== Информационный граф ==
+
<math></math>
  
 
== Ресурс параллелизма алгоритма ==
 
== Ресурс параллелизма алгоритма ==
 +
Параллельно могут быть выполнены следующие шаги алгоритма:
 +
* Нахождение ближайшего к новому элементу подкластера в узле при выполнении операции вставки. Это возможно за счет того, что расстояние между парами элементов может быть вычислено независимо друг от друга.
 +
* Вычисление величин <math>\vec{LS},\vec{X0}, R, D, D_0-D_4</math>, в процессе чего выполняются операции сложения и скалярного произведения векторов.
 +
 +
Таким образом, параллельная сложность фазы 1 алгоритма будет равна <math>O((N + log_2\frac{N}{N_0} \cdot \frac{M}{ES})(log_2 B + log_2 d)(1+log_B\frac{M}{P}))</math>
 +
 +
Другим способом параллелизации алгоритма может служить создание и заполнение сразу множества кластерных деревьев, между которыми будут распределены входные данные. Множество всех подкластеров листьевых узлов полученных таким образом деревьев может быть подвергнуто глобальной кластеризации с помощью какого-либо из известных параллельных алгоритмов, например, k-средних<ref>[A Garg, N Gupta PBIRCH: A Scalable Parallel Clustering algorithm for Incremental Data //10th International Database Engineering and Applications Symposium (IDEAS'06), 2006</ref>.
  
 
== Входные и выходные данные алгоритма ==
 
== Входные и выходные данные алгоритма ==
 +
'''Входные данные:''' набор из <math>N</math> точек <math>\{X_i\}, i=1,...,N</math> размерности <math>d</math>.
 +
 +
'''Объем входных данных:''' <math>N \cdot d</math>
 +
 +
'''Выходные данные:''' кластерное дерево с не более чем <math>\frac{M}{P}</math> узлами.
 +
 +
'''Объем выходных данных:''' <math>M</math>
  
 
== Свойства алгоритма ==
 
== Свойства алгоритма ==
  
=== Достоинства алгоритма ===
+
Вычислительная мощность алгоритма имеет порядок <math>O(\frac{d \cdot B \cdot (1+log_B\frac{M}{P}) \cdot (N +log_2\frac{N}{N_0} \cdot \frac{M}{ES})}{N \cdot d + M})</math>
По сравнению с предыдущими методами BIRCH обладает следующими достоинствами:
+
 
 +
Алгоритм BIRCH не является детерминированным, так как процесс его выполнения во многом зависит от входных данных.
 +
 
 +
К достоинствам алгоритма можно отнести следующие его свойства:
  
 
1. BIRCH является локальным алгоритмом, то есть каждое решение о каждом элементе кластера принимается без повторного сканирования данных или уже существующих кластеров. Используются только метрики, отражающие близость элементов друг к другу.
 
1. BIRCH является локальным алгоритмом, то есть каждое решение о каждом элементе кластера принимается без повторного сканирования данных или уже существующих кластеров. Используются только метрики, отражающие близость элементов друг к другу.
Строка 183: Строка 338:
 
4. BIRCH не требует всего набора данных заранее (при этом просматривает его всего один раз).
 
4. BIRCH не требует всего набора данных заранее (при этом просматривает его всего один раз).
  
 +
В свою очередь, недостатки алгоритма можно сформулировать следующим образом:
  
 +
1. Алгоритм позволяет работать только с числовыми данными.
  
= ЧАСТЬ. Программная реализация алгоритма =
+
2. BIRCH хорошо выделяет только кластеры сферической формы.
  
= Литература =
+
3. Существует необходимость в задании пороговых значений.
 +
 
 +
= Программная реализация алгоритма =
  
[1] Википедия
 
 
== Особенности реализации последовательного алгоритма ==
 
== Особенности реализации последовательного алгоритма ==
 +
 +
== Локальность данных и вычислений ==
 +
 +
== Возможные способы и особенности параллельной реализации алгоритма ==
 +
 +
== Масштабируемость алгоритма и его реализации ==
 +
 +
Проведём исследование масштабируемости параллельной реализации алгоритма BIRCH. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].
 +
 +
 +
[[file:Масштабируемость параллельной реализации алгоритма BIRCH. Производительность.png|thumb|center|700px|Рисунок 1. График времени работы параллельной реализации алгоритма BIRCH. ]]
 +
 +
 +
[[file:Масштабируемость параллельной реализации алгоритма BIRCH. Эффективность.png|thumb|center|700px|Рисунок 2. График эффективности распараллеливания алгоритма BIRCH относительно последовательной реализации. ]]
 +
 +
 +
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
 +
* число процессоров [8 : 80] с шагом 8
 +
* число точек [100 000 : 1 000 000] с шагом 100 000
 +
 +
 +
В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:
 +
* минимальная эффективность реализации 9,13% (80 процессоров, 100 000 точек)
 +
* максимальная эффективность реализации 235,42% (8 процессоров, 800 000 точек)
 +
 +
Полученные результаты могут быть объяснены недерминированностью алгоритма BIRCH и существенной зависимостью времени его работы от входных данных.
 +
 +
Оценка масштабируемости параллельной реализации:
 +
* По числу процессов:  при увеличении числа процессов эффективность распараллеливания снижается. При количестве процессов <math>n>30</math> темп снижения становится несущественным.
 +
* По размеру задачи: при увеличении размера входных данных эффективность растет неравномерно, что свидетельствует о сложной зависимости от входных данных.
 +
 +
Для исследования возможностей паралеллизма алгоритма BIRCH была написана [https://github.com/duran-duran/birch реализация на языке C++] с использованием технологии MPI. В данной реализации входные данные равномерно распределяются между всеми процессами, в каждом из которых выполняется построение собственного кластерного дерева. Листьевые элементы полученных деревьев затем подвергаются глобальной кластеризации с помощью распределенного алгоритма k-средних. В качестве входных данных использовались точки размерности <math>d=5</math>, координаты которых были равномерно распределены в диапазоне <math>[-10000;10000]</math>.
 +
 +
{| class="wikitable mw-collapsible mw-collapsed"
 +
! Технические детали реализации
 +
|-
 +
|
 +
Компилятор: intel/15.0.090
 +
 +
Версия реализации MPI: openmpi/1.10.2-icc
 +
 +
Планировщик задач: slurm/2.5.6
 +
 +
Очереди: test, regular4
 +
 +
Команда компиляции: mpicxx -std=c++11 -Wall <source_files> -o <executable>
 +
 +
Команда запуска: sbatch -n <num_of_processes> -p <queue> -o <log_file> ompi <executable> <args>
 +
 +
|}
 +
 +
== Динамические характеристики и эффективность реализации алгоритма ==
 +
 +
== Выводы для классов архитектур ==
 +
 +
== Существующие реализации алгоритма ==
 +
 +
В составе пакетов и библиотек:
 +
* [http://scikit-learn.org/stable/modules/generated/sklearn.cluster.Birch.html scikit-learn]
 +
* [http://cucis.ece.northwestern.edu/projects/DMS/MineBench.html NU-MineBench]
 +
Пользовательские реализации:
 +
* [https://code.google.com/archive/p/jbirch/ JBIRCH]
 +
 +
= Литература =

Текущая версия на 17:44, 13 декабря 2016

Symbol wait.svgЭта работа прошла предварительную проверку
Дата последней правки страницы:
13.12.2016
Данная работа соответствует формальным критериям.
Проверено Coctic.

Авторы: Морозова Светлана, Смирнов Максим. Вклад авторов:

Смирнов Максим:

  • п.1.5
  • п.1.7
  • п.1.8
  • п.1.9
  • п.2.7

Морозова Светлана

  • п.1.1
  • п.1.2
  • п.1.3
  • п.1.4
  • п.1.6
  • п.1.10
  • п.3

Содержание

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Нахождение полезных для анализа закономерностей в больших объёмах данных с недавних пор вызывает значительный интерес. В связи с этим ввелось и стало активно развиваться такое понятие как кластеризация.

Ранние работы и алгоритмы, разработанные в этой области, не уделяли достаточного внимания анализу очень больших наборов данных или минимизации издержек на процессы ввода-вывода. Решением этих проблем стал алгоритм, известный как BIRCH.

BIRCH[1][2] - алгоритм, применяемый в области Data mining и использующий принципы иерархической кластеризации.

Если имеется очень большой набор данных, то в пространстве он распределен, как правило, неравномерно. Кластерный анализ определяет места наибольшего и наименьшего скоплений, чтобы таким образом понять всю картину целиком. Кроме того, полученные кластеры визуализируются гораздо нагляднее, чем начальные "сырые" данные. Задачей алгоритмов кластеризации является не только простое разбиение данных на кластеры, но и работа в рамках ограниченного объёма доступной памяти (как правило, её объём гораздо меньше, чем размер исходного набора данных) и минимизация времени, требуемого на операции ввода-вывода.

Для наилучшего решения этих проблем BIRCH распределяет входящие данные по кластерам динамически. Для эффективной кластеризации алгоритму требуется всего одно сканирование данных (т.е. с увеличением количества данных сложность увеличивается линейно). А при помощи одной (или более) дополнительных итераций можно и далее улучшать эффективность. BIRCH также является первым алгоритмом, предложенным для эффективного управления "шумами" (данными, которые не вписываются в общее представление модели).

1.2 Математическое описание алгоритма

1.2.1 Теоретическая основа

Пусть в кластере имеются [math]N[/math] точек размерности [math]d[/math]: [math]\{\vec{X_i}\}, i=1,2,...,N[/math]. Тогда центроид [math]{\vec{{X_0}}}[/math], радиус [math]R[/math] и диаметр [math]D[/math] кластера определяются следующим образом:

[math]{\vec{X_0}}=\frac{\sum_{i=1}^N\vec{X_i}}{N}[/math]

[math]R = (\frac{\sum_{i=1}^N{(\vec{X_i} - \vec{X_0})}^2}{N})^{1/2}[/math]

[math]D = (\frac{\sum_{i=1}^N\sum_{j=1}^N{(\vec{X_i} - \vec{X_j})}^2}{N(N-1)})^{1/2}[/math]

[math]R[/math] - это среднее расстояние от каждой точки до центроида. [math]D[/math] - это среднее расстояние между парами в кластере. Данные величины являются альтернативными метриками плотности кластера относительно центроида.

Для измерения близости друг к другу двух кластеров вводятся следующие метрики:

пусть даны центроиды двух кластеров [math]\vec{X_{01}}[/math] и [math]\vec{X_{02}}[/math]. Евклидова метрика [math]D_0[/math] и метрика Манхэттена [math]D1[/math] между двумя кластерами определяются следующим образом:

[math]D_0 = ((\vec{X_{01}}-\vec{X_{02}})^2)^{1/2}[/math]

[math]D_1 = |\vec{X_{01}}-\vec{X_{02}}| = \sum_{i=1}^d |{\vec{X_{01}}}^{(i)}-{\vec{X_{02}}}^{(i)}| [/math]

Пусть имеются два кластера, содержащих соответственно [math]N_1[/math] и [math]N_2[/math] точек размерности [math]d[/math]: [math]\{\vec{X_i}\}[/math], где [math]i= 1,2, ...,N_1[/math] и [math]\{\vec{X_j}\}[/math], где [math]j= N_1+1,N_1+2, ...,N_1+N_2[/math].

Среднее расстояние [math]D_2[/math], среднее внутрикластерное расстояние [math]D_3[/math] и дисперсия [math]D_4[/math] для двух кластеров определяются следующим образом:

[math]D_2 = (\frac{\sum_{i=1}^{N_1}\sum_{j=N_1+1}^{N_1+N_2}{(\vec{X_i} - \vec{X_j})}^2}{N_1N_2})^{1/2}[/math]

[math]D_3 = (\frac{\sum_{i=1}^{N_1+N_2}\sum_{j=1}^{N_1+N_2}{(\vec{X_i} - \vec{X_j})}^2}{(N_1+N_2)(N_1+N_2-1)})^{1/2}[/math]


[math]D_4 = \sum_{k=1}^{N_1+N_2}(\vec{X_k} - \frac{\sum_{i=1}^{N_1+N_2}\vec{X_i}}{N_1+N_2})^2 - \sum_{i=1}^{N_1}(\vec{X_i} - \frac{\sum_{i=1}^{N_1}\vec{X_i}}{N_1})^2 - \sum_{j=N_1+1}^{N_1+N_2}(\vec{X_j} - \frac{\sum_{i=N_1+1}^{N_1+N_2}\vec{X_i}}{N_2})^2[/math]


Таким образом, величины [math]\vec{X_0}[/math], [math]R[/math] и [math]D[/math] относятся к отдельным кластерам, а [math]D_0[/math], [math]D_1[/math], [math]D_2[/math], [math]D_3[/math] и [math]D_4[/math] - к объединению двух кластеров.

1.2.2 Кластерный элемент и кластерное дерево

В основе концепции алгоритма BIRCH лежат понятия кластерного элемента и кластерного дерева (CF Tree).

1.2.2.1 Кластерный элемент

Определение. Пусть в кластере содержатся [math]N[/math] точек размерности [math]d[/math]:[math]\{\vec{X_i}\}[/math], где [math]i=1,2,...,N[/math]. Кластерный элемент (CF) - тройка чисел, характеризующая информацию о кластере: [math]CF = (N, \vec{LS}, SS)[/math], где [math]N[/math] - количество элементов входных данных, содержащихся в кластере, [math]\vec{LS}[/math] - линейная сумма входных данных (т.е. [math]\sum_{i=1}^{N}\vec{X_i}[/math]), [math]SS[/math] - сумма квадратов входных данных (т.е. [math]\sum_{i=1}^{N}{\vec{X_i}}^2[/math])

Теорема Пусть [math]CF_1 = (N_1, \vec{LS_1}, SS_1)[/math] и [math]CF_2 = (N_1, \vec{LS_2}, SS_2)[/math] - CF векторы двух непересекающихся кластеров. Тогда при их объединении образуется кластер со следующим CF вектором:

[math]CF = CF_1 + CF_2 = (N_1+N_2, \vec{LS_1}+\vec{LS_2}, SS_1+SS_2)[/math].

Из указанных выше определения и теоремы вытекает тот факт, что при объединении кластеров их CF вектор может вычисляться инкрементно и точно. Легко показать, что вычислить величины [math]\vec{X_0}[/math], [math]R[/math], [math]D[/math], [math]D_0[/math], [math]D_1[/math], [math]D_2[/math], [math]D_3[/math], [math]D_4[/math], как и обычные метрики, также не составит труда.

Таким образом, в данном случае информацией о кластере является не весь набор точек, а вектор CF. Хранение одного только вектора может показаться неэффективным, но этого вполне достаточно для оперирования всеми необходимыми метриками, на основе которых принимаются решения в алгоритме BIRCH.

1.2.2.2 Кластерное дерево

Определение. Кластерное дерево (CF Tree) - это взвешенно сбалансированное дерево с двумя параметрами: [math]B[/math] - коэффициент разветвления, [math]T[/math] - пороговая величина.

Каждый нелистьевой узел дерева имеет не более чем [math]B[/math] вхождений узлов следующей формы: [math][CF_i,child_i][/math], где [math]i=1,2,...,B[/math], child - указатель на i-й дочерний узел, [math]CF_i[/math] - CF вектор соответствующего подкластера.

Каждый листьевой узел имеет ссылку на два соседних узла (prev и next) для того, чтобы связать все узлы для эффективного сканирования. Все листьевые узлы должны удовлетворять пороговому ограничению [math]T[/math], т.е. диаметр (радиус) не должен превосходить [math]T[/math]. В процессе вставки новых данных CF дерево строится динамически. Оно использует вставку данных для кластеризации точно также как [math]B+[/math] дерево использует её для поиска. CF дерево очень компактно, поскольку каждый листьевой узел - это не просто точка, а подкластер (который объединяет множество точек с учётом ограничения [math]T[/math]).

1.2.2.3 Операция вставки в CF дерево

Опишем алгоритм вставки элемнта [math]Ent[/math] в CF дерево:

1) Определение подходящего листа: Начиная с корня, алгоритм рекурсивно спускается по CF дереву, выбирая ближайший дочерний узел в соответствии с выбранной метрикой [math]D0[/math], [math]D1[/math], [math]D2[/math], [math]D3[/math] или [math]D4[/math].

2) Преобразование листа: Когда алгоритм доходит до листа, он находит ближайшую листьевой элемент, скажем, [math]L_1[/math], а затем проверяет, можно ли добавить Ent к [math]L_1[/math] без нарушения порогового условия. Если да, то с учётом этого изменяется CF вектор для [math]L_1[/math]; если нет, то Ent становится новым элементом листа. Если в листе для этого достаточно места, то шаг окончен, иначе он должен "расщепиться". Расщепление узла производится при помощи выбора за основу наиболее удалённой друг от друга пары элементов и перераспределение оставшихся элементов в соответствии с выбранным критерием близости.

3) Преобразование пути к листу: После вставки Ent в лист мы должны обновить информацию о CF для каждого нелистьевого элемента на пути к листу. При отсутствии расщепления это означает простое сложение CF векторов для отражения факта добавления Ent. Расщепление листа же требует вставки нового нелистьевого элемента в родительский узел для задания только что созданного листа. Если у родителя есть место для этого элемента, то необходимо просто преобразовать CF векторы на всех более высоких уровнях. В общем случае, однако, нам также придётся расщепить родительский узел, и так далее до корня. Если расщеплён корень, то высота дерева увеличивается на единицу.

4) Улучшение слияния: Расщепление вызвано ограничением на размер узла, который не зависит от кластеризационных свойств данных. Если во входящем потоке присутствуют "искажённые" (из областей с низкой плотностью) данные, это может повлиять на качество кластеризации, а также уменьшить эффективность использования памяти. Дополнительный шаг алгоритма помогает решить эти проблемы: предположим, что произошло расщепление листа, и распространение этого процесса остановилось на некотором нелистьевом узле [math]N_j[/math], то есть [math]N_j[/math] может вместить дополнительный элемент, полученный после расщепления. Теперь мы сканируем узел [math]N_j[/math] для нахождения двух наиболее близких элементов. Если это не пара, отвечающая расщеплению, мы пытаемся объединить их и поставить в соответствие два дочерних узла. Если количество элементов в дочерних узлах больше B, мы снова расщепляем результат объединения. В процессе повторного расщепления, в случае, если один источник собирает достаточно элементов для того, чтобы полностью заполнить узел, оставшиеся элементы передаются другом источнику. В итоге, если объединённые элементы помещаются в одном узле, в нём освобождается место для ещё одного элемента. Тем самым увеличивается степень использования свободного пространства и откладывается дальнейшее расщепление. В ином случае мы улучшаем распределение элементов в двух ближайших подкластерах.

1.3 Вычислительное ядро алгоритма

Вычислительное ядро алгоритма заключается в многократном выполнении операции вставки нового элемента в дерево, в процессе чего требуется вычисление следующих величин:

  • радиуса [math]R[/math] или диаметра [math]D[/math] кластерного элемента. Выполняется при попытке вставить новый элемент в один из подкластеров листьевого узла дерева.
  • расстояния между двумя элементами. Выполняется при поиске ближайшего по отношению к новому элементу подкластера в узле дерева по одной из рассмотренных в разд. 1.2.1 метрик [math]D_0[/math], [math]D_1[/math], [math]D_2[/math], [math]D_3[/math] или [math]D_4[/math].

Зная характеристики кластерных элементов [math]N[/math], [math]\vec{LS}[/math] и [math]S[/math], в результате алгебраических преобразований можно получить следующие упрощенные формулы вычисления необходимых значений:

[math]\vec{X_0} = \frac{\vec{LS}}{N}[/math]

[math]R = (\frac{SS - 2\vec{X_0}\vec{LS} + N(\vec{X_0})^2}{N})^{1/2}[/math]

[math]D = (\frac{2(N \cdot SS - (\vec{LS})^2)}{N(N-1)})^{1/2}[/math]

[math]D_2 = (\frac{N_1 \cdot SS_2 + N_2 \cdot SS_1 - 2\vec{LS_1}\vec{LS_2}}{N_1 \cdot N_2})^{1/2}[/math]

[math]D_3 = (\frac{2((N_1+N_2)(SS_1+SS_2)-(\vec{LS_1}+\vec{LS_2})^2)}{(N_1+N_2)(N_1+N_2-1)})^{1/2}[/math]

1.4 Макроструктура алгоритма

Реализация алгоритма BIRCH состояит из следующих четырёх фаз:

  • Фаза 1. Главной задачей фазы 1 является сканирование всех данных и построение в памяти исходного CF дерева, используя заданное количество памяти. Это дерево стремится отразить информацию о кластеризации данных настолько хорошо, насколько это позволяют ограничения по памяти. При этом плотно распределённые данные группируются в подкластеры, а более разрозненные данные удаляются. После завершения фазы 1 вспомогательные вычисления в дальнейших фазах будут:

1) быстрее, потому что (а) больше не нужны операции ввода-вывода, (b) проблема кластеризации начальных данных упрощается до проблемы кластеризации подкластеров в листьях;

2) точнее, потому что (а) большинство данных с низкой плотностью удалены, (b) оставшиеся данные распределены оптимально (в соответствии с доступным количеством памяти);


  • Фаза 2. Данная фаза является опциональной. Известно, что существующие методы глобальной кластеризации, используемые в рамках фазы 3, имеют различные диапазоны входных значений, при которых их реализация наиболее эффективна. Поэтому потенциально существует пробел между размером фазы 1 и входными значениями фазы 3. И фаза 2 как раз является недостающим связующим звеном: так же как и фаза 1, она сканирует листьевые элементы начального CF дерева для того, чтобы построить меньшее дерево, удаляя ещё больше элементов с низкой плотностью и группируя переполненные подкластеры в большие кластеры.


  • Фаза 3. В данной фазе для листьевых элементов применяется (любой подходящий) алгоритм глобальной кластеризации. Существующие алгоритмы кластеризации наборов точек могут также работать с наборами подкластеров, каждый из которых представлен своим CF вектором. Зная CF вектор, можно вычислить центроид и в дальнейшем заменить всю информацию о кластере этим значением (этого достаточно для вычисления большинства необходимых метрик). После фазы 3 мы получаем набор кластеров, который отражает основные характеристики распределяемых данных.

Однако, всё ещё могут оставаться некоторые неточности, для устранения которых существует фаза 4.

  • Фаза 4. Данная фаза является опциональной и влечёт за собой затраты на дополнительное сканирование данных для корректировки неточностей и дальнейшего улучшения кластеризации. Фаза 4 использует центроиды кластеров, полученные в фазе 3 для как основы и перераспределяет точки входных данных в ближайшие для них основы для получения нового списка кластеров. Фаза 4, если это необходимо пользователю, может быть расширена дополнительными проходами для уверенности в том, что результат приближается к оптимальному.

1.5 Схема реализации последовательного алгоритма

Последовательную реализацию основных операций алгоритма BIRCH можно продемонстрировать на примере следующего фрагмента кода на языке C++:

void CF_Node::insert(const CF_Cluster &entry)
{
    //Находим ближайший к новому элементу подкластер в узле
    СF_Vector_it closest = entry.findClosest(subclusters);
    //Если узел пустой, добавляем в него новый подкластер
    if (closest == subclusters.end()) {
        subclusters.push_back(entry);
        return;
    }
    closest->add(entry);
    //Если узел является листьевым, и ближайший подкластер не может вместить
    //новый элемент, добавляем в узел новый подкластер
    if (leaf) {
        if (closest->D > threshold) {
            closest->remove(entry);
            subclusters.push_back(entry);
        }
    }
    else {
        CF_Node *node = closest->child;
        node->insert(entry);
        //Если при добавлении нового элемента в дочерний узел тот переполнился,
        //расщепляем его        
        if (node->getSubclusters().size() > bFactor) {
            CF_Vector newClusters = node->splitNode();
            delete node;
            subclusters.erase(closest);
            subclusters.insert(subclusters.end(), newClusters.begin(), newClusters.end());
        }
    }
    //Если узел является корневым и он переполнен, расщепляем его
    if (root && subclusters.size() > bFactor) {
        subclusters = splitNode();
        leaf = false;
    }
}

CF_Vector CF_Node::splitNode()
{
    if (subclusters.size() < 2)
        return (root) ? subclusters : CF_Vector{CF_Cluster(this)};
    //Находим пару наиболее удаленных друг от друга подкластеров
    CF_Vector_it pole1, pole2;
    data_t longestDist = 0.0;
    for (auto lhs = subclusters.begin(); lhs != subclusters.end() - 1; ++lhs) {
        for (auto rhs = lhs + 1; rhs != subclusters.end(); ++rhs) {
            auto distance = getDistance(*lhs, *rhs);
            if (distance > longestDist) {
                longestDist = distance;
                pole1 = lhs;
                pole2 = rhs;
            }
        }
    }
    //Разделяем множество всех подкластеров узла на две части
    CF_Vector subclusters1, subclusters2;
    for (auto it = subclusters.begin(); it != subclusters.end(); ++it) {
        if (getDistance(*it, *pole1) < getDistance(*it, *pole2))
            subclusters1.push_back(*it);
        else
            subclusters2.push_back(*it);
    }
    //Создаем два новых узла
    CF_Node *node1 = new CF_Node(threshold, bFactor, count, leaf, subclusters1),
            *node2 = new CF_Node(threshold, bFactor, count, leaf, subclusters2);
    //Связываем листья
    if (leaf) {
        if (prevLeaf) {
            node1->setPrevLeaf(prevLeaf);
            prevLeaf->setNextLeaf(node1);
        }
        if (nextLeaf) {
            node2->setNextLeaf(nextLeaf);
            nextLeaf->setPrevLeaf(node2);
        }
        node1->setNextLeaf(node2);
        node2->setPrevLeaf(node1);
    }
    CF_Cluster cluster1(node1), cluster2(node2);
    return CF_Vector{cluster1, cluster2};
}

1.6 Последовательная сложность алгоритма

Для начала проанализируем вычислительную сложность фазы 1. Максимальный размер дерева [math]\frac{M}{P}[/math], где [math]P[/math] - ограничение по памяти на размер узла, а [math]M[/math] - общий объем памяти. Для того чтобы вставить элемент, мы должны пройти путь от корня до листа (это около [math]1+log_B\frac{M}{P}[/math] узлов). В каждом узле в поисках "ближайшего" нам необходимо просмотреть B элементов; сложность для каждого элемента пропорциональна размерности d.

Поэтому сложность вставки всех входных точек [math]O(d \cdot N \cdot B(1+log_B\frac{M}{P}))[/math].

В случае, когда необходимо перестроить дерево, предположим, что ES - это размер CF элемента. Существует максимум [math]\frac{M}{ES}[/math] листьевых элементов для вставки, поэтому сложность повторной вставки листьевых элементов [math]O(d \cdot \frac{M}{ES} \cdot B(1+log_B\frac{M}{P}))[/math].

Количество итераций перестройки дерева зависит от пороговой величины. На самом деле, это около [math]log_2\frac{N}{N_0}[/math] (двоичное основание появилось из-за того, что мы не можем провести оценку более чем в 2 раза отличающуюся от текущего размера). [math]N_0[/math] - это число входных точек, загруженных в память с пороговым ограничением [math]T_0[/math].

Соответственно, итоговая сложность фазы 1 [math]O(d \cdot N \cdot B(1+log_B\frac{M}{P})+log_2\frac{N}{N_0} \cdot d \cdot \frac{M}{ES} \cdot B(1+log_B\frac{M}{P}))[/math].

Анализ фазы 2 проводится аналогично.

Что касается операций ввода-вывода, то в фазе 1 данные сканируются один раз, а в фазе 2 не сканируются вовсе. Некоторое количество вычислений связано с удалением точек из областей с низкой плотностью. Если количество доступной для этой операции памяти не больше M и проведено порядка [math]log_2\frac{N}{N_0}[/math] перестроек дерева, то сложность ввода-вывода для фазы 1 существенно не отличается от сложности чтения из файла. Основываясь рассуждениях выше, сложность фаз 1 и 2 будет линейно увеличиваться с ростом N.

В фазе 3 нет операций ввода-вывода. Её сложность ограничена константой, которая зависит от максимального размера входных данных, и варианта выбранного алгоритма для кластеризации.

Фаза 4 снова сканирует данные и записывает каждую точку в подходящий кластер; время работы пропорционально [math]N \cdot K[/math].


[math][/math]

1.7 Информационный граф

1.7.1 Вычисление расстояния

[math]D_2=\frac{N_1\cdot SS_2+N_2\cdot SS_1-2 \cdot \vec{LS_1}\cdot \vec{LS_2}}{N_1\cdot N_2}[/math], где

[math]CF_1=[N_1,\vec{LS_1},SS_1][/math]

[math]CF_2=[N_2,\vec{LS_2},SS_2][/math]

ZgYL51QJsQk.jpg

1.7.2 Поиск ближайшего подкластера

[math]E[/math] - новый элемент

[math]CF_i, i = 1,...,B[/math] - подкластеры узла

[math]m[/math] - операция min

[math]\rho[/math] - нахождение расстояния


PFA16KHUQ3I.jpg


1.7.3 Скалярное произведение

[math]s = \vec{x}\cdot\vec{y}=\sum_{i=1}^d x_i\cdot y_i[/math]

Xb7FYXVMPpQ.jpg

[math][/math]

1.8 Ресурс параллелизма алгоритма

Параллельно могут быть выполнены следующие шаги алгоритма:

  • Нахождение ближайшего к новому элементу подкластера в узле при выполнении операции вставки. Это возможно за счет того, что расстояние между парами элементов может быть вычислено независимо друг от друга.
  • Вычисление величин [math]\vec{LS},\vec{X0}, R, D, D_0-D_4[/math], в процессе чего выполняются операции сложения и скалярного произведения векторов.

Таким образом, параллельная сложность фазы 1 алгоритма будет равна [math]O((N + log_2\frac{N}{N_0} \cdot \frac{M}{ES})(log_2 B + log_2 d)(1+log_B\frac{M}{P}))[/math]

Другим способом параллелизации алгоритма может служить создание и заполнение сразу множества кластерных деревьев, между которыми будут распределены входные данные. Множество всех подкластеров листьевых узлов полученных таким образом деревьев может быть подвергнуто глобальной кластеризации с помощью какого-либо из известных параллельных алгоритмов, например, k-средних[3].

1.9 Входные и выходные данные алгоритма

Входные данные: набор из [math]N[/math] точек [math]\{X_i\}, i=1,...,N[/math] размерности [math]d[/math].

Объем входных данных: [math]N \cdot d[/math]

Выходные данные: кластерное дерево с не более чем [math]\frac{M}{P}[/math] узлами.

Объем выходных данных: [math]M[/math]

1.10 Свойства алгоритма

Вычислительная мощность алгоритма имеет порядок [math]O(\frac{d \cdot B \cdot (1+log_B\frac{M}{P}) \cdot (N +log_2\frac{N}{N_0} \cdot \frac{M}{ES})}{N \cdot d + M})[/math]

Алгоритм BIRCH не является детерминированным, так как процесс его выполнения во многом зависит от входных данных.

К достоинствам алгоритма можно отнести следующие его свойства:

1. BIRCH является локальным алгоритмом, то есть каждое решение о каждом элементе кластера принимается без повторного сканирования данных или уже существующих кластеров. Используются только метрики, отражающие близость элементов друг к другу.

2. BIRCH использует факт неравномерного распределения данных в пространстве и поэтому не все данные рассматриваются как одинаково важные для построения кластера. Области с большой плотностью обрабатываются как единый кластер. Данные в более разреженных областях могут удаляться (опционально).

3. BIRCH использует всю доступную память для получения наилучших из возможных подкластеров, в то же время минимизируя затраты на операции ввода/вывода. Оптимизация процесса кластеризации достигается за счет использования взвешенно-сбалансированного дерева. При этом время исполнения линейно.

4. BIRCH не требует всего набора данных заранее (при этом просматривает его всего один раз).

В свою очередь, недостатки алгоритма можно сформулировать следующим образом:

1. Алгоритм позволяет работать только с числовыми данными.

2. BIRCH хорошо выделяет только кластеры сферической формы.

3. Существует необходимость в задании пороговых значений.

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

Проведём исследование масштабируемости параллельной реализации алгоритма BIRCH. Исследование проводилось на суперкомпьютере "Ломоносов"[4] Суперкомпьютерного комплекса Московского университета.


Рисунок 1. График времени работы параллельной реализации алгоритма BIRCH.


Рисунок 2. График эффективности распараллеливания алгоритма BIRCH относительно последовательной реализации.


Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:

  • число процессоров [8 : 80] с шагом 8
  • число точек [100 000 : 1 000 000] с шагом 100 000


В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:

  • минимальная эффективность реализации 9,13% (80 процессоров, 100 000 точек)
  • максимальная эффективность реализации 235,42% (8 процессоров, 800 000 точек)

Полученные результаты могут быть объяснены недерминированностью алгоритма BIRCH и существенной зависимостью времени его работы от входных данных.

Оценка масштабируемости параллельной реализации:

  • По числу процессов: при увеличении числа процессов эффективность распараллеливания снижается. При количестве процессов [math]n\gt 30[/math] темп снижения становится несущественным.
  • По размеру задачи: при увеличении размера входных данных эффективность растет неравномерно, что свидетельствует о сложной зависимости от входных данных.

Для исследования возможностей паралеллизма алгоритма BIRCH была написана реализация на языке C++ с использованием технологии MPI. В данной реализации входные данные равномерно распределяются между всеми процессами, в каждом из которых выполняется построение собственного кластерного дерева. Листьевые элементы полученных деревьев затем подвергаются глобальной кластеризации с помощью распределенного алгоритма k-средних. В качестве входных данных использовались точки размерности [math]d=5[/math], координаты которых были равномерно распределены в диапазоне [math][-10000;10000][/math].

Технические детали реализации

Компилятор: intel/15.0.090

Версия реализации MPI: openmpi/1.10.2-icc

Планировщик задач: slurm/2.5.6

Очереди: test, regular4

Команда компиляции: mpicxx -std=c++11 -Wall <source_files> -o <executable>

Команда запуска: sbatch -n <num_of_processes> -p <queue> -o <log_file> ompi <executable> <args>

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

В составе пакетов и библиотек:

Пользовательские реализации:

3 Литература

  1. Нейский И.М. Классификация и сравнение методов кластеризации // Интеллектуальные технологии и системы. Сборник учебно-методических работ и статей аспирантов и студентов. – М.: НОК «CLAIM», 2006. – Выпуск 8. – С. 130-142.
  2. T Zhang, R Ramakrishnan, M Livny. BIRCH: An Efficient Data Clustering Method for Very Large Databases - 1996. - С.103-114)
  3. [A Garg, N Gupta PBIRCH: A Scalable Parallel Clustering algorithm for Incremental Data //10th International Database Engineering and Applications Symposium (IDEAS'06), 2006
  4. Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.