Участник:Gkhazeeva/Нечеткий алгоритм C средних - История изменений

Gkhazeeva в 20:58, 19 декабря 2016

2016-12-19T20:58:59Z

← Предыдущая версия		Версия от 20:58, 19 декабря 2016
Строка 3:		Строка 3:
	{{algorithm		{{algorithm
	\| name = Нечеткий алгоритм C средних		\| name = Нечеткий алгоритм C средних
	\| serial_complexity = <math>O(Mc^~~2n_~~{iter} )</math>, <math>n_{iter} </math> - количество итераций		\| serial_complexity = <math>O(c^2 Mn_{iter} + cMdn_{iter})</math>, <math>n_{iter} </math> - количество итераций
	\| input_data = <math>Md</math>, [количество наблюдений размерность]		\| input_data = <math>Md</math>, [количество наблюдений размерность]
	\| output_data = <math>Mc</math>, [количество наблюдений количество кластеров]		\| output_data = <math>Mc</math>, [количество наблюдений количество кластеров]

Gkhazeeva в 20:57, 19 декабря 2016

2016-12-19T20:57:42Z

← Предыдущая версия		Версия от 20:57, 19 декабря 2016
Строка 6:		Строка 6:
	\| input_data = <math>Md</math>, [количество наблюдений размерность]		\| input_data = <math>Md</math>, [количество наблюдений размерность]
	\| output_data = <math>Mc</math>, [количество наблюдений количество кластеров]		\| output_data = <math>Mc</math>, [количество наблюдений количество кластеров]
	\| pf_height = <math>2n_{iter} </math>		\| pf_height = <math>O(cdn_{iter} + c^2n_{iter})</math>
	\| pf_width = <math>n</math>		\| pf_width = <math>O (M) </math>
	}}		}}

Gkhazeeva: /* Ресурс параллелизма алгоритма */

2016-12-19T20:56:30Z

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

← Предыдущая версия		Версия от 20:56, 19 декабря 2016
Строка 150:		Строка 150:

	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
	~~Параллельная сложность~~ алгоритма: <math>Mc^~~2n_~~{iter} </math>. ~~Такая сложность получается за счет распараллеливания на каждом ярусе~~ <math>M</math> ~~операций~~. Иерархическая структура параллелизма подробно описана в [[#Информационный граф\|п.1.7]].		На первом ярусе происходит <math> O(cdn_{iter}) </math> операций, на втором - <math> O(c^2n_{iter}) </math>, итого высота ЯПФ алгоритма <math> O(cdn_{iter} + c^2n_{iter}) </math>. Ширина ярусно-параллельной формы алгоритма равна <math> O(M) </math>. Иерархическая структура параллелизма подробно описана в [[#Информационный граф\|п.1.7]].

	В алгоритме не возникает скошенного параллелизма.		В алгоритме не возникает скошенного параллелизма.

Gkhazeeva: /* Информационный граф */

2016-12-19T20:15:34Z

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

← Предыдущая версия		Версия от 20:15, 19 декабря 2016
Строка 124:		Строка 124:
	Информационный граф представлен на рисунке ниже.		Информационный граф представлен на рисунке ниже.

	'''Первый ярус''' состоит из параллельных процессов, между которыми равномерно распределены <math>M</math> операций 1, 2, совершаемых в цикле <math>c</math> раз для каждого кластера.		'''Первый ярус''' состоит из <math>n_{p}</math> параллельных процессов, между которыми равномерно распределены <math>M</math> операций 1, 2, совершаемых в цикле <math>c</math> раз для каждого кластера.

	'''Операция 1''': <math>w_{ij}^m</math>, где <math>j</math> - номер итерации в цикле, <math>i</math> - номер параллельной ветви.		'''Операция 1''': <math>w_{ij}^m</math>, где <math>j</math> - номер итерации в цикле, <math>i</math> - номер параллельной ветви.
Строка 135:		Строка 135:
	Далее совершаем поэлементное сложение векторов и матриц соответственно, а затем делим каждый столбец в матрице на соответствующий элемент в векторе.		Далее совершаем поэлементное сложение векторов и матриц соответственно, а затем делим каждый столбец в матрице на соответствующий элемент в векторе.

	'''Второй ярус''' состоит из параллельных процессов, между которыми равномерно распределены <math>M</math> операций 3, 4, 5 также совершаемых в цикле <math>c</math> раз.		'''Второй ярус''' состоит из <math>n_{p}</math> параллельных процессов, между которыми равномерно распределены <math>M</math> операций 3, 4, 5 также совершаемых в цикле <math>c</math> раз.

	'''Операция 3''': обновление значения <math>w_{ij}</math> по указанной в разделе 1.2 в пункте 5 формуле.		'''Операция 3''': обновление значения <math>w_{ij}</math> по указанной в разделе 1.2 в пункте 5 формуле.

Gkhazeeva: /* Информационный граф */

2016-12-19T19:56:08Z

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

← Предыдущая версия		Версия от 19:56, 19 декабря 2016
Строка 135:		Строка 135:
	Далее совершаем поэлементное сложение векторов и матриц соответственно, а затем делим каждый столбец в матрице на соответствующий элемент в векторе.		Далее совершаем поэлементное сложение векторов и матриц соответственно, а затем делим каждый столбец в матрице на соответствующий элемент в векторе.

	'''Второй ярус''' состоит их <math>M</math> ~~параллельных~~ операций 3, 4, 5 также совершаемых в цикле <math>c</math> раз.		'''Второй ярус''' состоит из параллельных процессов, между которыми равномерно распределены <math>M</math> операций 3, 4, 5 также совершаемых в цикле <math>c</math> раз.

	'''Операция 3''': обновление значения <math>w_{ij}</math> по указанной в разделе 1.2 в пункте 5 формуле.		'''Операция 3''': обновление значения <math>w_{ij}</math> по указанной в разделе 1.2 в пункте 5 формуле.

Gkhazeeva: /* Информационный граф */

2016-12-19T19:55:35Z

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

← Предыдущая версия		Версия от 19:55, 19 декабря 2016
Строка 124:		Строка 124:
	Информационный граф представлен на рисунке ниже.		Информационный граф представлен на рисунке ниже.

	'''Первый ярус''' состоит из <math>M</math> ~~параллельных~~ операций 1, 2, совершаемых в цикле <math>c</math> раз для каждого кластера.		'''Первый ярус''' состоит из параллельных процессов, между которыми равномерно распределены <math>M</math> операций 1, 2, совершаемых в цикле <math>c</math> раз для каждого кластера.

	'''Операция 1''': <math>w_{ij}^m</math>, где <math>j</math> - номер итерации в цикле, <math>i</math> - номер параллельной ветви.		'''Операция 1''': <math>w_{ij}^m</math>, где <math>j</math> - номер итерации в цикле, <math>i</math> - номер параллельной ветви.

Gkhazeeva в 19:51, 19 декабря 2016

2016-12-19T19:51:02Z

← Предыдущая версия		Версия от 19:51, 19 декабря 2016
Строка 3:		Строка 3:
	{{algorithm		{{algorithm
	\| name = Нечеткий алгоритм C средних		\| name = Нечеткий алгоритм C средних
	\| serial_complexity = <math>O(~~Mdc~~^2n_{iter} )</math>, <math>n_{iter} </math> - количество итераций		\| serial_complexity = <math>O(Mc^2n_{iter} )</math>, <math>n_{iter} </math> - количество итераций
	\| input_data = <math>Md</math>, [количество наблюдений размерность]		\| input_data = <math>Md</math>, [количество наблюдений размерность]
	\| output_data = <math>Mc</math>, [количество наблюдений количество кластеров]		\| output_data = <math>Mc</math>, [количество наблюдений количество кластеров]

Gkhazeeva: /* Последовательная сложность алгоритма */

2016-12-19T19:50:11Z

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

← Предыдущая версия		Версия от 19:50, 19 декабря 2016
Строка 119:		Строка 119:

	== Последовательная сложность алгоритма ==		== Последовательная сложность алгоритма ==
	Последовательная сложность алгоритма состоит из сложности каждой итерации умноженной на их количество <math> n_{iter} </math>. Так как число итераций заранее неизвестно и зависит от входных параметров, рассмотрим сложность на каждой итерации. Наибольшую сложность представляет собой пересчет матрицы, сложность которого <math>O(c^2 Md)</math> (по сравнению со сложностью <math>O(cMd)</math> расчета расстояний, вычисления центроидов и проверки условия останова). Итого общая сложность алгоритма <math>O(c^2 ~~Mdn_~~{iter} )</math>		Последовательная сложность алгоритма состоит из сложности каждой итерации умноженной на их количество <math> n_{iter} </math>. Так как число итераций заранее неизвестно и зависит от входных параметров, рассмотрим сложность на каждой итерации. Наибольшую сложность представляет собой пересчет матрицы, сложность которого <math>O(c^2 M)</math> (по сравнению со сложностью <math>O(cMd)</math> расчета расстояний, вычисления центроидов и проверки условия останова). Итого общая сложность алгоритма <math>O(c^2 Mn_{iter} + cMdn_{iter})</math>. Так как обычно <math> n >> c </math>, то в этом случае сложность <math>O(c^2 Mn_{iter} )</math>.

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

Gkhazeeva: /* Свойства алгоритма */

2016-12-19T14:56:36Z

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

← Предыдущая версия		Версия от 14:56, 19 декабря 2016
Строка 164:		Строка 164:

	* Соотношение последовательной и параллельной сложности: <math>M</math>		* Соотношение последовательной и параллельной сложности: <math>M</math>
	* Вычислительная мощность: <math>{dc^2i} \over {c+d}</math>.		* Вычислительная мощность: <math>{dc^2n_{iter} } \over {c+d}</math>.
	* Устойчивость: алгоритм не является устойчивым, поэтому существует много исследований о том, как первоначально выбрать параметры кластеризации.		* Устойчивость: алгоритм не является устойчивым, поэтому существует много исследований о том, как первоначально выбрать параметры кластеризации.
	* Сбалансированность: в данном алгоритме операция умножения доминирует над операцией сложения. Операции между параллельными ветвями сбалансированы.		* Сбалансированность: в данном алгоритме операция умножения доминирует над операцией сложения. Операции между параллельными ветвями сбалансированы.

Gkhazeeva: /* Ресурс параллелизма алгоритма */

2016-12-19T14:56:16Z

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

← Предыдущая версия		Версия от 14:56, 19 декабря 2016
Строка 150:		Строка 150:

	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
	Параллельная сложность алгоритма: <math>Mc^2i</math>. Такая сложность получается за счет распараллеливания на каждом ярусе <math>M</math> операций. Иерархическая структура параллелизма подробно описана в [[#Информационный граф\|п.1.7]].		Параллельная сложность алгоритма: <math>Mc^2n_{iter} </math>. Такая сложность получается за счет распараллеливания на каждом ярусе <math>M</math> операций. Иерархическая структура параллелизма подробно описана в [[#Информационный граф\|п.1.7]].

	В алгоритме не возникает скошенного параллелизма.		В алгоритме не возникает скошенного параллелизма.