Участник:Dmitry/Плотностный алгоритм кластеризации - История изменений

ASA в 07:11, 9 февраля 2017

2017-02-09T07:11:40Z

← Предыдущая версия		Версия от 07:11, 9 февраля 2017
Строка 1:		Строка 1:
			{{Assignment\|ASA}}

	{{algorithm		{{algorithm
	\| name = Плотностный алгоритм кластеризации DBSCAN		\| name = Плотностный алгоритм кластеризации DBSCAN

Dmitry: /* Масштабируемость алгоритма и его реализации */

2017-02-08T19:58:19Z

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

← Предыдущая версия		Версия от 19:58, 8 февраля 2017
Строка 154:		Строка 154:


	[[Файл:График ~~масштабируемости~~.png\|thumb\|center\|800px\|Рис. 6. График масштабируемости DBSCAN]]		[[Файл:График масштабируемостиv2.png\|thumb\|center\|800px\|Рис. 6. График масштабируемости DBSCAN]]

	На рисунке 6 показан график масштабируемости DBSCAN, из которого можно сделать следующие выводы:		На рисунке 6 показан график масштабируемости DBSCAN, из которого можно сделать следующие выводы:

Dmitry: /* Масштабируемость алгоритма и его реализации */

2017-02-08T19:46:40Z

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

← Предыдущая версия		Версия от 19:46, 8 февраля 2017
Строка 146:		Строка 146:
	== Масштабируемость алгоритма и его реализации ==		== Масштабируемость алгоритма и его реализации ==

	Было проведено исследование масштабируемости параллельной реализации алгоритма DBSCAN. Исследование проводилось на суперкомпьютере "Ломоносов". Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI. Распараллеливание проводилось по числу входных объектов.		Было проведено исследование масштабируемости параллельной реализации алгоритма DBSCAN. Исследование проводилось на суперкомпьютере "Ломоносов". Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI. Распараллеливание проводилось по числу входных объектов. Программа реализована на языке C++.

			Набор и границы значений изменяемых параметров запуска реализации алгоритма:

			* число процессоров [1 : 128] с шагом по степеням двойки;
			* число входных объектов [1000 : 40000].


	[[Файл:График масштабируемости.png\|thumb\|center\|800px\|Рис. 6. График масштабируемости DBSCAN]]		[[Файл:График масштабируемости.png\|thumb\|center\|800px\|Рис. 6. График масштабируемости DBSCAN]]

	При увеличении размерности системы при фиксированном количестве процессов на области изменений значений параметров наблюдается увеличение эффективности.		На рисунке 6 показан график масштабируемости DBSCAN, из которого можно сделать следующие выводы:

			* При увеличении размерности системы при фиксированном количестве процессов на области изменений значений параметров наблюдается увеличение эффективности.

			* При увеличении числа процессов наблюдается уменьшение эффективности на всей области рассматриваемых значений параметров. При этом с ростом числа процессов снижение эффективности замедляется.

	При увеличении ~~числа~~ процессов наблюдается уменьшение эффективности ~~на всей области рассматриваемых значений параметров~~. При этом ~~с ростом числа процессов снижение~~ эффективности ~~замедляется~~.		* При одновременном увеличении количества процессов и размерности системы наблюдается уменьшение эффективности. При этом скорость убывания эффективности крайне низкая.

	При одновременном увеличении количества процессов и размерности системы наблюдается уменьшение эффективности. При этом скорость убывания эффективности крайне низкая.		[https://github.com/ByDmitryT/DBSCAN Реализация на языке C++]

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

Dmitry: /* Масштабируемость алгоритма и его реализации */

2017-02-07T16:47:58Z

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

← Предыдущая версия		Версия от 16:47, 7 февраля 2017
Строка 148:		Строка 148:
	Было проведено исследование масштабируемости параллельной реализации алгоритма DBSCAN. Исследование проводилось на суперкомпьютере "Ломоносов". Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI. Распараллеливание проводилось по числу входных объектов.		Было проведено исследование масштабируемости параллельной реализации алгоритма DBSCAN. Исследование проводилось на суперкомпьютере "Ломоносов". Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI. Распараллеливание проводилось по числу входных объектов.

	[[Файл:График масштабируемости.png\|thumb\|center\|800px\|Рис. 5. График масштабируемости DBSCAN]]		[[Файл:График масштабируемости.png\|thumb\|center\|800px\|Рис. 6. График масштабируемости DBSCAN]]

	При увеличении размерности системы при фиксированном количестве процессов на области изменений значений параметров наблюдается увеличение эффективности.		При увеличении размерности системы при фиксированном количестве процессов на области изменений значений параметров наблюдается увеличение эффективности.

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

2017-02-07T16:47:35Z

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

← Предыдущая версия		Версия от 16:47, 7 февраля 2017
Строка 112:		Строка 112:


	[[Файл:DBSCAN.png\|thumb\|center\|800px\|Рис. 4. Информационный граф алгоритма DBSCAN]]		[[Файл:DBSCAN.png\|thumb\|center\|800px\|Рис. 5. Информационный граф алгоритма DBSCAN]]

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

Dmitry: /* Масштабируемость алгоритма и его реализации */

2017-02-07T16:46:43Z

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

← Предыдущая версия		Версия от 16:46, 7 февраля 2017
Строка 145:		Строка 145:

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

			Было проведено исследование масштабируемости параллельной реализации алгоритма DBSCAN. Исследование проводилось на суперкомпьютере "Ломоносов". Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI. Распараллеливание проводилось по числу входных объектов.

	[[Файл:График масштабируемости.png\|thumb\|center\|800px\|Рис. 5. График масштабируемости DBSCAN]]		[[Файл:График масштабируемости.png\|thumb\|center\|800px\|Рис. 5. График масштабируемости DBSCAN]]

			При увеличении размерности системы при фиксированном количестве процессов на области изменений значений параметров наблюдается увеличение эффективности.

			При увеличении числа процессов наблюдается уменьшение эффективности на всей области рассматриваемых значений параметров. При этом с ростом числа процессов снижение эффективности замедляется.

			При одновременном увеличении количества процессов и размерности системы наблюдается уменьшение эффективности. При этом скорость убывания эффективности крайне низкая.

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

Dmitry: /* Масштабируемость алгоритма и его реализации */

2017-02-07T16:45:11Z

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

← Предыдущая версия		Версия от 16:45, 7 февраля 2017
Строка 145:		Строка 145:

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

			[[Файл:График масштабируемости.png\|thumb\|center\|800px\|Рис. 5. График масштабируемости DBSCAN]]

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

Dmitry: /* Макроструктура алгоритма */

2017-02-07T13:32:45Z

Макроструктура алгоритма

← Предыдущая версия		Версия от 13:32, 7 февраля 2017
Строка 61:		Строка 61:

	== Макроструктура алгоритма ==		== Макроструктура алгоритма ==
			Основную часть алгоритма на верхнем уровне составляют множественные вычисления расстояния между объектами.

	Вычисление расстояния между двумя объектами из выборки <math>D</math> осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: <math>dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.</math>		Вычисление расстояния между двумя объектами из выборки <math>D</math> осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: <math>dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.</math>

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

2017-02-05T12:24:29Z

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

← Предыдущая версия		Версия от 12:24, 5 февраля 2017
Строка 30:		Строка 30:
	Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).		Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).

	[[Файл:~~Окруженная_точка_при_MCP_~~=_5.png\|thumb\|center\|300px\|Рис. 1. Окруженная точка при MCP = 5]]		[[Файл:Окруженная_точка_при_MPC_=_5.png\|thumb\|center\|300px\|Рис. 1. Окруженная точка при MCP = 5]]

	Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MCP</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).		Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MCP</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).

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

2017-02-05T12:23:50Z

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

← Предыдущая версия		Версия от 12:23, 5 февраля 2017
Строка 26:		Строка 26:
	Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:		Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:

	<math>M_\varepsilon(X) \ge ~~MPC~~</math>		<math>M_\varepsilon(X) \ge MCP</math>

	Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).		Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).

	[[Файл:~~Окруженная_точка_при_MPC_~~=_5.png\|thumb\|center\|300px\|Рис. 1. Окруженная точка при ~~MPC~~ = 5]]		[[Файл:Окруженная_точка_при_MCP_=_5.png\|thumb\|center\|300px\|Рис. 1. Окруженная точка при MCP = 5]]

	Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>~~MPC~~</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).		Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MCP</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).

	[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png\|thumb\|center\|300px\|Рис. 2. Точка X прямо достижима по плотности от точки f]]		[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png\|thumb\|center\|300px\|Рис. 2. Точка X прямо достижима по плотности от точки f]]