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

Артем Желтков в 19:21, 9 февраля 2017

2017-02-09T19:21:25Z

← Предыдущая версия		Версия от 19:21, 9 февраля 2017
Строка 285:		Строка 285:
	** Алгоритм предназначен для обработки категориальных данных, а значит практически неприменим к обработке наборов числовых данных. Данный метод «не понимает», что, например, числа 3 и 4 являются близкими по значению, а числа 3 и 100 — нет. В ходе алгоритма они будут просто интерпретироваться, как разные категории.		** Алгоритм предназначен для обработки категориальных данных, а значит практически неприменим к обработке наборов числовых данных. Данный метод «не понимает», что, например, числа 3 и 4 являются близкими по значению, а числа 3 и 100 — нет. В ходе алгоритма они будут просто интерпретироваться, как разные категории.
	** Алгоритм достаточно прост в реализации и имеет высокую скорость работы, а также качество кластеризации.		** Алгоритм достаточно прост в реализации и имеет высокую скорость работы, а также качество кластеризации.
	** Во время работы алгоритма в оперативной памяти хранится относительно небольшое количество информации по каждому кластеру и требуется минимальное число сканирований набора транзакций. Это позволяет применять его для кластеризации больших объемов категориальных данных <ref>Н. Паклин. «Кластеризация категорийных данных: масштабируемый алгоритм CLOPE». Электронное издание. ~~http~~://~~www.~~basegroup.ru/~~clusterization~~/clope~~.htm~~ </ref>		** Во время работы алгоритма в оперативной памяти хранится относительно небольшое количество информации по каждому кластеру и требуется минимальное число сканирований набора транзакций. Это позволяет применять его для кластеризации больших объемов категориальных данных <ref>Н. Паклин. «Кластеризация категорийных данных: масштабируемый алгоритм CLOPE». Электронное издание. https://basegroup.ru/community/articles/clope </ref>
	** Требования к памяти главным образом зависят от количества различных категорий в базе транзакций.		** Требования к памяти главным образом зависят от количества различных категорий в базе транзакций.
	** Количество кластеров зависит от параметра — коэффициента отталкивания — и подбирается автоматически. Это означает, что хоть количество кластеров и регулируется пользователем при помощи данного коэффициента, нельзя априорно получить число кластеров, которое будет в итоге создано, а значит, нельзя точно предсказать сложность алгоритма и объем выходных данных (т.к. они зависят от количества кластеров).		** Количество кластеров зависит от параметра — коэффициента отталкивания — и подбирается автоматически. Это означает, что хоть количество кластеров и регулируется пользователем при помощи данного коэффициента, нельзя априорно получить число кластеров, которое будет в итоге создано, а значит, нельзя точно предсказать сложность алгоритма и объем выходных данных (т.к. они зависят от количества кластеров).

Артем Желтков: /* Ресурс параллелизма алгоритма */

2017-01-31T00:12:41Z

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

← Предыдущая версия		Версия от 00:12, 31 января 2017
Строка 252:		Строка 252:
	То есть, для <math>i</math>-ой транзакции вычисление обобщенной цены добавления на <math>j</math>-й кластер никак не зависит от вычисления обобщенной цены добавления этой же транзакции на <math>k</math>-й кластер. Поэтому эти операции при обработке текущей транзакции <math>t_i</math> можно выполнять одновременно.		То есть, для <math>i</math>-ой транзакции вычисление обобщенной цены добавления на <math>j</math>-й кластер никак не зависит от вычисления обобщенной цены добавления этой же транзакции на <math>k</math>-й кластер. Поэтому эти операции при обработке текущей транзакции <math>t_i</math> можно выполнять одновременно.

	Однако при этом важно отметить, что обработка всех транзакций на каждой итерации алгоритма (инициализирующей или уточняющей) должна выполняться строго последовательно — вычисления обобщенных стоимостей добавления транзакции <math>t_{i+1}</math> на существующие кластеры могут быть начаты только после завершения обработки транзакции <math>t_i</math> — т.е. после вычислений всех ее обобщенных стоимостей добавления на каждый из кластеров (стоимости ее удаления с текущего кластера (если итерация алгоритма — уточняющая) и стоимостей добавления на каждый из остальных кластеров) и возможного выполнения перемещения транзакции на новый кластер — потому как обобщенные стоимости добавления транзакции <math>t_{i+1}</math> на кластеры информационно зависят от результата распределения транзакции <math>t_i</math> на текущей итерации алгоритма.		Однако при этом важно отметить, что для корректного распараллеливания (чтобы результат выполнения параллельной программы был эквивалентен результату последовательной) обработка всех транзакций на каждой итерации алгоритма (инициализирующей или уточняющей) должна выполняться строго последовательно — вычисления обобщенных стоимостей добавления транзакции <math>t_{i+1}</math> на существующие кластеры могут быть начаты только после завершения обработки транзакции <math>t_i</math> — т.е. после вычислений всех ее обобщенных стоимостей добавления на каждый из кластеров (стоимости ее удаления с текущего кластера (если итерация алгоритма — уточняющая) и стоимостей добавления на каждый из остальных кластеров) и возможного выполнения перемещения транзакции на новый кластер — потому как обобщенные стоимости добавления транзакции <math>t_{i+1}</math> на кластеры информационно зависят от результата распределения транзакции <math>t_i</math> на текущей итерации алгоритма.

	Таким образом, полагая, что количество вычислительных элементов не ограничено и всегда превышает количество кластеров <math>k</math>, существующих на любой из итераций алгоритма, можно считать, что обработка '''одной''' транзакции на каждой итерации алгоритма выполняется за <math>O(A)</math> операций (это соответствует сложности однократного вычисления <math>Cost^{\pm}(C_j, t_i) </math> — данная оценка приводится в разделе [[#Последовательная сложность алгоритма\|Последовательная сложность алгоритма]]), где <math>A</math> — максимальная длина транзакции.		Таким образом, полагая, что количество вычислительных элементов не ограничено и всегда превышает количество кластеров <math>k</math>, существующих на любой из итераций алгоритма, можно считать, что обработка '''одной''' транзакции на каждой итерации алгоритма выполняется за <math>O(A)</math> операций (это соответствует сложности однократного вычисления <math>Cost^{\pm}(C_j, t_i) </math> — данная оценка приводится в разделе [[#Последовательная сложность алгоритма\|Последовательная сложность алгоритма]]), где <math>A</math> — максимальная длина транзакции.

Артем Желтков: /* Ресурс параллелизма алгоритма */

2017-01-31T00:05:34Z

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

← Предыдущая версия		Версия от 00:05, 31 января 2017
Строка 256:		Строка 256:
	Таким образом, полагая, что количество вычислительных элементов не ограничено и всегда превышает количество кластеров <math>k</math>, существующих на любой из итераций алгоритма, можно считать, что обработка '''одной''' транзакции на каждой итерации алгоритма выполняется за <math>O(A)</math> операций (это соответствует сложности однократного вычисления <math>Cost^{\pm}(C_j, t_i) </math> — данная оценка приводится в разделе [[#Последовательная сложность алгоритма\|Последовательная сложность алгоритма]]), где <math>A</math> — максимальная длина транзакции.		Таким образом, полагая, что количество вычислительных элементов не ограничено и всегда превышает количество кластеров <math>k</math>, существующих на любой из итераций алгоритма, можно считать, что обработка '''одной''' транзакции на каждой итерации алгоритма выполняется за <math>O(A)</math> операций (это соответствует сложности однократного вычисления <math>Cost^{\pm}(C_j, t_i) </math> — данная оценка приводится в разделе [[#Последовательная сложность алгоритма\|Последовательная сложность алгоритма]]), где <math>A</math> — максимальная длина транзакции.

	С учетом требования к последовательной обработке транзакций на каждой итерации алгоритма приходим к выводу, что сложность параллельного алгоритма будет равна <math>O(N*A)</math> (<math>N</math> — количество транзакций).		С учетом требования к последовательной обработке транзакций на каждой итерации алгоритма приходим к выводу, что сложность параллельного алгоритма будет равна <math>O(N*A)</math> (здесь <math>N</math> — количество транзакций).

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

Артем Желтков: /* Ресурс параллелизма алгоритма */

2017-01-31T00:04:59Z

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

← Предыдущая версия		Версия от 00:04, 31 января 2017
Строка 252:		Строка 252:
	То есть, для <math>i</math>-ой транзакции вычисление обобщенной цены добавления на <math>j</math>-й кластер никак не зависит от вычисления обобщенной цены добавления этой же транзакции на <math>k</math>-й кластер. Поэтому эти операции при обработке текущей транзакции <math>t_i</math> можно выполнять одновременно.		То есть, для <math>i</math>-ой транзакции вычисление обобщенной цены добавления на <math>j</math>-й кластер никак не зависит от вычисления обобщенной цены добавления этой же транзакции на <math>k</math>-й кластер. Поэтому эти операции при обработке текущей транзакции <math>t_i</math> можно выполнять одновременно.

	Однако при этом важно отметить, что обработка всех транзакций на каждой итерации алгоритма (инициализирующей или уточняющей) должна выполняться строго последовательно — вычисления обобщенных стоимостей добавления транзакции <math>t_{i+1}</math> на существующие кластеры могут быть начаты только после завершения обработки транзакции <math>t_i</math> — т.е. после вычислений всех ее обобщенных стоимостей добавления на каждый из кластеров (стоимости ее удаления с текущего кластера (если итерация алгоритма — уточняющая) и стоимостей добавления на каждый из остальных кластеров) и возможного выполнения перемещения транзакции на новый кластер — потому как обобщенные стоимости добавления транзакции <math>t_{i+1}</math> информационно зависят от результата распределения транзакции <math>t_i</math> на текущей итерации алгоритма.		Однако при этом важно отметить, что обработка всех транзакций на каждой итерации алгоритма (инициализирующей или уточняющей) должна выполняться строго последовательно — вычисления обобщенных стоимостей добавления транзакции <math>t_{i+1}</math> на существующие кластеры могут быть начаты только после завершения обработки транзакции <math>t_i</math> — т.е. после вычислений всех ее обобщенных стоимостей добавления на каждый из кластеров (стоимости ее удаления с текущего кластера (если итерация алгоритма — уточняющая) и стоимостей добавления на каждый из остальных кластеров) и возможного выполнения перемещения транзакции на новый кластер — потому как обобщенные стоимости добавления транзакции <math>t_{i+1}</math> на кластеры информационно зависят от результата распределения транзакции <math>t_i</math> на текущей итерации алгоритма.

	Таким образом, полагая, что количество вычислительных элементов не ограничено и всегда превышает количество кластеров <math>k</math>, существующих на любой из итераций алгоритма, можно считать, что обработка '''одной''' транзакции на каждой итерации алгоритма выполняется за <math>O(A)</math> операций (это соответствует сложности однократного вычисления <math>Cost^{\pm}(C_j, t_i) </math> — данная оценка приводится в разделе [[#Последовательная сложность алгоритма\|Последовательная сложность алгоритма]]), где <math>A</math> — максимальная длина транзакции.		Таким образом, полагая, что количество вычислительных элементов не ограничено и всегда превышает количество кластеров <math>k</math>, существующих на любой из итераций алгоритма, можно считать, что обработка '''одной''' транзакции на каждой итерации алгоритма выполняется за <math>O(A)</math> операций (это соответствует сложности однократного вычисления <math>Cost^{\pm}(C_j, t_i) </math> — данная оценка приводится в разделе [[#Последовательная сложность алгоритма\|Последовательная сложность алгоритма]]), где <math>A</math> — максимальная длина транзакции.

Артем Желтков: /* Ресурс параллелизма алгоритма */

2017-01-31T00:02:45Z

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

← Предыдущая версия		Версия от 00:02, 31 января 2017
Строка 248:		Строка 248:
	Для алгоритма CLOPE кластеризации категориальных данных имеет место '''конечный''' параллелизм.		Для алгоритма CLOPE кластеризации категориальных данных имеет место '''конечный''' параллелизм.

	В рамках каждой итерации алгоритма (инициализирующей или уточняющей) можно выделить информационно-независимый фрагмент - вычисление обобщенной стоимости добавления текущей обрабатываемой транзакции на каждый из уже существующих кластеров — <math>Cost^{\pm}(C_j, t_i) </math>, при фиксированном значении <math>i</math>.		В рамках каждой итерации алгоритма (инициализирующей или уточняющей) можно выделить информационно-независимый фрагмент — вычисление обобщенной стоимости добавления текущей обрабатываемой транзакции на каждый из уже существующих кластеров — <math>Cost^{\pm}(C_j, t_i) </math>, при фиксированном значении <math>i</math>.

	То есть, для <math>i</math>-ой транзакции вычисление обобщенной цены добавления на <math>j</math>-й кластер никак не зависит от вычисления обобщенной цены добавления этой же транзакции на <math>k</math>-й кластер. Поэтому эти операции при обработке текущей транзакции <math>t_i</math> можно выполнять одновременно.		То есть, для <math>i</math>-ой транзакции вычисление обобщенной цены добавления на <math>j</math>-й кластер никак не зависит от вычисления обобщенной цены добавления этой же транзакции на <math>k</math>-й кластер. Поэтому эти операции при обработке текущей транзакции <math>t_i</math> можно выполнять одновременно.

	Однако при этом важно отметить, что обработка всех транзакций на каждой итерации алгоритма (инициализирующей или уточняющей) должна выполняться строго последовательно - вычисления обобщенных стоимостей добавления транзакции <math>t_{i+1}</math> на существующие кластеры могут быть начаты только после завершения обработки транзакции <math>t_i</math> — т.е. после вычислений всех ее обобщенных стоимостей добавления на каждый из кластеров (стоимости ее удаления с текущего кластера (если итерация алгоритма - уточняющая) и стоимостей добавления на каждый из остальных кластеров) и возможного выполнения перемещения транзакции на новый кластер — потому как обобщенные стоимости добавления транзакции <math>t_{i+1}</math> информационно зависят от результата распределения транзакции <math>t_i</math> на текущей итерации алгоритма.		Однако при этом важно отметить, что обработка всех транзакций на каждой итерации алгоритма (инициализирующей или уточняющей) должна выполняться строго последовательно — вычисления обобщенных стоимостей добавления транзакции <math>t_{i+1}</math> на существующие кластеры могут быть начаты только после завершения обработки транзакции <math>t_i</math> — т.е. после вычислений всех ее обобщенных стоимостей добавления на каждый из кластеров (стоимости ее удаления с текущего кластера (если итерация алгоритма — уточняющая) и стоимостей добавления на каждый из остальных кластеров) и возможного выполнения перемещения транзакции на новый кластер — потому как обобщенные стоимости добавления транзакции <math>t_{i+1}</math> информационно зависят от результата распределения транзакции <math>t_i</math> на текущей итерации алгоритма.

	Таким образом, полагая, что количество вычислительных элементов не ограничено и всегда превышает количество кластеров <math>k</math>, существующих на любой из итераций алгоритма, можно считать, что обработка '''одной''' транзакции на каждой итерации алгоритма выполняется за <math>O(A)</math> операций (это соответствует сложности однократного вычисления <math>Cost^{\pm}(C_j, t_i) </math> - данная оценка ~~описана~~ в разделе [[#Последовательная сложность алгоритма\|Последовательная сложность алгоритма]]), где <math>A</math> — максимальная длина транзакции.		Таким образом, полагая, что количество вычислительных элементов не ограничено и всегда превышает количество кластеров <math>k</math>, существующих на любой из итераций алгоритма, можно считать, что обработка '''одной''' транзакции на каждой итерации алгоритма выполняется за <math>O(A)</math> операций (это соответствует сложности однократного вычисления <math>Cost^{\pm}(C_j, t_i) </math> — данная оценка приводится в разделе [[#Последовательная сложность алгоритма\|Последовательная сложность алгоритма]]), где <math>A</math> — максимальная длина транзакции.

	С учетом требования к последовательной обработке транзакций на каждой итерации алгоритма приходим к выводу, что сложность параллельного алгоритма будет равна <math>O(N*A)</math> (<math>N</math> — количество транзакций).		С учетом требования к последовательной обработке транзакций на каждой итерации алгоритма приходим к выводу, что сложность параллельного алгоритма будет равна <math>O(N*A)</math> (<math>N</math> — количество транзакций).

Артем Желтков: /* Ресурс параллелизма алгоритма */

2017-01-31T00:00:46Z

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

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

	Для удобства будем рассматривать одну операцию вычисления стоимости удаления транзакции с текущего кластера <math>Cost^{-}(C_{C(t_i)}, t_i) </math> совместно с операциями вычисления стоимости добавления транзакции на остальные кластеры <math>Cost^{+}(C_j, t_i) </math> — таким образом, на каждой итерации алгоритма для каждой транзакции должно производиться по одному выполнению такой обобщенной операции <math>Cost^{\pm}(C_j, t_i) </math> вычисления стоимости добавления/удаления на каждый из существующих кластеров.		Для удобства будем рассматривать одну операцию вычисления стоимости удаления транзакции с текущего кластера <math>Cost^{-}(C_{C(t_i)}, t_i) </math> совместно с операциями вычисления стоимости добавления транзакции на остальные кластеры <math>Cost^{+}(C_j, t_i) </math> — таким образом, на каждой итерации алгоритма для каждой транзакции должно производиться по одному выполнению такой обобщенной операции <math>Cost^{\pm}(C_j, t_i) </math> вычисления стоимости добавления/удаления на каждый из существующих кластеров.
	Поэтому в данном разделе условимся, что под выражением "'''обобщенная''' стоимость (цена) добавления <math>Cost^{\pm}(C_j, t_i) </math> транзакции <math>t_i</math> на кластер <math>C_j</math>" подразумевается непосредственно стоимость добавления <math>Cost^{+}(C_j, t_i) </math> транзакции <math>t_i</math> на кластер <math>C_j</math>, если транзакция <math>t_i</math> в данный момент '''не находится''' на кластере <math>C_j</math>, а если транзакция <math>t_i</math> ~~'''находится''' на кластере~~ <math>C_j</math> — то стоимость ее удаления ~~с данного кластера~~ <math>Cost^{-}(C_j, t_i) </math>.		Поэтому в данном разделе условимся, что под выражением "'''обобщенная''' стоимость (цена) добавления <math>Cost^{\pm}(C_j, t_i) </math> транзакции <math>t_i</math> на кластер <math>C_j</math>" подразумевается непосредственно стоимость добавления <math>Cost^{+}(C_j, t_i) </math> транзакции <math>t_i</math> на кластер <math>C_j</math>, если транзакция <math>t_i</math> в данный момент '''не находится''' на кластере <math>C_j</math>, а иначе, если транзакция <math>t_i</math> принадлежит кластеру <math>C_j</math> — то стоимость ее удаления <math>Cost^{-}(C_j, t_i) </math> с данного кластера.

Артем Желтков: /* Ресурс параллелизма алгоритма */

2017-01-30T23:59:15Z

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

← Предыдущая версия		Версия от 23:59, 30 января 2017
Строка 243:		Строка 243:

	Для удобства будем рассматривать одну операцию вычисления стоимости удаления транзакции с текущего кластера <math>Cost^{-}(C_{C(t_i)}, t_i) </math> совместно с операциями вычисления стоимости добавления транзакции на остальные кластеры <math>Cost^{+}(C_j, t_i) </math> — таким образом, на каждой итерации алгоритма для каждой транзакции должно производиться по одному выполнению такой обобщенной операции <math>Cost^{\pm}(C_j, t_i) </math> вычисления стоимости добавления/удаления на каждый из существующих кластеров.		Для удобства будем рассматривать одну операцию вычисления стоимости удаления транзакции с текущего кластера <math>Cost^{-}(C_{C(t_i)}, t_i) </math> совместно с операциями вычисления стоимости добавления транзакции на остальные кластеры <math>Cost^{+}(C_j, t_i) </math> — таким образом, на каждой итерации алгоритма для каждой транзакции должно производиться по одному выполнению такой обобщенной операции <math>Cost^{\pm}(C_j, t_i) </math> вычисления стоимости добавления/удаления на каждый из существующих кластеров.
	Поэтому в данном разделе условимся, что под выражением "'''обобщенная''' стоимость (цена) добавления <math>Cost^{\pm}(C_j, t_i) </math> транзакции <math>t_i</math> на кластер <math>C_j</math>" подразумевается непосредственно стоимость добавления <math>Cost^{+}(C_j, t_i) </math> транзакции <math>t_i</math> на кластер <math>C_j</math>, если транзакция <math>t_i</math> в данный момент не находится на кластере <math>C_j</math>, а если транзакция <math>t_i</math> находится на кластере <math>C_j</math> — то стоимость ее удаления с данного кластера <math>Cost^{-}(C_j, t_i) </math>.		Поэтому в данном разделе условимся, что под выражением "'''обобщенная''' стоимость (цена) добавления <math>Cost^{\pm}(C_j, t_i) </math> транзакции <math>t_i</math> на кластер <math>C_j</math>" подразумевается непосредственно стоимость добавления <math>Cost^{+}(C_j, t_i) </math> транзакции <math>t_i</math> на кластер <math>C_j</math>, если транзакция <math>t_i</math> в данный момент '''не находится''' на кластере <math>C_j</math>, а если транзакция <math>t_i</math> '''находится''' на кластере <math>C_j</math> — то стоимость ее удаления с данного кластера <math>Cost^{-}(C_j, t_i) </math>.

Артем Желтков: /* Ресурс параллелизма алгоритма */

2017-01-30T23:58:08Z

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

← Предыдущая версия		Версия от 23:58, 30 января 2017
Строка 243:		Строка 243:

	Для удобства будем рассматривать одну операцию вычисления стоимости удаления транзакции с текущего кластера <math>Cost^{-}(C_{C(t_i)}, t_i) </math> совместно с операциями вычисления стоимости добавления транзакции на остальные кластеры <math>Cost^{+}(C_j, t_i) </math> — таким образом, на каждой итерации алгоритма для каждой транзакции должно производиться по одному выполнению такой обобщенной операции <math>Cost^{\pm}(C_j, t_i) </math> вычисления стоимости добавления/удаления на каждый из существующих кластеров.		Для удобства будем рассматривать одну операцию вычисления стоимости удаления транзакции с текущего кластера <math>Cost^{-}(C_{C(t_i)}, t_i) </math> совместно с операциями вычисления стоимости добавления транзакции на остальные кластеры <math>Cost^{+}(C_j, t_i) </math> — таким образом, на каждой итерации алгоритма для каждой транзакции должно производиться по одному выполнению такой обобщенной операции <math>Cost^{\pm}(C_j, t_i) </math> вычисления стоимости добавления/удаления на каждый из существующих кластеров.
	Поэтому в данном разделе условимся, что под выражением "'''обобщенная''' стоимость (цена) добавления транзакции <math>t_i</math> на кластер <math>C_j</math> <math>Cost^{~~\pm~~}(C_j, t_i) </math>~~)" подразумевается непосредственно стоимость добавления~~ транзакции <math>t_i</math> на кластер <math>C_j</math> ~~<math>Cost^{+}(C_j, t_i) </math>)~~, если транзакция <math>t_i</math> в данный момент не находится на кластере <math>C_j</math>, а если транзакция <math>t_i</math> находится на кластере <math>C_j</math> — то стоимость ее удаления с данного кластера <math>Cost^{-}(C_j, t_i) </math>.		Поэтому в данном разделе условимся, что под выражением "'''обобщенная''' стоимость (цена) добавления <math>Cost^{\pm}(C_j, t_i) </math> транзакции <math>t_i</math> на кластер <math>C_j</math>" подразумевается непосредственно стоимость добавления <math>Cost^{+}(C_j, t_i) </math> транзакции <math>t_i</math> на кластер <math>C_j</math>, если транзакция <math>t_i</math> в данный момент не находится на кластере <math>C_j</math>, а если транзакция <math>t_i</math> находится на кластере <math>C_j</math> — то стоимость ее удаления с данного кластера <math>Cost^{-}(C_j, t_i) </math>.


	Для алгоритма CLOPE кластеризации категориальных данных имеет место '''конечный''' параллелизм.		Для алгоритма CLOPE кластеризации категориальных данных имеет место '''конечный''' параллелизм.

	В рамках каждой итерации алгоритма (инициализирующей или уточняющей) можно выделить информационно-независимый фрагмент - вычисление обобщенной стоимости добавления текущей обрабатываемой транзакции на каждый из уже существующих кластеров — <math>Cost^{\pm}(C_j, t_i) </math>, при фиксированном значении <math>i</math>.		В рамках каждой итерации алгоритма (инициализирующей или уточняющей) можно выделить информационно-независимый фрагмент - вычисление обобщенной стоимости добавления текущей обрабатываемой транзакции на каждый из уже существующих кластеров — <math>Cost^{\pm}(C_j, t_i) </math>, при фиксированном значении <math>i</math>.


	То есть, для <math>i</math>-ой транзакции вычисление обобщенной цены добавления на <math>j</math>-й кластер никак не зависит от вычисления обобщенной цены добавления этой же транзакции на <math>k</math>-й кластер. Поэтому эти операции при обработке текущей транзакции <math>t_i</math> можно выполнять одновременно.		То есть, для <math>i</math>-ой транзакции вычисление обобщенной цены добавления на <math>j</math>-й кластер никак не зависит от вычисления обобщенной цены добавления этой же транзакции на <math>k</math>-й кластер. Поэтому эти операции при обработке текущей транзакции <math>t_i</math> можно выполнять одновременно.

Артем Желтков: /* Ресурс параллелизма алгоритма */

2017-01-30T23:55:53Z

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

← Предыдущая версия		Версия от 23:55, 30 января 2017
Строка 241:		Строка 241:

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
	~~Для алгоритма CLOPE кластеризации категориальных данных имеет место '''конечный''' параллелизм.~~

	Для удобства будем рассматривать одну операцию вычисления стоимости удаления транзакции с текущего кластера <math>Cost^{-}(C_{C(t_i)}, t_i) </math> совместно с операциями вычисления стоимости добавления транзакции на остальные кластеры <math>Cost^{+}(C_j, t_i) </math> — таким образом, на каждой итерации алгоритма для каждой транзакции должно производиться по одному выполнению такой обобщенной операции <math>Cost^{\pm}(C_j, t_i) </math> вычисления стоимости добавления/удаления на каждый из существующих кластеров.		Для удобства будем рассматривать одну операцию вычисления стоимости удаления транзакции с текущего кластера <math>Cost^{-}(C_{C(t_i)}, t_i) </math> совместно с операциями вычисления стоимости добавления транзакции на остальные кластеры <math>Cost^{+}(C_j, t_i) </math> — таким образом, на каждой итерации алгоритма для каждой транзакции должно производиться по одному выполнению такой обобщенной операции <math>Cost^{\pm}(C_j, t_i) </math> вычисления стоимости добавления/удаления на каждый из существующих кластеров.
	Поэтому в данном разделе условимся, что под выражением "'''обобщенная''' стоимость (цена) добавления транзакции <math>t_i</math> на кластер <math>C_j</math> <math>Cost^{\pm}(C_j, t_i) </math>)" подразумевается непосредственно стоимость добавления транзакции <math>t_i</math> на кластер <math>C_j</math> <math>Cost^{+}(C_j, t_i) </math>), если транзакция <math>t_i</math> в данный момент не находится на кластере <math>C_j</math>, а если транзакция <math>t_i</math> находится на кластере <math>C_j</math> — то стоимость ее удаления с данного кластера <math>Cost^{-}(C_j, t_i) </math>.		Поэтому в данном разделе условимся, что под выражением "'''обобщенная''' стоимость (цена) добавления транзакции <math>t_i</math> на кластер <math>C_j</math> <math>Cost^{\pm}(C_j, t_i) </math>)" подразумевается непосредственно стоимость добавления транзакции <math>t_i</math> на кластер <math>C_j</math> <math>Cost^{+}(C_j, t_i) </math>), если транзакция <math>t_i</math> в данный момент не находится на кластере <math>C_j</math>, а если транзакция <math>t_i</math> находится на кластере <math>C_j</math> — то стоимость ее удаления с данного кластера <math>Cost^{-}(C_j, t_i) </math>.

			Для алгоритма CLOPE кластеризации категориальных данных имеет место '''конечный''' параллелизм.

	В рамках каждой итерации алгоритма (инициализирующей или уточняющей) можно выделить информационно-независимый фрагмент - вычисление обобщенной стоимости добавления текущей обрабатываемой транзакции на каждый из уже существующих кластеров — <math>Cost^{\pm}(C_j, t_i) </math>, при фиксированном значении <math>i</math>.		В рамках каждой итерации алгоритма (инициализирующей или уточняющей) можно выделить информационно-независимый фрагмент - вычисление обобщенной стоимости добавления текущей обрабатываемой транзакции на каждый из уже существующих кластеров — <math>Cost^{\pm}(C_j, t_i) </math>, при фиксированном значении <math>i</math>.

Артем Желтков: /* Ресурс параллелизма алгоритма */

2017-01-30T23:55:12Z

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

← Предыдущая версия		Версия от 23:55, 30 января 2017
Строка 243:		Строка 243:
	Для алгоритма CLOPE кластеризации категориальных данных имеет место '''конечный''' параллелизм.		Для алгоритма CLOPE кластеризации категориальных данных имеет место '''конечный''' параллелизм.

	В рамках каждой итерации алгоритма (инициализирующей или уточняющей) можно выделить информационно-независимый фрагмент - вычисление стоимости добавления текущей обрабатываемой транзакции на каждый из уже существующих кластеров (отличных от текущего) — <math>Cost^{+}(C_j, t_i) </math>, при фиксированном значении <math>i</math>, а также вычисление стоимости удаления транзакции с текущего кластера <math>Cost^{-}(C_{C(t_i)}, t_i) </math> ~~для этого <math>i</math>.~~		Для удобства будем рассматривать одну операцию вычисления стоимости удаления транзакции с текущего кластера <math>Cost^{-}(C_{C(t_i)}, t_i) </math> совместно с операциями вычисления стоимости добавления транзакции на остальные кластеры <math>Cost^{+}(C_j, t_i) </math> — таким образом, на каждой итерации алгоритма для каждой транзакции должно производиться по одному выполнению такой обобщенной операции <math>Cost^{\pm}(C_j, t_i) </math> вычисления стоимости добавления/удаления на каждый из существующих кластеров.
	Для удобства будем рассматривать эту одну операцию вычисления стоимости удаления транзакции с текущего кластера совместно с операциями вычисления стоимости добавления транзакции на остальные кластеры — таким образом, на каждой итерации алгоритма для каждой транзакции должно производиться по одному выполнению такой обобщенной операции вычисления стоимости добавления/удаления на каждый из существующих кластеров.		Поэтому в данном разделе условимся, что под выражением "'''обобщенная''' стоимость (цена) добавления транзакции <math>t_i</math> на кластер <math>C_j</math> <math>Cost^{\pm}(C_j, t_i) </math>)" подразумевается непосредственно стоимость добавления транзакции <math>t_i</math> на кластер <math>C_j</math> <math>Cost^{+}(C_j, t_i) </math>), если транзакция <math>t_i</math> в данный момент не находится на кластере <math>C_j</math>, а если транзакция <math>t_i</math> находится на кластере <math>C_j</math> — то стоимость ее удаления с данного кластера <math>Cost^{-}(C_j, t_i) </math>.

	~~То есть, для <math>i</math>~~-~~ой транзакции~~ вычисление ~~цены~~ добавления ~~на <math>j</math>-й кластер никак не зависит от вычисления цены добавления этой же~~ транзакции на <math>k</math>~~-й кластер. Поэтому эти операции~~ при ~~обработке текущей транзакции~~ <math>~~t_i~~</math> ~~можно выполнять одновременно~~.		В рамках каждой итерации алгоритма (инициализирующей или уточняющей) можно выделить информационно-независимый фрагмент - вычисление обобщенной стоимости добавления текущей обрабатываемой транзакции на каждый из уже существующих кластеров — <math>Cost^{\pm}(C_j, t_i) </math>, при фиксированном значении <math>i</math>.

	Однако при этом важно отметить, что обработка всех транзакций на каждой итерации алгоритма (инициализирующей или уточняющей) должна выполняться строго последовательно - вычисления стоимостей добавления транзакции <math>t_{i+1}</math> на существующие кластеры могут быть начаты только после завершения обработки транзакции <math>t_i</math> - т.е. после вычислений стоимости ее удаления с текущего кластера (если итерация алгоритма - уточняющая) и стоимостей добавления на каждый из кластеров и возможного выполнения перемещения транзакции на новый кластер - потому как стоимости добавления транзакции <math>t_{i+1}</math> информационно зависят от результата распределения транзакции <math>t_i</math> на текущей итерации алгоритма.
			То есть, для <math>i</math>-ой транзакции вычисление обобщенной цены добавления на <math>j</math>-й кластер никак не зависит от вычисления обобщенной цены добавления этой же транзакции на <math>k</math>-й кластер. Поэтому эти операции при обработке текущей транзакции <math>t_i</math> можно выполнять одновременно.

			Однако при этом важно отметить, что обработка всех транзакций на каждой итерации алгоритма (инициализирующей или уточняющей) должна выполняться строго последовательно - вычисления обобщенных стоимостей добавления транзакции <math>t_{i+1}</math> на существующие кластеры могут быть начаты только после завершения обработки транзакции <math>t_i</math> — т.е. после вычислений всех ее обобщенных стоимостей добавления на каждый из кластеров (стоимости ее удаления с текущего кластера (если итерация алгоритма - уточняющая) и стоимостей добавления на каждый из остальных кластеров) и возможного выполнения перемещения транзакции на новый кластер — потому как обобщенные стоимости добавления транзакции <math>t_{i+1}</math> информационно зависят от результата распределения транзакции <math>t_i</math> на текущей итерации алгоритма.

	Таким образом, полагая, что количество вычислительных элементов не ограничено и всегда превышает количество кластеров <math>k</math>, существующих на любой из итераций алгоритма, можно считать, что обработка '''одной''' транзакции на каждой итерации алгоритма выполняется за <math>O(A)</math> операций (это соответствует сложности однократного вычисления <math>Cost^{\pm}(C_j, t_i) </math> - данная оценка описана в разделе [[#Последовательная сложность алгоритма\|Последовательная сложность алгоритма]]), где <math>A</math> — максимальная длина транзакции.		Таким образом, полагая, что количество вычислительных элементов не ограничено и всегда превышает количество кластеров <math>k</math>, существующих на любой из итераций алгоритма, можно считать, что обработка '''одной''' транзакции на каждой итерации алгоритма выполняется за <math>O(A)</math> операций (это соответствует сложности однократного вычисления <math>Cost^{\pm}(C_j, t_i) </math> - данная оценка описана в разделе [[#Последовательная сложность алгоритма\|Последовательная сложность алгоритма]]), где <math>A</math> — максимальная длина транзакции.