Алгоритм управления процессом кластеризации по ближайшему расстоянию

Алгоритм управления процессом кластеризации по ближайшему расстоянию

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

Gespeichert in:
Bibliographische Detailangaben
Datum:2012
1. Verfasser: Коваль, П.Н.
Format: Artikel
Sprache:Russian
Veröffentlicht: Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2012
Schriftenreihe:Індуктивне моделювання складних систем
Online Zugang:http://dspace.nbuv.gov.ua/handle/123456789/45961
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Алгоритм управления процессом кластеризации по ближайшему расстоянию / П.Н. Коваль // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2012. — Вип. 4. — С. 87-91. — Бібліогр.: 4 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-45961
record_format dspace
spelling irk-123456789-459612013-06-22T03:18:27Z Алгоритм управления процессом кластеризации по ближайшему расстоянию Коваль, П.Н. Предложен алгоритм управления процессом кластеризации по ближайшему расстоянию с использованием процедуры иерархической группировки. Запропоновано алгоритм керування процесом кластеризації за найближчою відстанню з використанням процедури ієрархічного групування. There is proposed an algorithm of control for clustering process by nearest distance with the use of hierarchical grouping procedure. 2012 Article Алгоритм управления процессом кластеризации по ближайшему расстоянию / П.Н. Коваль // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2012. — Вип. 4. — С. 87-91. — Бібліогр.: 4 назв. — рос. XXXX-0044 http://dspace.nbuv.gov.ua/handle/123456789/45961 681.513 ru Індуктивне моделювання складних систем Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
description Предложен алгоритм управления процессом кластеризации по ближайшему расстоянию с использованием процедуры иерархической группировки.
format Article
author Коваль, П.Н.
spellingShingle Коваль, П.Н.
Алгоритм управления процессом кластеризации по ближайшему расстоянию
Індуктивне моделювання складних систем
author_facet Коваль, П.Н.
author_sort Коваль, П.Н.
title Алгоритм управления процессом кластеризации по ближайшему расстоянию
title_short Алгоритм управления процессом кластеризации по ближайшему расстоянию
title_full Алгоритм управления процессом кластеризации по ближайшему расстоянию
title_fullStr Алгоритм управления процессом кластеризации по ближайшему расстоянию
title_full_unstemmed Алгоритм управления процессом кластеризации по ближайшему расстоянию
title_sort алгоритм управления процессом кластеризации по ближайшему расстоянию
publisher Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate 2012
url http://dspace.nbuv.gov.ua/handle/123456789/45961
citation_txt Алгоритм управления процессом кластеризации по ближайшему расстоянию / П.Н. Коваль // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2012. — Вип. 4. — С. 87-91. — Бібліогр.: 4 назв. — рос.
series Індуктивне моделювання складних систем
work_keys_str_mv AT kovalʹpn algoritmupravleniâprocessomklasterizaciipobližajšemurasstoâniû
first_indexed 2025-07-04T05:00:48Z
last_indexed 2025-07-04T05:00:48Z
_version_ 1836691225192693760
fulltext Коваль П.Н. Індуктивне моделювання складних систем, випуск 4, 2012 87 УДК 681.513 АЛГОРИТМ УПРАВЛЕНИЯ ПРОЦЕССОМ КЛАСТЕРИЗАЦИИ ПО БЛИЖАЙШЕМУ РАССТОЯНИЮ П.Н.Коваль Международный научно-учебный центр информационных технологий и систем НАН и МОН Украины dep175@irtc.org.ua Предложен алгоритм управления процессом кластеризации по ближайшему расстоянию с использованием процедуры иерархической группировки. Ключевые слова: кластеризация, иерархическая группировка. There is proposed an algorithm of control for clustering process by nearest distance with the use of hierarchical grouping procedure. Keywords: clustering, hierarchical grouping. Запропоновано алгоритм керування процесом кластеризації за найближчою відстанню з використанням процедури ієрархічного групування. Ключові слова: кластеризація, ієрархічне групування. Вступление Ранее [1,2] нами было предложено использовать кластеризацию для удаления неинформативных признаков из первичного набора данных при построении математических моделей сложных систем. При значительном количестве неинформативных параметров процесс кластеризации, основанный на процедуре иерархической группировки, завершается выделением большого количества непредставительных кластеров. В настоящей работе предложен метод управления процессом кластеризации для получения представительных кластеров. Кластеризация по ближайшему расстоянию Кластеризация осуществляется с помощью процедуры иерархической группировки по ближайшему расстоянию d в многомерном пространстве параметров. При длине выборки N и количестве параметров m ближайшее расстояние di для i – ой точки Xi(xi1, xi2, xi3 … xim) определяется следующим образом: ),(min jiiji XXdd = при Njjirr ji ,1,, ∈≠≥ (1) где .1;)(;)( 11 2 1 2 ∑∑∑ === =−=−= N l lkk m k ikki m k jkikij x N xxxrxxd Алгоритм управления процессом кластеризации по ближайшему расстоянию Індуктивне моделювання складних систем, випуск 4, 2012 88 Использование функции плотности распределения для ближайшего расстояния d в виде: , 1 exp)1(),( 1           ⋅ − − − = − m m m m d x m m d xmdxp (2) где d - наиболее вероятное значение ближайшего расстояния, позволило свести задачу кластеризации к задаче дихотомии, а именно, к отделению внутри кластерных ближайших расстояний от меж кластерных. Для вычисления порога θ может быть использовано одно из известных решающих правил: байесовское, Неймана-Пирсона, по МПУ (метод предельных упрощений [3]) или мини- максное. С помощью функции плотности p(x,d) для каждого решающего правила может быть вычислена вероятность ошибки R , которая принята нами за оценку качества кластеризации, а именно, качество кластеризации тем выше, чем меньше значение вероятности ошибки. При использовании байесовского решающего правила для вероятности ошибки получено следующее выражение: . 1 ln exp 1 ln exp1*5.0                         −       −+             −       −−= m m m m D d d Dm d D d Dm R (3) где d - наиболее вероятное значение внутри кластерного ближайшего расстояния, усреднённое по кластерам; D - наиболее вероятное значение меж кластерного ближайшего расстояния. Как следует из (3), с ростом отношения D/d вероятность ошибки отделения внутрикластерных ближайших расстояний от межкластерных уменьшается. Кроме того, на ход функции R влияет мерность пространства параметров m . С увеличением мерности пространства значение R падает с ростом отношения D/d более резко. Возможность использования процедуры кластеризации для устранения неинформативных параметров обусловлена тем, что их исключение из выборки уменьшает значение вероятности ошибки R, тогда как исключение информативного параметра эту вероятность увеличивает. Это позволило организовать итеративный процесс исключения из выборки данных неинформативных параметров. Однако при наличии значительного количества неинформативных параметров в исходных данных процедура кластеризации оканчивается выделением большого количества слабо наполненных кластеров, либо объединением всех точек в один кластер. Коваль П.Н. Індуктивне моделювання складних систем, випуск 4, 2012 89 Управление ходом процесса кластеризации Термин кластеризация может быть расшифрован как автоматическая классификация при незаданном заранее числе классов. В одном из первых алгоритмов кластеризации «Форель» [4] вместо задания числа классов вводился максимальный радиус класса. При наличии «компактных» классов, т.е. ограниченных областей простой формы, равномерно заполненных точками, результаты классификации сохранялись при изменении заданного максимального радиуса в определенном интервале. Деформация классов (кластеров) сужала этот интервал. Для управления процессом кластеризации, базирующемся на использовании процедуры иерархической группировки, нами предложено организовать кластеризацию в виде итеративного процесса, использующего решающее правило Неймана-Пирсона либо МПУ. В первом случае задаётся граничное значение ошибки второго рода: ∫ ≤ θ β 0 .),( dxDxp (4) Это приводит к следующему выражению для решающего правила: ( )( ),1ln 1 m m mD βθ −−⋅ − ⋅= (5) где D – наиболее вероятное межкластерное расстояние. При использовании метода предельных упрощений [3] задаётся граничное значение вероятности ошибки первого рода α. Порог θ определяется при этом из условия: ∫ ∞ ≤ θ α.),( dxdxp (6) Из этого условия получаем следующее выражение для порога: ,ln 1 m m md αθ − −⋅= (7) где d – наиболее вероятное значение внутри кластерного расстояния. Управление кластеризацией осуществляется путём постепенного уменьшения значения величины ошибки первого рода α или второго рода β от 0.5 до значения, близкого к нулю. При значении α=0.5 число выделенных кластеров равняется числу точек выборки, а при α=0.0001 процесс кластеризации заканчивается объединением всех точек в один кластер. Алгоритм управления процессом кластеризации по ближайшему расстоянию Індуктивне моделювання складних систем, випуск 4, 2012 90 Кластеризация при вычислении порога по величине ошибки второго рода β носит противоположный характер: при β=0.5 получаем один кластер. Приемлемый вариант кластеризации находится повторением процедуры кластеризации с пошаговым уменьшением значения α или β. Алгоритм управления процессом кластеризации Таким образом, при значительном количестве неинформативных признаков в исходных данных, предложенный в [1] алгоритм следует дополнить итеративным процессом выбора окончательного варианта кластеризации. Опишем алгоритм управления кластеризацией на примере задания граничного значения величины ошибки первого рода α: 1. Принимаем α=0.25 и проводим кластеризацию. 2. Если число кластеров близко к числу точек, то уменьшаем значение α вдвое и снова проводим кластеризацию. 3. При объединении всех точек в один кластер, увеличиваем значение α на половину величины верхнего интервала и снова проводим кластеризацию. 4. При выделении преемлемого числа кластеров l , т.е. при l << N , значение α считаем окончательным. По этому значению оцениваем качество кластеризации. Решение тестового примера Для подтверждения работоспособности описанного алгоритма было проведено его испытание на тестовом примере. Была смоделирована смешанная выборка из 20 точек по 6 параметров каждая. В плоскости первых двух параметров все данные группировались в 2 разнесённых кластера. и две отдельно отстоящие точки. В плоскости 3-го и 4-го параметров точки образовали 4 других по составу кластера. В плоскости 5-го и 6-го параметров все точки были равномерно рассеяны по всей плоскости, т.е. эти параметры неинформативные. При переходе в пространство 5-ти измерений исключение неинформативного параметра дало следующие значения вероятности ошибки: α=0.0078125. При исключении второго (информативного) параметра получено следующее значение вероятности ошибки: α=0.046875. Как видим, даже при таком соотношении информативны и неинформативных параметров может быть проведена кластеризация и получена оценка её качества, т.е. исключение информативного параметра позволяет провести кластеризацию при более высоком значении Коваль П.Н. Індуктивне моделювання складних систем, випуск 4, 2012 91 вероятности ошибки первого рода, чем исключение неинформативного параметра. Исключение неинформативного параметра значительно снижает допустимую величину ошибки первого рода. Выводы Управление процессом кластеризации по ближайшему расстоянию с помощью процедуры иерархической группировки позволило выделить кластеры при значительном количестве неинформативных параметров в выборке исходных данных. При этом качество кластеризации оценивается непосредственно по значению вероятности ошибки (первого или второго рода) по отделению внутри кластерных расстояний от меж кластерных. Литература 1. Коваль П.Н. Использование кластеризации при анализе данных // УСиМ. - 2010. - №6. - С. 32 – 34. 2. Коваль П.Н. Использование кластеризации при выборе структуры объекта управления // Індуктивне моделювання складних систем. Єбірник наукових праць / Відп. Редактор В.С.Степашко – Київ: Міжнар. наук.- навч. центр інформ. технологій та систем НАН та МОН України, 2010.- Вип. 2. - 280 с. 3. Васильев В.И., Шевченко А.И., Эш С.Н. Принцип редукции в задачах обнаружения закономерностей // Донецьк: ІПШІ «Наука і освіта», 2009. – 340 с. 4. Загоруйко Н.Г. Методы распознавания и их применение. – М: Сов. Радио, 1972. – 208с. Вступление Кластеризация по ближайшему расстоянию Выводы

Ähnliche Einträge