Участник:Мязина Екатерина/Алгоритм концептуальной кластеризации COBWEB - История изменений

ASA в 13:14, 27 октября 2016

2016-10-27T13:14:37Z

← Предыдущая версия		Версия от 13:14, 27 октября 2016
Строка 1:		Строка 1:
	~~{{Assignment}}~~

	{{algorithm		{{algorithm
	\| name = COBWEB		\| name = COBWEB

Мязина Екатерина в 18:32, 15 октября 2016

2016-10-15T18:32:46Z

← Предыдущая версия		Версия от 18:32, 15 октября 2016
Строка 1:		Строка 1:
			{{Assignment}}

	{{algorithm		{{algorithm
	\| name = COBWEB		\| name = COBWEB

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

2016-10-15T12:43:26Z

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

← Предыдущая версия		Версия от 12:43, 15 октября 2016
Строка 28:		Строка 28:
	обозначим через – множество распознаваемых объектов, характеризуемое бинарными параметрами , принимаемыми одно из возможных значений . – множество формируемых кластеров, где n – заранее неизвестно.		обозначим через – множество распознаваемых объектов, характеризуемое бинарными параметрами , принимаемыми одно из возможных значений . – множество формируемых кластеров, где n – заранее неизвестно.
	Полезность кластеризации в методе COBWEB рассматривается как функция <math>{\displaystyle CU}</math>, определяющая сходство объектов в рамках одного кластера, и их различие по отношению к объектам из других кластеров. Внутриклассовое сходство определяется условной вероятностью , а межклассовое сходство условной вероятностью .		Полезность кластеризации в методе COBWEB рассматривается как функция <math>{\displaystyle CU}</math>, определяющая сходство объектов в рамках одного кластера, и их различие по отношению к объектам из других кластеров. Внутриклассовое сходство определяется условной вероятностью , а межклассовое сходство условной вероятностью .
	Функция полезности кластеризации определяется в виде <math>{\displaystyle CU= \frac{\sum_{k=1}^{N}P(A=u_{ij}\|C_{k})\sum_{j}\sum_{i}(P(C_{k}\|A=u_{ij})^2-P(A=u_{ij})^2)}{N}}</math>, где n – количество кластеров.		Функция полезности кластеризации определяется в виде <math>{\displaystyle CU= \frac{\sum_{k=1}^{N}P(A=u_{ij}\|C_{k})\sum_{j}\sum_{i}(P(C_{k}\|A=u_{ij})^2-P(A=u_{ij})^2)}{N}}</math>, где N – количество кластеров.

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

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

2016-10-15T12:43:10Z

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

← Предыдущая версия		Версия от 12:43, 15 октября 2016
Строка 27:		Строка 27:
	Критерий полезности категории максимизирует вероятность того, что два объекта, отнесенные к одной категории, имеют одинаковые значения свойств и значения свойств для объектов из различных категорий отличаются.		Критерий полезности категории максимизирует вероятность того, что два объекта, отнесенные к одной категории, имеют одинаковые значения свойств и значения свойств для объектов из различных категорий отличаются.
	обозначим через – множество распознаваемых объектов, характеризуемое бинарными параметрами , принимаемыми одно из возможных значений . – множество формируемых кластеров, где n – заранее неизвестно.		обозначим через – множество распознаваемых объектов, характеризуемое бинарными параметрами , принимаемыми одно из возможных значений . – множество формируемых кластеров, где n – заранее неизвестно.
	Полезность кластеризации в методе COBWEB рассматривается как функция CU, определяющая сходство объектов в рамках одного кластера, и их различие по отношению к объектам из других кластеров. Внутриклассовое сходство определяется условной вероятностью , а межклассовое сходство условной вероятностью .		Полезность кластеризации в методе COBWEB рассматривается как функция <math>{\displaystyle CU}</math>, определяющая сходство объектов в рамках одного кластера, и их различие по отношению к объектам из других кластеров. Внутриклассовое сходство определяется условной вероятностью , а межклассовое сходство условной вероятностью .
	Функция полезности кластеризации определяется в виде (~~CU HERE~~), где n – количество кластеров.		Функция полезности кластеризации определяется в виде <math>{\displaystyle CU= \frac{\sum_{k=1}^{N}P(A=u_{ij}\|C_{k})\sum_{j}\sum_{i}(P(C_{k}\|A=u_{ij})^2-P(A=u_{ij})^2)}{N}}</math>, где n – количество кластеров.

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

Мязина Екатерина: /* Существующие реализации алгоритма */

2016-10-15T12:37:49Z

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

← Предыдущая версия		Версия от 12:37, 15 октября 2016
Строка 122:		Строка 122:

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

			*[https://github.com/cmaclell/concept_formation Working python implementation of COBWEB]

Мязина Екатерина: /* Информационный граф */

2016-10-15T12:37:04Z

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

← Предыдущая версия		Версия от 12:37, 15 октября 2016
Строка 87:		Строка 87:
	[[Файл:Cobweb graph.png\|border\|500px]]		[[Файл:Cobweb graph.png\|border\|500px]]

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

	== Ресурс параллелизма ==		== Ресурс параллелизма ==

Мязина Екатерина в 12:34, 15 октября 2016

2016-10-15T12:34:14Z

← Предыдущая версия		Версия от 12:34, 15 октября 2016
Строка 4:		Строка 4:
	}}		}}

	= ~~ЧАСТЬ.~~ Свойства и структура алгоритмов =		= Свойства и структура алгоритмов =

	== Общее описание алгоритма ==		== Общее описание алгоритма ==
Строка 106:		Строка 106:
	Результатом работы алгоритма является построенное дерево классификации, листья которого представляют собой различные классы объектов и содержат сами объекты принадлежащие данному классу.		Результатом работы алгоритма является построенное дерево классификации, листья которого представляют собой различные классы объектов и содержат сами объекты принадлежащие данному классу.

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

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

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

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

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

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

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

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

Мязина Екатерина в 12:32, 15 октября 2016

2016-10-15T12:32:59Z

← Предыдущая версия		Версия от 12:32, 15 октября 2016
Строка 105:		Строка 105:
	На вход алгоритм принимает множество объектов, характеризуемых набором свойств. В свою очередь, каждое свойство может принимать какое-либо значение из множества допустимых значений.		На вход алгоритм принимает множество объектов, характеризуемых набором свойств. В свою очередь, каждое свойство может принимать какое-либо значение из множества допустимых значений.
	Результатом работы алгоритма является построенное дерево классификации, листья которого представляют собой различные классы объектов и содержат сами объекты принадлежащие данному классу.		Результатом работы алгоритма является построенное дерево классификации, листья которого представляют собой различные классы объектов и содержат сами объекты принадлежащие данному классу.

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

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

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

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

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

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

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

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

Мязина Екатерина: /* ЧАСТЬ. Свойства и структура алгоритмов */

2016-10-15T12:31:14Z

ЧАСТЬ. Свойства и структура алгоритмов

← Предыдущая версия		Версия от 12:31, 15 октября 2016
Строка 85:		Строка 85:
	== Информационный граф ==		== Информационный граф ==

			[[Файл:Cobweb graph.png\|border\|500px]]

Мязина Екатерина: /* Ресурс параллелизма */

2016-10-15T12:16:46Z

Ресурс параллелизма

← Предыдущая версия		Версия от 12:16, 15 октября 2016
Строка 98:		Строка 98:
	Кроме того, стоит отметить, что оба данных подхода к распараллеливанию могут быть использованы вместе, что может быть полезно на системах типа MPI+OpenMP.		Кроме того, стоит отметить, что оба данных подхода к распараллеливанию могут быть использованы вместе, что может быть полезно на системах типа MPI+OpenMP.

	С точки зрения простоты реализации и получения наибольшей выгоды второй подход является более привлекательным и позволяет избавиться от квадратичной сложности, понизив оценку до <math>log_{B}n*~~B^AV~~</math>		С точки зрения простоты реализации и получения наибольшей выгоды второй подход является более привлекательным и позволяет избавиться от квадратичной сложности, понизив оценку до <math>log_{B}n*BAV</math>.

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