Алгоритм устойчивой кластеризации с иcпользованием связей - История изменений

Viktorrulev: Полностью удалено содержимое страницы

2016-10-13T20:31:07Z

Полностью удалено содержимое страницы

← Предыдущая версия		Версия от 20:31, 13 октября 2016
Строка 1:		Строка 1:
	~~{{algorithm~~
	~~\| name = Алгоритм устойчивой кластеризации с иcпользованием связей~~
	~~\| serial_complexity = <math>...</math>~~
	~~\| pf_height = <math>...</math>~~
	~~\| pf_width = <math>...</math>~~
	~~\| input_data = <math>...</math>~~
	~~\| output_data = <math>...</math>~~
	}}

	~~Автор описания: [[Участник:viktorrulev\|В.А. Рулев]].~~

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

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

	Кластеризация (кластерный анализ) — задача разбиения заданной выборки объектов на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались. Каждый объект из выборки характеризуется рядом признаков, которые могут быть вещественными, целочисленными, категорийными (то есть принимающими значения из какого-либо множества) и другими. Множество значений, которые может принимать признак, называется доменом этого признака. Так, например, у объекта '''кошка''' может быть категорийный признак '''порода''', доменом которого является множество '''[персидская, бенгальская, сфинкс, мейн-кун, ...]'''.

	'''Алгоритм устойчивой кластеризации с иcпользованием связей (robust clustering using links, ROCK)''' был предложен в 2000 году Sudipto Guha (Stanford University), Rajeev Rastogi (Bell Laboratories) и Kyuseok Shim (Bell Laboratories) <ref>Sudipto Guha, Rajeev Rastogi, Kyuseok Shim ROCK: A robust clustering algorithm for categorical attributes. 2000. Information Systems. Vol 25, Issue 5, Pages 345-366</ref> для кластеризации объектов с категорийными признаками.

	Алгоритм устойчивой кластеризации с использованием связей предназначен для работы с объектами типа "транзакция" ("покупательская корзина"). Транзакция представляет собой множество товаров, приобретенных покупателем у поставщика. Каждому товару, который есть в наличии у поставщика, в транзакции соответствует отдельный признак, который принимает значение '''true''', если товар присутствует в транзакции, и '''false''', если товар в транзакции отсутствует.

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

	В ходе кластеризации все имеющиеся транзакции <math>P=\{p_1,...,p_M\}</math> должны быть разделены на <math>K</math> непересекающихся подмножеств (кластеров) <math>C_1, ..., C_K</math> таким образом, чтобы полученные кластеры максимизировали некоторую критериальную функцию <math>E(C_1, ..., C_K)</math>.

	Будет называть две транзакции <math>p_1</math> и <math>p_2</math> '''соседями''', если мера сходства этих транзакций больше некоторого заранее заданного порогового значения <math>\theta</math>, то есть

	~~<math>sim(p_1,p_2)<\theta</math>~~

	В качестве меры сходства в алгоритме устойчивой кластеризации с использованием связей используется основанная на коэффициенте Жаккара мера сходства

	~~<math>sim(p_1,p_2)=\frac{N(p_1 \cap p_2)}{N(p_1 \cup p_2)}</math>~~

	'''Количеством связей''' между двумя транзакциями будем называть количество общих соседей этих транзакций, то есть

	~~<math>link(p_1,p_2)=N \Big( \{ p \in P \| sim(p_1,p) < \theta \} \cap \{ p \in P \| sim(p_2,p) < \theta \} \Big)</math>~~

	~~В качестве критериальной функции используется функция вида~~

	~~<math>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>N(C_i)^{1+2f(\theta)}</math> имеет смысл ожидаемого (среднего) количества связей внутри одного кластера. Функция <math>f(\theta)</math> имеет вид

	~~<math>f(\theta)=\frac {1-\theta}{1+\theta}</math>~~

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

	~~тут что-то будет~~

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

	~~и тут~~

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

	~~и тут~~

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

	~~и тут~~

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

	~~и тут~~

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

	~~и тут~~

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

	~~и тут~~

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

	~~и тут~~

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

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

	~~и тут~~

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

	~~и тут~~

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

	~~и тут~~

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

	~~и тут~~

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

	~~и тут~~

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

	~~и тут~~

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

	~~нету :(~~

	~~== Литература ==~~

	~~<references \>~~

	~~[[Категория:Начатые статьи‏‎]]~~
	~~[[Категория:Алгоритмы кластеризации]]~~

Viktorrulev: /* Математическое описание алгоритма */

2016-10-11T21:46:41Z