Участник:Ilya365365/Алгоритм кластеризации категориальных данных - История изменений

Ilya365365: /* Свойства и структура алгоритма CLOPE */

2017-02-02T18:10:34Z

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

← Предыдущая версия		Версия от 18:10, 2 февраля 2017
Строка 75:		Строка 75:
	* size - количество объектов в транзакции		* size - количество объектов в транзакции
	* objects - массив с номерами объектов		* objects - массив с номерами объектов
	* id - уникальный номер транзакции		* id - уникальный номер транзакции. Равен 0, если транзакция не отнесена к какому-либо кластеру
			* cluster_id - номер кластера, в котором находится транзакция.
			Класс Transaction имеет метод add(Cluster)
			add(Cluster):
			cluster_id = Cluster.id;

	====Класс Cluster====		====Класс Cluster====
	Класс Cluster - структура данных, описывающая кластер. Содержит следующие поля:		Класс Cluster - структура данных, описывающая кластер. Содержит следующие поля:
Строка 84:		Строка 89:
	*power - число объектов в кластере		*power - число объектов в кластере
	*width - ширина кластера (число уникальных объектов)		*width - ширина кластера (число уникальных объектов)
	*profit_summand - вклад кластера в ~~функцию~~ profit		*profit_summand - вклад кластера в функционал profit
			*id - уникальный номер кластера
	Класс Cluster содержит следующие методы:		Класс Cluster содержит следующие методы:
	* calculate_profit_summand(power, width, transaction_quantity) вычисляет вклад кластера с заданными параметрами в ~~функцию profit~~		* calculate_profit_summand(power, width, transaction_quantity) вычисляет вклад кластера с заданными параметрами в функционал Profit
	calculate_profit_summand(power, width, transaction_quantity)		calculate_profit_summand(power, width, transaction_quantity)
	'''return''' power * transaction_quantity / width^self.repultion		'''return''' power * transaction_quantity / width^self.repultion;
	* ~~estimate_width_after_addition~~(transaction) - оценивает ~~ширину~~ кластера, после добавления транзакции ~~в кластер~~		* estimate_profit_summand_after_addition(transaction) - оценивает вклад кластера в функционал Profit после добавления транзакции
	~~estimate_width_after_addition~~(transaction)		estimate_profit_summand_after_addition(transaction)
	new_width = width;		new_width = width;
	'''for each''' object '''in''' transaction:		'''for each''' object '''in''' transaction:
	if (self.object_map.get(object) == NULL) new_width += 1;		if (self.object_map.get(object) == NULL):
	'''return''' ~~new_width~~;		new_width += 1;
			new_profit = calculate_profit_summand(self.power + transaction.size,
			new_width,
			transaction_quantity + 1);
			'''return''' new_profit;


	* ~~estimate_width_after_delition~~(transaction) - оценивает ~~ширину~~ кластера, после удаления транзакции ~~из кластера~~		* estimate_profit_summand_after_dellition(transaction) - оценивает вклад кластера в функционал Profit после удаления транзакции
	~~estimate_width_after_deliton~~(transaction)		estimate_profit_summand_after_dellition(transaction)
	new_width = width;		new_width = width;
	'''for each''' object '''in''' transaction:		'''for each''' object '''in''' transaction:
	~~'''~~if~~'''~~ (object_map.get(object) == 1):		if (self.object_map.get(object) == 1) new_width -= 1;
	new_width -= 1;		new_profit = calculate_profit_summand(self.power - transaction.size,
	'''return''' ~~new_width~~;		new_width,
			transaction_quantity - 1);
			'''return''' new_profit;
	* add_transaction(transaction) - добавление транзакции		* add_transaction(transaction) - добавление транзакции
	add_transaction(transaction)		add_transaction(transaction)
	self.transaction_map.push(transaction.id)		self.transaction_map.push(transaction.id);
	self.power += transaction.size		self.power += transaction.size;
	self.transaction_quantity += 1		self.transaction_quantity += 1;
	'''for each''' object '''in''' transaction.objects:		'''for each''' object '''in''' transaction.objects:
	'''if''' (self.object_map.get(object) == NULL):		'''if''' (self.object_map.get(object) == NULL):
Строка 117:		Строка 129:
	self.profit_summand = calculate_profit_summand(self.power,		self.profit_summand = calculate_profit_summand(self.power,
	self.width,		self.width,
	self.transaction_quantity)		self.transaction_quantity);
	* delete_transaction(transaction) - удаление транзакции		* delete_transaction(transaction) - удаление транзакции
	delete_transaction(transaction)		delete_transaction(transaction)
	self.transaction_map.pop(transaction.id)		self.transaction_map.pop(transaction.id);
	self.power -= transaction.size		self.power -= transaction.size;
	self.transaction_quantity -= 1		self.transaction_quantity -= 1;
	'''for each''' object '''in''' transaction.objects:		'''for each''' object '''in''' transaction.objects:
	'''if''' (self.object_map.get(object) == 1):		'''if''' (self.object_map.get(object) == 1):
Строка 131:		Строка 143:
	self.profit_summand = calculate_profit_summand(self.power,		self.profit_summand = calculate_profit_summand(self.power,
	self.width,		self.width,
	self.transaction_quantity)		self.transaction_quantity);
			Также класс Cluster содержит два конструктора:
			* Cluster(id) - конструктор, создающий пустой кластер.
			* Cluster(id, transaction) - конструктор, создающий кластер с единственной транзакцией.
			====Класс CLOPE====
			Класс CLOPE структура данных, обеспечивающая работу алгоритма. Класс CLOPE содержит следующие поля:
			* cluster_map - ассоциативный массив, содержащий информацию о кластерах. Ключ - номер кластера. Кластер с индексом 0 является пустым.
			* cluster_quantity - переменная, хранящая количество кластеров
			* sample_size - переменная хранящая, количество транзакций.
			В классе CLOPE необходимо реализовать следующие методы:
			* get_next_transaction() - получение следующей транзакции из файла. Если достигнут конец файла, считывается первая транзакция.
			*get_best_move(transaction) - найти кластер, в который следует переместить транзакцию
			get_best_move(transaction)
			'''if''' transaction.cluster_id != 0 : //транзакция лежит в кластере
			old_cluster = self.cluster_map[transaction.cluster_id];
			delete_change = old_cluster.profit_summand -
			old_cluster.estimate_profit_summand_after_dellition(transaction);
			else: //инициализация
			delete_change = 0;
	=== Схема реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===
	=== Информационный граф ===		=== Информационный граф ===
	=== Ресурс параллелизма ===		=== Ресурс параллелизма ===
	=== Входные и выходные данные ===		=== Входные и выходные данные ===

Ilya365365: /* Свойства и структура алгоритма CLOPE */

2017-02-02T17:30:09Z

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

@@ Строка 53: / Строка 53: @@
 '''Доказательство''': Рассмотрим некоторую кластеризацию <math>C</math> и кластеризацию <math>C^{new}</math>, полученную из  <math>C</math> перемещением <math>t</math> в кластер <math>C_i</math>.
 Тогда <math>Profit(C^{new}) - Profit(C) = \frac{Add(C_i, t, r) + Delete(C_l, t, r)}{M} </math>
-&nbsp;=&nbsp; <math>\frac{DeltaAdd(C_i, t, r)}{M}</math>
+&nbsp;=&nbsp; <math>\frac{DeltaAdd(C_i, t, r)}{M};</math>
 '''Следствие 1''': Алгоритм CLOPE сходится при любых <math>O</math>, <math>D</math> и <math>r</math>.
-'''Доказательство следствия 1''': Так как <math>DeltaAdd(C_l, t, r)</math> = 0 (<math>C_l</math> - кластер, к которому отнесена <math>t</math>), любое перемещение транзакции увеличивает <math>Profit(C)</math>, следовательно, алгоритм CLOPE сходится при любых <math>O</math>, <math>D</math> и <math>r</math>.
+'''Доказательство следствия 1''': Так как <math>DeltaAdd(C_l, t, r) = 0 </math>  (<math>C_l</math> - кластер, к которому отнесена <math>t</math>), любое перемещение транзакции увеличивает <math>Profit(C)</math>, следовательно, алгоритм CLOPE сходится при любых <math>O</math>, <math>D</math> и <math>r</math>.
 === Вычислительное ядро ===
 === Макроструктура алгоритма ===
 === Схема реализации последовательного алгоритма ===
 === Информационный граф ===
 === Ресурс параллелизма ===
 === Входные и выходные данные ===

Ilya365365: /* Свойства и структура алгоритма CLOPE */

2017-02-02T12:49:41Z

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

@@ Строка 15: / Строка 15: @@
 : {{ab, abc}, {acd, de, def}}.
-Для первого и второго вариантов разбиения в каждом кластере рассчитаем количество вхождений в него каждого элемента транзакции, а затем вычислим ширину <math>W(c_i)</math> (количество уникальных объектов кластера), общее число объектов в кластере <math>S(C_i)</math> и высоту <math>H(C_i) = \frac{S(C_i)}{W(C_i)^r}</math>, где <math>r</math> - коэффициент отталкивания. Чем больше <math>r</math>, тем больше кластеров будет сгенерировано.   Например, кластер {ab, abc, acd} имеет вхождения a:3, b:2, c:2, d:1 с H=2 и W=4, при r = 1.
+Для первого и второго вариантов разбиения в каждом кластере рассчитаем количество вхождений в него каждого элемента транзакции, а затем вычислим ширину <math>W(c_i)</math> (количество уникальных объектов кластера), общее число объектов в кластере <math>S(C_i)</math> и высоту <math>H(C_i) = \frac{S(C_i)}{W(C_i)}</math>.  Например, кластер {ab, abc, acd} имеет вхождения a:3, b:2, c:2, d:1 с H=2 и W=4.
 [[Файл:Clope split.png|border|Гистограммы разбиений]]
-Лучшим признаётся разбиение, при котором достигается максимум функции <math> Profit(C)=\frac{\sum^{k}_{i=1} H(C_i) \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} </math> &nbsp;=&nbsp; <math>\frac{\sum^{k}_{i=1} \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid} {M} </math>
+Очевидно, что чем меньше ширина и чем больше высота кластера, тем больше сходство в ходящих в него транзакций. Авторы алгоритма формализовали эту идею, введя следующий функционал: <math> Profit(C)=\frac{\sum^{k}_{i=1} G(C_i) \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} </math> &nbsp;=&nbsp; <math>\frac{\sum^{k}_{i=1} \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid} {M} </math>
-Здесь <math>k</math> - количество кластеров, <math>C_i</math>, <math>\mid C_i \mid</math> - число транзакций в кластере <math> C_i </math>, M - число транзакций в выборке.
+Здесь <math>k</math> - количество кластеров, <math>C_i</math>, <math>\mid C_i \mid</math> - число транзакций в кластере <math> C_i </math>, M - число транзакций в выборке, <math>G(C_i) = \frac{S(C_i)}{W^r(C_i)}</math>, <math>r</math> - коэффициент отталкивания. Чем больше <math>r</math>, тем больше кластеров будет сгенерировано.
 === Математическое описание алгоритма CLOPE ===
 === Вычислительное ядро ===
 === Макроструктура алгоритма ===

Ilya365365 в 18:00, 31 января 2017

2017-01-31T18:00:54Z

← Предыдущая версия		Версия от 18:00, 31 января 2017
Строка 19:		Строка 19:
	[[Файл:Clope split.png\|border\|Гистограммы разбиений]]		[[Файл:Clope split.png\|border\|Гистограммы разбиений]]

	Лучшим признаётся разбиение, при котором достигается максимум функции <math> Profit(C)=\frac{\sum^{k}_{i=1} H(C_i) \times \mid C_i \mid} {M} </math>  =  <math>\frac{\sum^{k}_{i=1} \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid} {~~\sum^{k}_{i=1} \mid C_i \mid~~} </math>		Лучшим признаётся разбиение, при котором достигается максимум функции <math> Profit(C)=\frac{\sum^{k}_{i=1} H(C_i) \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} </math>  =  <math>\frac{\sum^{k}_{i=1} \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid} {M} </math>

Ilya365365 в 17:59, 31 января 2017

2017-01-31T17:59:08Z

← Предыдущая версия		Версия от 17:59, 31 января 2017
Строка 16:		Строка 16:

	Для первого и второго вариантов разбиения в каждом кластере рассчитаем количество вхождений в него каждого элемента транзакции, а затем вычислим ширину <math>W(c_i)</math> (количество уникальных объектов кластера), общее число объектов в кластере <math>S(C_i)</math> и высоту <math>H(C_i) = \frac{S(C_i)}{W(C_i)^r}</math>, где <math>r</math> - коэффициент отталкивания. Чем больше <math>r</math>, тем больше кластеров будет сгенерировано. Например, кластер {ab, abc, acd} имеет вхождения a:3, b:2, c:2, d:1 с H=2 и W=4, при r = 1.		Для первого и второго вариантов разбиения в каждом кластере рассчитаем количество вхождений в него каждого элемента транзакции, а затем вычислим ширину <math>W(c_i)</math> (количество уникальных объектов кластера), общее число объектов в кластере <math>S(C_i)</math> и высоту <math>H(C_i) = \frac{S(C_i)}{W(C_i)^r}</math>, где <math>r</math> - коэффициент отталкивания. Чем больше <math>r</math>, тем больше кластеров будет сгенерировано. Например, кластер {ab, abc, acd} имеет вхождения a:3, b:2, c:2, d:1 с H=2 и W=4, при r = 1.

	[[Файл:Clope split.png\|border\|Гистограммы разбиений]]		[[Файл:Clope split.png\|border\|Гистограммы разбиений]]

	Лучшим признаётся разбиение, при котором достигается максимум функции <math> Profit(C)=\frac{\sum^{k}_{i=1} H(C_i) \times \mid C_i \mid} {~~\sum^{k}_{i=1} \mid C_i \mid~~} </math>  =  <math>\frac{\sum^{k}_{i=1} \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} </math>		Лучшим признаётся разбиение, при котором достигается максимум функции <math> Profit(C)=\frac{\sum^{k}_{i=1} H(C_i) \times \mid C_i \mid} {M} </math>  =  <math>\frac{\sum^{k}_{i=1} \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} </math>


	Здесь <math>k</math> - количество кластеров, <math>C_i</math>, <math>\mid C_i \mid</math> - число транзакций в кластере <math> C_i </math>.		Здесь <math>k</math> - количество кластеров, <math>C_i</math>, <math>\mid C_i \mid</math> - число транзакций в кластере <math> C_i </math>, M - число транзакций в выборке.
	=== Математическое описание алгоритма CLOPE ===		=== Математическое описание алгоритма CLOPE ===

Ilya365365: /* Свойства и структура алгоритма CLOPE */

2017-01-31T17:55:39Z

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

← Предыдущая версия		Версия от 17:55, 31 января 2017
Строка 3:		Строка 3:


	Алгоритм CLOPE решает задачу кластеризации категориальных данных. ~~Здесь и далее под категориальными данными понимаются качественные характеристики объектов~~, ~~измеренные в шкале наименований~~, ~~то есть при сравнении категориальных данных указывается только~~, ~~одинаковы или нет объекты относительно данного признака~~.		Алгоритм CLOPE решает задачу кластеризации категориальных транзакционных данных. Алгоритм основан на эвристическом методе повышения близости транзакций в кластерах при помощи оптимизации параметров кластерной гистограммы. Авторы (Yiling Yang Xudong Guan Jinyuan You )<ref>Y. Yang, X. Guan J. You. CLOPE: A Fast and Effective Clustering Algorithm for Transactional Data. http://www.inf.ufrgs.br/~alvares/CMP259DCBD/clope.pdf</ref> предложили эффективный, масштабируемый алгоритм, не требующий хранения обучающей выборки в оперативной памяти.

	~~Алгоритм CLOPE работает с транзакциями. Под термином транзакция понимается произвольный набор~~ объектов, ~~например, список ключевых слов статьи, товары, купленные~~ в ~~супермаркете, множество симптомов пациента~~, ~~характерные фрагменты изображения и так далее. Задача кластеризации транзакционных~~ данных состоит в получении такого разбиения всего множества транзакций, чтобы похожие транзакции оказались в одном кластере, ~~а отличающиеся друг от друга – в разных кластерах~~.		Здесь и далее под категориальными данными понимаются качественные характеристики объектов, измеренные в шкале наименований, то есть при сравнении категориальных данных указывается только, одинаковы или нет объекты относительно данного признака.

	В основе алгоритма кластеризации CLOPE лежит идея максимизации глобальной функции стоимости, которая повышает близость транзакций в кластерах при помощи увеличения параметра кластерной гистограммы.Для примера рассмотрим выборку из пяти списков покупок: {(apple, banana), (apple, banana, cake), (apple, cake, dish), (dish, egg), (dish, egg, fish)}, или сокращённо {ab, abc, acd, de, def}. Каждый список - транзакция. Каждый купленный предмет является объектом. Представим себе, что мы хотим сравнить между собой следующие два разбиения на кластеры:		Под термином транзакция понимается произвольный набор объектов, например, список ключевых слов статьи, товары, купленные в супермаркете, множество симптомов пациента, характерные фрагменты изображения и так далее. Задача кластеризации транзакционных данных состоит в получении такого разбиения всего множества транзакций, чтобы похожие транзакции оказались в одном кластере, а отличающиеся друг от друга – в разных кластерах.

			В основе алгоритма кластеризации CLOPE лежит идея максимизации глобальной функции стоимости, которая повышает близость транзакций в кластерах при помощи увеличения параметра кластерной гистограммы. Для примера рассмотрим выборку из пяти списков покупок: {(apple, banana), (apple, banana, cake), (apple, cake, dish), (dish, egg), (dish, egg, fish)}, или сокращённо {ab, abc, acd, de, def}. Каждый список - транзакция. Каждый купленный предмет является объектом. Представим себе, что мы хотим сравнить между собой следующие два разбиения на кластеры:

	1: {{ab, abc, acd}, {de, def}}		1: {{ab, abc, acd}, {de, def}}
Строка 13:		Строка 15:
	2: {{ab, abc}, {acd, de, def}}.		2: {{ab, abc}, {acd, de, def}}.

	Для первого и второго вариантов разбиения в каждом кластере рассчитаем количество вхождений в него каждого элемента транзакции, а затем вычислим ширину W (количество уникальных объектов кластера) и высоту H (~~отношение общего числа объектов и ширины~~). Например, кластер {ab, abc, acd} имеет вхождения a:3, b:2, c:2, d:1 с H=2 и W=4.		Для первого и второго вариантов разбиения в каждом кластере рассчитаем количество вхождений в него каждого элемента транзакции, а затем вычислим ширину <math>W(c_i)</math> (количество уникальных объектов кластера), общее число объектов в кластере <math>S(C_i)</math> и высоту <math>H(C_i) = \frac{S(C_i)}{W(C_i)^r}</math>, где <math>r</math> - коэффициент отталкивания. Чем больше <math>r</math>, тем больше кластеров будет сгенерировано. Например, кластер {ab, abc, acd} имеет вхождения a:3, b:2, c:2, d:1 с H=2 и W=4, при r = 1.
	[[Файл:Clope split.png\|border\|Гистограммы разбиений]]		[[Файл:Clope split.png\|border\|Гистограммы разбиений]]

	Лучшим признаётся разбиение, при котором достигается ~~минимум~~ функции <math> Profit(C)=\frac{\sum^{k}_{i=1} H(C_i) \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} </math>  =  <math>\frac{\sum^{k}_{i=1} \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} </math>		Лучшим признаётся разбиение, при котором достигается максимум функции <math> Profit(C)=\frac{\sum^{k}_{i=1} H(C_i) \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} </math>  =  <math>\frac{\sum^{k}_{i=1} \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} </math>
	Здесь ~~<math>r</math> - коэффициент отталкивания,~~ <math>k</math> - количество кластеров, ~~<math>S(C_i)</math> - число объектов в кластере~~ <math>C_i</math>, <math>\mid C_i \mid</math> - число транзакций в кластере <math> C_i </math>~~, <math>H(C_i)</math> и <math>W(c_i)</math> - высота и ширина <math>C_i</math> соответственно~~.

			Здесь <math>k</math> - количество кластеров, <math>C_i</math>, <math>\mid C_i \mid</math> - число транзакций в кластере <math> C_i </math>.
	=== Математическое описание алгоритма CLOPE ===		=== Математическое описание алгоритма CLOPE ===

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

Ilya365365: /* Свойства и структура алгоритма CLOPE */

2017-01-31T17:14:08Z

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

← Предыдущая версия		Версия от 17:14, 31 января 2017
Строка 1:		Строка 1:
	== Свойства и структура алгоритма CLOPE ==		== Свойства и структура алгоритма CLOPE ==
	=== Общее описание алгоритма CLOPE ===		=== Общее описание алгоритма CLOPE ===


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

Строка 14:		Строка 16:
	[[Файл:Clope split.png\|border\|Гистограммы разбиений]]		[[Файл:Clope split.png\|border\|Гистограммы разбиений]]

	Лучшим признаётся разбиение, ~~у которого сумма~~ H/W, ~~взвешенная с количеством~~ транзакций в ~~каждом~~ кластере, ~~минимальна~~.		Лучшим признаётся разбиение, при котором достигается минимум функции <math> Profit(C)=\frac{\sum^{k}_{i=1} H(C_i) \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} </math>  =  <math>\frac{\sum^{k}_{i=1} \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} </math>
			Здесь <math>r</math> - коэффициент отталкивания, <math>k</math> - количество кластеров, <math>S(C_i)</math> - число объектов в кластере <math>C_i</math>, <math>\mid C_i \mid</math> - число транзакций в кластере <math> C_i </math>, <math>H(C_i)</math> и <math>W(c_i)</math> - высота и ширина <math>C_i</math> соответственно.
	=== Математическое описание алгоритма CLOPE ===		=== Математическое описание алгоритма CLOPE ===
	=== Вычислительное ядро ===		=== Вычислительное ядро ===

Ilya365365 в 06:47, 20 января 2017

2017-01-20T06:47:11Z

← Предыдущая версия		Версия от 06:47, 20 января 2017
Строка 14:		Строка 14:
	[[Файл:Clope split.png\|border\|Гистограммы разбиений]]		[[Файл:Clope split.png\|border\|Гистограммы разбиений]]

	Лучшим признаётся разбиение, у которого		Лучшим признаётся разбиение, у которого сумма H/W, взвешенная с количеством транзакций в каждом кластере, минимальна.
	=== Математическое описание алгоритма CLOPE ===		=== Математическое описание алгоритма CLOPE ===
	=== Вычислительное ядро ===		=== Вычислительное ядро ===

Ilya365365: Новая страница: «== Свойства и структура алгоритма CLOPE == === Общее описание алгоритма CLOPE === Алгоритм CLOPE реша…»

2017-01-20T06:34:17Z

Новая страница: «== Свойства и структура алгоритма CLOPE == === Общее описание алгоритма CLOPE === Алгоритм CLOPE реша…»

Новая страница

== Свойства и структура алгоритма CLOPE ==
=== Общее описание алгоритма CLOPE ===
Алгоритм CLOPE решает задачу кластеризации категориальных данных. Здесь и далее под категориальными данными понимаются качественные характеристики объектов, измеренные в шкале наименований, то есть при сравнении категориальных данных указывается только, одинаковы или нет объекты относительно данного признака.

Алгоритм CLOPE работает с транзакциями. Под термином транзакция понимается произвольный набор объектов, например, список ключевых слов статьи, товары, купленные в супермаркете, множество симптомов пациента, характерные фрагменты изображения и так далее. Задача кластеризации транзакционных данных состоит в получении такого разбиения всего множества транзакций, чтобы похожие транзакции оказались в одном кластере, а отличающиеся друг от друга – в разных кластерах.

В основе алгоритма кластеризации CLOPE лежит идея максимизации глобальной функции стоимости, которая повышает близость транзакций в кластерах при помощи увеличения параметра кластерной гистограммы.Для примера рассмотрим выборку из пяти списков покупок: {(apple, banana), (apple, banana, cake), (apple, cake, dish), (dish, egg), (dish, egg, fish)}, или сокращённо {ab, abc, acd, de, def}. Каждый список - транзакция. Каждый купленный предмет является объектом. Представим себе, что мы хотим сравнить между собой следующие два разбиения на кластеры:

1: {{ab, abc, acd}, {de, def}}

2: {{ab, abc}, {acd, de, def}}.

Для первого и второго вариантов разбиения в каждом кластере рассчитаем количество вхождений в него каждого элемента транзакции, а затем вычислим ширину W (количество уникальных объектов кластера) и высоту H (отношение общего числа объектов и ширины). Например, кластер {ab, abc, acd} имеет вхождения a:3, b:2, c:2, d:1 с H=2 и W=4.
[[Файл:Clope split.png|border|Гистограммы разбиений]]

Лучшим признаётся разбиение, у которого
=== Математическое описание алгоритма CLOPE ===
=== Вычислительное ядро ===
=== Макроструктура алгоритма ===
=== Схема реализации последовательного алгоритма ===
=== Информационный граф ===
=== Ресурс параллелизма ===
=== Входные и выходные данные ===