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

Demon smd в 21:13, 18 декабря 2016

2016-12-18T21:13:47Z

← Предыдущая версия		Версия от 21:13, 18 декабря 2016
Строка 3:		Строка 3:
	{{algorithm		{{algorithm
	\| name = Нечеткий алгоритм C средних (Fuzzy C-means)		\| name = Нечеткий алгоритм C средних (Fuzzy C-means)
	\| serial_complexity = <math>O(C^2\|X\|IterNumber)</math>		\| serial_complexity = <math>O(C^2\|X\|D*IterNumber)</math>
	\| pf_height = <math>O(\log_{2}C^4\|X\|^3) IterNumber</math>		\| pf_height = <math>O(\log_{2}C^4\|X\|^3) IterNumber</math>
	\| pf_width = <math>O(C^2\|X\|D)</math>		\| pf_width = <math>O(C^2*\|X\|)</math>
	\| input_data = <math>\|X\|*p</math>, где <math>p</math> - размерность входных векторов		\| input_data = <math>\|X\|*p</math>, где <math>p</math> - размерность входных векторов
	\| output_data = <math>\|X\|*C </math>		\| output_data = <math>\|X\|*C </math>

Demon smd в 21:13, 18 декабря 2016

2016-12-18T21:13:03Z

← Предыдущая версия		Версия от 21:13, 18 декабря 2016
Строка 5:		Строка 5:
	\| serial_complexity = <math>O(C^2\|X\|IterNumber)</math>		\| serial_complexity = <math>O(C^2\|X\|IterNumber)</math>
	\| pf_height = <math>O(\log_{2}C^4\|X\|^3) IterNumber</math>		\| pf_height = <math>O(\log_{2}C^4\|X\|^3) IterNumber</math>
	\| pf_width = <math>O(C^2*\|X\|)</math>		\| pf_width = <math>O(C^2\|X\|D)</math>
	\| input_data = <math>\|X\|*p</math>, где <math>p</math> - размерность входных векторов		\| input_data = <math>\|X\|*p</math>, где <math>p</math> - размерность входных векторов
	\| output_data = <math>\|X\|*C </math>		\| output_data = <math>\|X\|*C </math>

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

2016-12-18T21:12:34Z

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

← Предыдущая версия		Версия от 21:12, 18 декабря 2016
Строка 128:		Строка 128:
	* выбора начальных коэффициентов <math>u</math>		* выбора начальных коэффициентов <math>u</math>
	то в данном пункте будет приведена сложность одной итерации относительно количества входных векторов.		то в данном пункте будет приведена сложность одной итерации относительно количества входных векторов.
	Для вычисления коэффициентов u[][] на каждой итерации алгоритма требуется определить расстояние от векторов до центра кластера. Сложность данной операции зависит от размерности входных данных и определении нормы. В виду того, что для разных задач могут быть введены разные нормы, и сложность вычисления расстояний может варьироваться, то в данной статье сложность вычисления расстояния ~~будет считаться равной единице~~. В таком случае, для вычисления центров кластеров требуется <math>O(2C\|X\|)</math> операций, для определения коэффициентов <math>u</math> - <math>O(C^2\|X\|)</math> операций, а для вычисления решающей функции - <math>O(2C*\|X\|)</math> операций, где <math>\|X\|</math> - число входных векторов, а <math>C</math> - количество кластеров.		Для вычисления коэффициентов u[][] на каждой итерации алгоритма требуется определить расстояние от векторов до центра кластера. Сложность данной операции зависит от размерности входных данных и определении нормы. В виду того, что для разных задач могут быть введены разные нормы, и сложность вычисления расстояний может варьироваться, то в данной статье будем считать, что сложность вычисления расстояния зависит линейно от размерности водных данных. В таком случае, для вычисления центров кластеров требуется <math>O(2C\|X\|)</math> операций, для определения коэффициентов <math>u</math> - <math>O(C^2\|X\|D)</math> операций, а для вычисления решающей функции - <math>O(2C\|X\|)</math> операций, где <math>\|X\|</math> - число входных векторов, а <math>C</math> - количество кластеров.

	Таким образом итоговая сложность одной итерации составляет <math>O(C^2*\|X\|)</math>.		Таким образом итоговая сложность одной итерации составляет <math>O(C^2\|X\|D)</math>.

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

Chalker в 20:48, 18 декабря 2016

2016-12-18T20:48:31Z

← Предыдущая версия		Версия от 20:48, 18 декабря 2016
Строка 1:		Строка 1:
	{{Assignment\|~~{{REVISIONUSER}}~~}}		{{Assignment\|Coctic}}

	{{algorithm		{{algorithm

Demon smd в 17:37, 18 декабря 2016

2016-12-18T17:37:28Z

← Предыдущая версия		Версия от 17:37, 18 декабря 2016
Строка 3:		Строка 3:
	{{algorithm		{{algorithm
	\| name = Нечеткий алгоритм C средних (Fuzzy C-means)		\| name = Нечеткий алгоритм C средних (Fuzzy C-means)
	\| serial_complexity = <math>O(C^2\|X\|D*IterNumber)</math>		\| serial_complexity = <math>O(C^2\|X\|IterNumber)</math>
	\| pf_height = <math>O(\log_{2}C^4\|X\|^3) IterNumber</math>		\| pf_height = <math>O(\log_{2}C^4\|X\|^3) IterNumber</math>
	\| pf_width = <math>O(C^2*\|X\|)</math>		\| pf_width = <math>O(C^2*\|X\|)</math>

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

2016-12-18T17:10:15Z

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

← Предыдущая версия		Версия от 17:10, 18 декабря 2016
Строка 128:		Строка 128:
	* выбора начальных коэффициентов <math>u</math>		* выбора начальных коэффициентов <math>u</math>
	то в данном пункте будет приведена сложность одной итерации относительно количества входных векторов.		то в данном пункте будет приведена сложность одной итерации относительно количества входных векторов.
	~~Как видно из предыдущего пункта~~, для вычисления центров кластеров требуется <math>O(2C\|X\|)</math> операций, для определения коэффициентов <math>u</math> - <math>O(C^2\|X\|)</math> операций, а для вычисления решающей функции - <math>O(2C*\|X\|)</math> операций, где <math>\|X\|</math> - число входных векторов, а <math>C</math> - количество кластеров.		Для вычисления коэффициентов u[][] на каждой итерации алгоритма требуется определить расстояние от векторов до центра кластера. Сложность данной операции зависит от размерности входных данных и определении нормы. В виду того, что для разных задач могут быть введены разные нормы, и сложность вычисления расстояний может варьироваться, то в данной статье сложность вычисления расстояния будет считаться равной единице. В таком случае, для вычисления центров кластеров требуется <math>O(2C\|X\|)</math> операций, для определения коэффициентов <math>u</math> - <math>O(C^2\|X\|)</math> операций, а для вычисления решающей функции - <math>O(2C*\|X\|)</math> операций, где <math>\|X\|</math> - число входных векторов, а <math>C</math> - количество кластеров.

	Таким образом итоговая сложность одной итерации составляет <math>O(C^2*\|X\|)</math>.		Таким образом итоговая сложность одной итерации составляет <math>O(C^2*\|X\|)</math>.

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

2016-12-18T17:02:32Z

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

← Предыдущая версия		Версия от 17:02, 18 декабря 2016
Строка 142:		Строка 142:
	На каждом ярусе ярусно-параллельной формы алгоритма будет располагаться конечное число элементарных операций, например, чтение элемента из памяти, сложение или возведение в степень. Информационый граф из п.1.7 изображает свёрнутую ярусно-параллельную форму алгоритма.		На каждом ярусе ярусно-параллельной формы алгоритма будет располагаться конечное число элементарных операций, например, чтение элемента из памяти, сложение или возведение в степень. Информационый граф из п.1.7 изображает свёрнутую ярусно-параллельную форму алгоритма.

	Сложность алгоритма будем рассчитывать в предположении, что число вычислительных ядер стремится к бесконечности. Как видно из информационного графа, параллельная сложность вычисления центров кластеров составляет <math>O(\log_{2} C\|X\|)</math>, вычисления коэффициентов принадлежности - <math>O(\log_{2} C^2\|X\|)</math>, а вычисления решающей функции - не больше чем <math>O(\log_{2} C*\|X\|)</math>.		Сложность алгоритма будем рассчитывать в предположении, что число вычислительных ядер стремится к бесконечности. Как видно из информационного графа, параллельная сложность вычисления центров кластеров составляет <math>O(\log_{2}(C\|X\|))</math>, вычисления коэффициентов принадлежности - <math>O(\log_{2}(C^2\|X\|))</math>, а вычисления решающей функции - не больше чем <math>O(\log_{2} (C*\|X\|))</math>.

	Таким образом параллельная сложность итерации алгоритма составляет <math>O(\log_{2} C^4*\|X\|^3)</math>.		Таким образом параллельная сложность итерации алгоритма составляет <math>O(\log_{2} (C^4*\|X\|^3))</math>.

	Так как задачи, решаемые в макроструктуре алгоритма могут быть сведены к задачам вычисления суммы элементов массива и максимального элемента массива, то на <math>i</math>-ом ярусе графа будет находиться <math>{N}\over{2^i}</math> операции, где N - количество элементов массива.		Так как задачи, решаемые в макроструктуре алгоритма могут быть сведены к задачам вычисления суммы элементов массива и максимального элемента массива, то на <math>i</math>-ом ярусе графа будет находиться <math>{N}\over{2^i}</math> операции, где N - количество элементов массива.

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

2016-12-18T16:28:55Z

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

← Предыдущая версия		Версия от 16:28, 18 декабря 2016
Строка 39:		Строка 39:
	:<math>		:<math>
	\begin{align}		\begin{align}
	~~J_{m} =~~ \sum_{i = 1}^{\|X\|}\sum_{j = 1}^{C}u_{i,j}^m\left\Vert{x_{i}-c_{j}}\right\\|^2 & , & & 1 \le m \le \infty , \\		\sum_{i = 1}^{\|X\|}\sum_{j = 1}^{C}u_{i,j}^m\left\Vert{x_{i}-c_{j}}\right\\|^2 & , & & 1 \le m \le \infty , \\
	\end{align}		\end{align}
	</math>		</math>

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

2016-12-18T16:25:58Z

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

← Предыдущая версия		Версия от 16:25, 18 декабря 2016
Строка 122:		Строка 122:
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

	Последовательная сложность всего алгоритма складывается из сложности операций на каждой итерации умноженную на количество итераций. Так как в данном алгоритме количество итераций не является фиксированным и зависит от:		Последовательная сложность всего алгоритма складывается из сложности операций на каждой итерации умноженную на количество итераций.
			Под операцией будем понимать выражение в языке с++ из пункта 1.5, находящееся в теле цикла (например, выражения "sum+= pow( dist(x[i], c[j]) / dist(x[i], c[k]), 2/(m-1));" или "uPrev[i][j]=u[i][j];" считаются за одну операцию). Так как при больших входных объёмах данных сложность алгоритма в большей степени зависит от количества входных данных, и незначительно зависит от сложности операций,то при оценке сложности алгоритма сложность выражений можно считать равной единице. Так как в данном алгоритме количество итераций не является фиксированным и зависит от:
	* параметра <math>\varepsilon</math>		* параметра <math>\varepsilon</math>
	* набора входных векторов <math>x</math>		* набора входных векторов <math>x</math>

Marina abramenkova в 14:02, 18 декабря 2016

2016-12-18T14:02:00Z

← Предыдущая версия		Версия от 14:02, 18 декабря 2016
Строка 135:		Строка 135:
	Как видно из пункта 1.5, на каждом действии каждой итерации алгоритма все операции, выполняющиеся в цикле, не зависят друг от друга и могут быть распараллелены. Это показано на Рисунке 1.		Как видно из пункта 1.5, на каждом действии каждой итерации алгоритма все операции, выполняющиеся в цикле, не зависят друг от друга и могут быть распараллелены. Это показано на Рисунке 1.

	[[File:FCMIG.png\|thumb\|center\|1200px\|Рисунок 1. Информационный граф алгоритма. (1)-(7) - это наборы последовательных действий (например, (2) - последовательные операции деления, ~~взятия адреса~~ и присваивания).]]		[[File:FCMIG.png\|thumb\|center\|1200px\|Рисунок 1. Информационный граф алгоритма. (1)-(7) - это наборы последовательных действий (например, (2) - последовательные операции деления, чтения элемента из памяти и присваивания).]]

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

	На каждом ярусе ярусно-параллельной формы алгоритма будет располагаться конечное число элементарных операций, например, ~~взятие адреса~~, сложение или возведение в степень. Информационый граф из п.1.7 изображает свёрнутую ярусно-параллельную форму алгоритма.		На каждом ярусе ярусно-параллельной формы алгоритма будет располагаться конечное число элементарных операций, например, чтение элемента из памяти, сложение или возведение в степень. Информационый граф из п.1.7 изображает свёрнутую ярусно-параллельную форму алгоритма.

	Сложность алгоритма будем рассчитывать в предположении, что число вычислительных ядер стремится к бесконечности. Как видно из информационного графа, параллельная сложность вычисления центров кластеров составляет <math>O(\log_{2} C\|X\|)</math>, вычисления коэффициентов принадлежности - <math>O(\log_{2} C^2\|X\|)</math>, а вычисления решающей функции - не больше чем <math>O(\log_{2} C*\|X\|)</math>.		Сложность алгоритма будем рассчитывать в предположении, что число вычислительных ядер стремится к бесконечности. Как видно из информационного графа, параллельная сложность вычисления центров кластеров составляет <math>O(\log_{2} C\|X\|)</math>, вычисления коэффициентов принадлежности - <math>O(\log_{2} C^2\|X\|)</math>, а вычисления решающей функции - не больше чем <math>O(\log_{2} C*\|X\|)</math>.

← Предыдущая версия		Версия от 21:13, 18 декабря 2016
Строка 3:		Строка 3:
	{{algorithm		{{algorithm
	\| name = Нечеткий алгоритм C средних (Fuzzy C-means)		\| name = Нечеткий алгоритм C средних (Fuzzy C-means)
	\| serial_complexity = <math>O(C^2\|X\|IterNumber)</math>		\| serial_complexity = <math>O(C^2\|X\|D*IterNumber)</math>
	\| pf_height = <math>O(\log_{2}C^4\|X\|^3) IterNumber</math>		\| pf_height = <math>O(\log_{2}C^4\|X\|^3) IterNumber</math>
	\| pf_width = <math>O(C^2\|X\|D)</math>		\| pf_width = <math>O(C^2*\|X\|)</math>
	\| input_data = <math>\|X\|*p</math>, где <math>p</math> - размерность входных векторов		\| input_data = <math>\|X\|*p</math>, где <math>p</math> - размерность входных векторов
	\| output_data = <math>\|X\|*C </math>		\| output_data = <math>\|X\|*C </math>

← Предыдущая версия		Версия от 21:13, 18 декабря 2016
Строка 5:		Строка 5:
	\| serial_complexity = <math>O(C^2\|X\|IterNumber)</math>		\| serial_complexity = <math>O(C^2\|X\|IterNumber)</math>
	\| pf_height = <math>O(\log_{2}C^4\|X\|^3) IterNumber</math>		\| pf_height = <math>O(\log_{2}C^4\|X\|^3) IterNumber</math>
	\| pf_width = <math>O(C^2*\|X\|)</math>		\| pf_width = <math>O(C^2\|X\|D)</math>
	\| input_data = <math>\|X\|*p</math>, где <math>p</math> - размерность входных векторов		\| input_data = <math>\|X\|*p</math>, где <math>p</math> - размерность входных векторов
	\| output_data = <math>\|X\|*C </math>		\| output_data = <math>\|X\|*C </math>