Участник:LKruglov/Алгоритм устойчивой кластеризации с использованием связей: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
(Новая страница: « == 1.1 Общее описание алгоритма ==»)
 
Строка 1: Строка 1:
  
 
== 1.1 Общее описание алгоритма ==
 
== 1.1 Общее описание алгоритма ==
 +
В связи с наличием огромного количества накопленной информации задача добычи данных становится все более важной. Кластеризация позволяет распределять данные по группам (кластрерам) так, что в каждой группе данные обладают схожими характеристиками, а в разных группах характеристики различаются.
 +
 +
Алгоритм устойчивой кластеризации с использованием связей (robust clustering using links, ROCK)построен на основе понятия связей между кластеризуемыми точками и их соседства. Две точки считаются соседями, если являются достаточно близким (схожими): <math>sim({p_i}, {p_j}) >= \theta</math>, где <math>\theta</math> - заданное пороговое значение в интервале от 0 до 1.
 +
 +
Связь <math>link({p_i}, {p_j})</math> между двумя точками определяется как число общих соседей между точками <math>{p_i}</math> и <math>{p_j}</math>. Таким образом, чем большее значение функции связи для двух точек, тем более вероятно они принадлежат одному кластеру.
 +
 +
В отличие от алгоритмов кластеризации, учитывающих локальные характеристики точек, данный алгоритм учитывает глобальную информацию о соседях точек при принятии решения о помещение точек в кластеры, что делает его очень устойчивым.
 +
 +
== Математическое описание алгоритма ==
 +
Итак, задача кластеризации сводиться к такому разбиению точек на кластеры, которое максимизирует сумму связей точек принадлежащих одному кластеру, и минимизирует эту функцию для точек из разных кластеров. Отсюда следует следующая целевая функция для разбияния на <math>k</math> кластеров:
 +
 +
<math>TODO</math>
 +
 +
Данная функция отличается от простой суммы связей для каждого кластера, поскольку такая функция бы не давала уверенности в том, что точки, имеющие мало связей между собой распределялись бы по разным кластерам. Поэтому действительную сумму связей в кластере следует разделить на, так называемую, ожидаемую сумму связей. Функция <math>f(\theta)</math> задается пользователем и должна обладать следующим свойством: каждая точка, принадлежащая кластеру Ci, имеет приблизительно <math>TODO</math> соседей в этом кластере.

Версия 13:28, 15 октября 2016

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

В связи с наличием огромного количества накопленной информации задача добычи данных становится все более важной. Кластеризация позволяет распределять данные по группам (кластрерам) так, что в каждой группе данные обладают схожими характеристиками, а в разных группах характеристики различаются.

Алгоритм устойчивой кластеризации с использованием связей (robust clustering using links, ROCK)построен на основе понятия связей между кластеризуемыми точками и их соседства. Две точки считаются соседями, если являются достаточно близким (схожими): [math]sim({p_i}, {p_j}) \gt = \theta[/math], где [math]\theta[/math] - заданное пороговое значение в интервале от 0 до 1.

Связь [math]link({p_i}, {p_j})[/math] между двумя точками определяется как число общих соседей между точками [math]{p_i}[/math] и [math]{p_j}[/math]. Таким образом, чем большее значение функции связи для двух точек, тем более вероятно они принадлежат одному кластеру.

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

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

Итак, задача кластеризации сводиться к такому разбиению точек на кластеры, которое максимизирует сумму связей точек принадлежащих одному кластеру, и минимизирует эту функцию для точек из разных кластеров. Отсюда следует следующая целевая функция для разбияния на [math]k[/math] кластеров:

[math]TODO[/math]

Данная функция отличается от простой суммы связей для каждого кластера, поскольку такая функция бы не давала уверенности в том, что точки, имеющие мало связей между собой распределялись бы по разным кластерам. Поэтому действительную сумму связей в кластере следует разделить на, так называемую, ожидаемую сумму связей. Функция [math]f(\theta)[/math] задается пользователем и должна обладать следующим свойством: каждая точка, принадлежащая кластеру Ci, имеет приблизительно [math]TODO[/math] соседей в этом кластере.