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

ASA в 13:13, 19 декабря 2016

2016-12-19T13:13:57Z

← Предыдущая версия		Версия от 13:13, 19 декабря 2016
Строка 1:		Строка 1:
	{{Assignment\|~~Преподаватель 1~~\|Dexter}}		{{Assignment\|ASA\|Dexter}}
	~~{{Assignment\|ASA~~}}

	{{algorithm		{{algorithm

Dexter в 14:27, 12 декабря 2016

2016-12-12T14:27:31Z

← Предыдущая версия		Версия от 14:27, 12 декабря 2016
Строка 1:		Строка 1:
	{Assignment\|Преподаватель 1\|Dexter}}		{{Assignment\|Преподаватель 1\|Dexter}}
	{{Assignment\|ASA}}		{{Assignment\|ASA}}

Dexter в 14:27, 12 декабря 2016

2016-12-12T14:27:00Z

← Предыдущая версия		Версия от 14:27, 12 декабря 2016
Строка 1:		Строка 1:
			{Assignment\|Преподаватель 1\|Dexter}}
	{{Assignment\|ASA}}		{{Assignment\|ASA}}

Казаков Артем: /* Общее описание алгоритма */

2016-12-05T09:39:44Z

Общее описание алгоритма

← Предыдущая версия		Версия от 09:39, 5 декабря 2016
Строка 12:		Строка 12:

	== Общее описание алгоритма ==		== Общее описание алгоритма ==
	Алгоритм '''COBWEB''' — классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт (концепт — описание группы объектов через определенный набор пар аттрибут-значение) и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу.<ref name="habr" />		Алгоритм '''COBWEB'''<ref name="wiki" /><ref name="paper" /> — классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт (концепт — описание группы объектов через определенный набор пар аттрибут-значение) и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу.<ref name="habr" />

	Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории — прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания. Чтобы встроить новый объект в дерево классификации, алгоритм '''COBWEB''' итеративно проходит всё дерево в поисках «лучшего» узла, к которому отнести этот объект. Выбор узла осуществляется на основе помещения объекта в каждый узел и вычисления полезности категории получившегося среза. Также вычисляется полезность категории для случая, когда объект относится к вновь создаваемому узлу. В итоге объект относится к тому узлу, для которого полезность категории наибольшая.		Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории — прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания. Чтобы встроить новый объект в дерево классификации, алгоритм '''COBWEB''' итеративно проходит всё дерево в поисках «лучшего» узла, к которому отнести этот объект. Выбор узла осуществляется на основе помещения объекта в каждый узел и вычисления полезности категории получившегося среза. Также вычисляется полезность категории для случая, когда объект относится к вновь создаваемому узлу. В итоге объект относится к тому узлу, для которого полезность категории наибольшая.

Казаков Артем: /* Математическое описание алгоритма */

2016-12-05T09:38:35Z

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

← Предыдущая версия		Версия от 09:38, 5 декабря 2016
Строка 28:		Строка 28:
	Критерий полезности категории максимизирует вероятность того, что два объекта, отнесенные к одной категории, имеют одинаковые значения свойств и значения свойств для объектов из различных категорий отличаются. Полезность категории определяется формулой		Критерий полезности категории максимизирует вероятность того, что два объекта, отнесенные к одной категории, имеют одинаковые значения свойств и значения свойств для объектов из различных категорий отличаются. Полезность категории определяется формулой

	<math>CU = \sum_{k} \sum_{i} \sum_{j} P(A_j = u_{ij}\|C_k) P(C_k\|A_j = u_{ij}) P(A_j = u_{ij})</math>		<math>CU = \sum_{k} \sum_{i} \sum_{j} P(A_j = u_{ij}\|C_k) P(C_k\|A_j = u_{ij}) P(A_j = u_{ij})</math><ref name="shit" />

	Значения суммируются по всем категориям <math>C_k</math>, всем свойствам <math>A_j</math> и всем значениям свойств <math>u_{ij}</math>. Значение <math>P(A_j = u_{ij} \| C_k)</math> называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство <math>A_j</math> принимает значение <math>u_{ij}</math>, относится к категории <math>C_k</math>. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина <math>P(C_k \| A = u_{ij})</math> называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории <math>C_k</math> свойство <math>A_j</math> принимает значение <math>u_{ij}</math>. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение <math>P(A = u_{ij})</math> — это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.		Значения суммируются по всем категориям <math>C_k</math>, всем свойствам <math>A_j</math> и всем значениям свойств <math>u_{ij}</math>. Значение <math>P(A_j = u_{ij} \| C_k)</math> называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство <math>A_j</math> принимает значение <math>u_{ij}</math>, относится к категории <math>C_k</math>. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина <math>P(C_k \| A = u_{ij})</math> называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории <math>C_k</math> свойство <math>A_j</math> принимает значение <math>u_{ij}</math>. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение <math>P(A = u_{ij})</math> — это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

Казаков Артем: /* Общее описание алгоритма */

2016-12-05T09:38:16Z

Общее описание алгоритма

← Предыдущая версия		Версия от 09:38, 5 декабря 2016
Строка 12:		Строка 12:

	== Общее описание алгоритма ==		== Общее описание алгоритма ==
	Алгоритм '''COBWEB''' — классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт (концепт — описание группы объектов через определенный набор пар аттрибут-значение) и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу.		Алгоритм '''COBWEB''' — классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт (концепт — описание группы объектов через определенный набор пар аттрибут-значение) и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу.<ref name="habr" />

	Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории — прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания. Чтобы встроить новый объект в дерево классификации, алгоритм '''COBWEB''' итеративно проходит всё дерево в поисках «лучшего» узла, к которому отнести этот объект. Выбор узла осуществляется на основе помещения объекта в каждый узел и вычисления полезности категории получившегося среза. Также вычисляется полезность категории для случая, когда объект относится к вновь создаваемому узлу. В итоге объект относится к тому узлу, для которого полезность категории наибольшая.		Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории — прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания. Чтобы встроить новый объект в дерево классификации, алгоритм '''COBWEB''' итеративно проходит всё дерево в поисках «лучшего» узла, к которому отнести этот объект. Выбор узла осуществляется на основе помещения объекта в каждый узел и вычисления полезности категории получившегося среза. Также вычисляется полезность категории для случая, когда объект относится к вновь создаваемому узлу. В итоге объект относится к тому узлу, для которого полезность категории наибольшая.

Казаков Артем: /* Литература */

2016-12-05T09:37:48Z

Литература

← Предыдущая версия		Версия от 09:37, 5 декабря 2016
Строка 204:		Строка 204:
	= Литература =		= Литература =
	<references>		<references>
	<ref>https://en.wikipedia.org/wiki/Cobweb_(clustering) — описание алгоритма на Википедии (Eng)</ref>		<ref name="wiki">https://en.wikipedia.org/wiki/Cobweb_(clustering) — описание алгоритма на Википедии (Eng)</ref>
	<ref>https://habrahabr.ru/post/164417/ — сравнение алгоритма COBWEB с другими алгоритмами кластеризации</ref>		<ref name="habr">https://habrahabr.ru/post/164417/ — сравнение алгоритма COBWEB с другими алгоритмами кластеризации</ref>
	<ref>http://bourabai.ru/tpoi/analysis6.htm — подробное описание алгоритма COBWEB</ref>		<ref name="shit">http://bourabai.ru/tpoi/analysis6.htm — подробное описание алгоритма COBWEB</ref>
	<ref>http://www.cl.cam.ac.uk/~av308/cobweb.pdf — статья, в которой алгоритм COBWEB был впервые представлем</ref>		<ref name="paper">http://www.cl.cam.ac.uk/~av308/cobweb.pdf — статья, в которой алгоритм COBWEB был впервые представлем</ref>
	</references>		</references>

Казаков Артем: /* Литература */

2016-12-05T09:37:00Z

Литература

← Предыдущая версия		Версия от 09:37, 5 декабря 2016
Строка 203:		Строка 203:

	= Литература =		= Литература =
			<references>
	<ref>https://en.wikipedia.org/wiki/Cobweb_(clustering) — описание алгоритма на Википедии (Eng)</ref>		<ref>https://en.wikipedia.org/wiki/Cobweb_(clustering) — описание алгоритма на Википедии (Eng)</ref>
	<ref>https://habrahabr.ru/post/164417/ — сравнение алгоритма COBWEB с другими алгоритмами кластеризации</ref>		<ref>https://habrahabr.ru/post/164417/ — сравнение алгоритма COBWEB с другими алгоритмами кластеризации</ref>

Казаков Артем: /* Литература */

2016-12-05T09:36:40Z

Литература

← Предыдущая версия		Версия от 09:36, 5 декабря 2016
Строка 203:		Строка 203:

	= Литература =		= Литература =
	* https://en.wikipedia.org/wiki/Cobweb_(clustering)		<ref>https://en.wikipedia.org/wiki/Cobweb_(clustering) — описание алгоритма на Википедии (Eng)</ref>
	* https://habrahabr.ru/post/164417/		<ref>https://habrahabr.ru/post/164417/ — сравнение алгоритма COBWEB с другими алгоритмами кластеризации</ref>
	* http://bourabai.ru/tpoi/analysis6.htm		<ref>http://bourabai.ru/tpoi/analysis6.htm — подробное описание алгоритма COBWEB</ref>
	* http://www.cl.cam.ac.uk/~av308/cobweb.pdf		<ref>http://www.cl.cam.ac.uk/~av308/cobweb.pdf — статья, в которой алгоритм COBWEB был впервые представлем</ref>
			</references>

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

2016-12-05T09:32:02Z

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

← Предыдущая версия		Версия от 09:32, 5 декабря 2016
Строка 163:		Строка 163:
	== Масштабируемость алгоритма и его реализации ==		== Масштабируемость алгоритма и его реализации ==

	Исследование масштабируемости параллельной реализации алгоритма COBWEB проводилось на компьютере с процессором Intel(R) Core(TM) i7-5960X @ 4.30GHz, который поддерживает до 12ти потоков при наличии 6 физических ядер. Была взята реализация алгоритма COBWEB на Python из библиотки Concept Formation<ref>"~~https://github.com/cmaclell/concept_formation~~" ~~— библиотека, содержащая реализацию алгоритма COBWEB на языке Python<~~/~~ref~~> и распараллелена с использованием средств Python multiprocessing<ref>"https://docs.python.org/3.5/library/multiprocessing.html"</ref>.		Исследование масштабируемости параллельной реализации алгоритма COBWEB проводилось на компьютере с процессором Intel(R) Core(TM) i7-5960X @ 4.30GHz, который поддерживает до 12ти потоков при наличии 6 физических ядер. Была взята реализация алгоритма COBWEB на Python из библиотки Concept Formation<ref name="gh_cf" /> и распараллелена с использованием средств Python multiprocessing<ref>https://docs.python.org/3.5/library/multiprocessing.html — библиотека multiprocessing для распараллеливания программ на Python</ref>.

	Для исследования масштабируемости проводилось множество запусков программы с разным количеством объектов для кластеризации <math>N</math>, а также с различным числом процессоров. Фиксировались время работы и количество произведенных итераций алгоритма.		Для исследования масштабируемости проводилось множество запусков программы с разным количеством объектов для кластеризации <math>N</math>, а также с различным числом процессоров. Фиксировались время работы и количество произведенных итераций алгоритма.