Содержание к диссертации
Введение
Глава 1. Интеллектуальный анализ данных и задача кластеризации 10
1.1 Понятие об интеллектуальном анализе данных 10
1.2 Формальное описание задач интеллектуального анализа данных 12
1.2.1 Задачи регрессии и классификации 12
1.2.2 Задача поиска ассоциативных правил 13
1.2.3 .Задача кластеризации 14
1.3 Методы интеллектуального анализа данных 15
1.3.1 Математический аппарат интеллектуального анализа данных 15
1.3.2 Алгоритмические особенности решения задач интеллектуального анализа данных 16
1.4. Первичный анализ данных и задача кластеризации 17
1.4.1 Сравнение данных 17
1.4.2 Методы и алгоритмы кластеризации 19
Выводы 35
Глава 2. Разработка метода нецентроидной нечеткой кластеризации 36
2.1 Анализ свойств нечетких бинарных отношений применительно к анализу данных 36
2.1.1 Отношения и свойства отношений 36
2.1.2 Сравнение данных 42
2.1.3 Нечеткое отношение толерантности 44
2.1.4 Нечеткое отношение эквивалентности 46
2.2 Построение шкалы нечеткого отношения эквивалентности как алгоритм анализа данных 55
Выводы 58
Глава 3. Адаптивная кластеризация 60
3.1 Выбор параметров решения задачи кластеризации 60
3.1.1 Расстояние 60
3.1.2 Целевая функция, алгоритм 61
3.1.3 Количество кластеров 61
3.2 Критерии оценки качества решения задачи кластеризации (центроидные методы) 63
3.2.1 Коэффициент разбиения 64
3.2.2 Энтропийные критерии 65
3.2.3 Эффективность разбиения 67
3.3 Исследование критериев на предопределенных наборах (центроидные методы) 69
3.3.1 Искусственный набор данных 69
3.3.2 Ирисы (Fisher's irises) 72
3.4 Критерий оценки качества решения задачи кластеризации (метод нечеткого отношения эквивалентности) 76
3.4.1 Представление результатов решения задачи кластеризации при использовании нечеткого отношения эквивалентности 76
3.4.2 Построение критерия оценки качества разбиения, полученного с использованием нечеткого отношения эквивалентности 78
3.5 Исследование критериев на предопределенных наборах (метод нечеткого отношения эквивалентности) 79
3.5.1 Искусственный набор данных 79
3.5.2 Ирисы (Fisher's irises) 80
3.6 Методика адаптивной кластеризации 81
3.6.1 Предварительная подготовка данных 82
3.6.2 Определение целей анализа 82
3.6.3 Определение средств анализа и способа представления результатов 83
3.6.4 Подготовка данных 84
3.6.5 Формулировка ограничений, критериев оценки качества решения 86
3.6.6 Применение адаптивной кластеризации и анализ результатов 86
Выводы 87
Глава 4. Практическое применение адаптивной кластеризации 88
4.1 Контроль качества программного обеспечения 88
4.2 Методики анализа данных как необходимый элемент зрелости организации 90
4.3 Пример применения методики адаптивной кластеризации 93
4.3.1 Постановка задачи анализа данных 93
4.3.2 Уточнение целей и инструментария 94
4.3.3 Нормировка данных, подготовка к кластеризации 95
4.3.4 Формулировка ограничений, критериев оценки качества решения 96
4.3.5 Адаптивная кластеризация 97
4.3.6 Анализ результатов, корректировка исходных данных, повторная кластеризация, заключение по анализу 107
4.4 Многоагентная система интеллектуального анализа данных 109
4.4.1 Системы мобильных агентов 109
4.4.2 Описание методики проектирования многоагентной системы 112
4.4.3 Задача интеллектуального анализа распределенных данных. 114
4.4.4 Разработка многоагентной системы интеллектуального анализа данных 115
Выводы 119
Заключение 120
Список литературы 122
Приложение 129
- Формальное описание задач интеллектуального анализа данных
- Построение шкалы нечеткого отношения эквивалентности как алгоритм анализа данных
- Критерии оценки качества решения задачи кластеризации (центроидные методы)
- Исследование критериев на предопределенных наборах (центроидные методы)
Введение к работе
Актуальность. Настоящая работа посвящена разработке и исследованию методов и алгоритмов кластеризации, широко используемой в системах интеллектуального анализа данных. Синонимами термина интеллектуальный анализ данных являются добыча данных (data mining), обнаружение знаний (knowledge discovery) [1,2]. Интеллектуальный анализ данных связан с поиском в данных скрытых нетривиальных и полезных закономерностей, позволяющих получить новые знания об исследуемых данных. Особенный интерес к методам анализа данных возник в связи с развитием средств сбора и хранения данных, позволившим накапливать большие объемы информации. Перед специалистами из разных областей человеческой деятельности встал вопрос об обработке собираемых данных, превращения их в знания. Известные статистические методы покрывают лишь часть нужд по обработке данных, и для их использования необходимо иметь четкое представление об искомых закономерностях. В такой ситуации методы интеллектуального анализа данных приобретают особую актуальность. Их основная особенность заключается в установлении наличия и характера скрытых закономерностей в данных, тогда как традиционные методы занимаются главным образом параметрической оценкой уже установленных закономерностей. Среди методов интеллектуального анализа данных особое место занимают классификация и кластеризация. Классификация, при известной заранее группировке данных на подмножества (классы), устанавливает закономерность, по которой данные группируются именно таким образом. Кластеризация же, основываясь на установленном отношении схожести элементов, устанавливает подмножества (кластеры), в которые группируются входные данные. В широком круге задач нашли свое применение методы нечеткой кластеризации, в которых элементы входного множества относят к тому или иному кластеру на основании значения функции принадлежности. Нечеткая кластеризация одна из наиболее проработанных методик интеллектуального
анализа данных. Однако, традиционные методы нечеткой кластеризации не дают приемлемых решений на данных со сложной внутренней структурой. Это связано с рядом допущений, закладываемых в эти методы: кластеры имеют заданную форму и особую внутреннюю точку - центр кластера; разбиение определяется, исходя из взаимосвязей между данными и центрами кластеров. Так как кластеры в общем случае могут быть произвольной формы и не иметь центров, актуальной является разработка метода кластеризации, свободного от указанных допущений и обеспечивающего разбиение только на базе отношений на исследуемых данных.
Задача кластеризации имеет различные способы решения. Сложность заключается в отсутствии на момент начала анализа какой-либо дополнительной информации о данных. В связи с этим возможное множество решений по мощности сопоставимо с входным множеством, что на практике неприемлемо. Для качественного и быстрого решения задачи кластеризации необходимы методики выбора наилучших решений. Поэтому особую актуальность имеет разработка методики адаптивной кластеризации, при которой выбор наилучшего решения осуществляется формально, по заданным критериям.
Целью диссертационного исследования является разработка методов и алгоритмов кластеризации, не требующих предварительной информации о кластерах, для систем анализа данных.
В процессе достижения поставленной цели решались следующие задачи:
анализ проблем, возникающих при применении методов кластеризации;
разработка метода и алгоритма кластеризации на базе нечеткого отношения эквивалентности;
разработка критериев качества кластеризации, пригодных для построения адаптивной системы;
разработка методики адаптивной кластеризации.
7 Методы исследования. Методологической базой явились работы по
методам кластеризации, в том числе посвященные практическим аспектам их
применения. В работе использован математический аппарат теории нечетких
множеств, методы дискретной и вычислительной математики.
Основные положения, выносимые на защиту:
Определения нечетких отношений, порождаемых только на основании свойств исследуемых данных.
Метод и алгоритм кластеризации данных на базе нечеткого отношения эквивалентности, не требующие дополнительной информации о кластерах и не привлекающие понятий центра и формы кластера.
Методика адаптивной кластеризации, формализующая решение задачи, в том числе, оценку качества каждого разбиения и выбор наилучшего из них.
Научную новизну работы составляют:
определения нечетких отношений толерантности и эквивалентности, позволяющие порождать их из свойств исследуемых данных;
метод и алгоритм кластеризации на базе нечеткого отношения эквивалентности, основанные на отношениях, порождаемых данными, и не делающие допущений о форме кластеров и наличии в них центров, и, следовательно, лишенные недостатков традиционных методов;
критерии качества кластеризации, пригодные для построения адаптивной системы;
методика адаптивной кластеризации, основанная на использовании критериев оценки качества решения и позволяющая полностью формализовать решение задачи кластеризации. Отличительной особенностью методики является оценка качества каждого разбиения и выбор наилучшего из них. Кроме того, данная методика и рекомендации по ее применению позволяют значительно сократить ресурсы, затрачиваемые на анализ данных.
8 Обоснованность и достоверность полученных результатов
обеспечивается корректностью применяемого математического аппарата,
строгими доказательствами предложенных теорем и утверждений;
согласованностью получаемых результатов при использовании
предложенных методов и алгоритмов с результатами применения известных
подходов на тестовых примерах и задачах.
Практическая значимость работы состоит в том, что предложенные метод и алгоритм кластеризации на базе нечеткого отношения эквивалентности позволяют эффективно выявлять в данных кластеры произвольной формы; приведенные в работе критерии позволяют оценить качество решений задачи кластеризации, получаемых как при помощи традиционных методов, так и при помощи нового метода предлагаемого в работе; описанная в работе методика адаптивной кластеризации и рекомендации по ее применению позволяют значительно формализовать анализ данных и сократить затрачиваемые на него ресурсы; реализованная в составе системы мобильных агентов методика адаптивной кластеризации позволяет повысить уровень эффективности применения системы для решения задач интеллектуального анализа данных.
Реализация и внедрение результатов работы. Результаты диссертационного исследования внедрены в отделе контроля качества петербургского филиала ЗАО «Моторола ЗАО», что подтверждено актом о внедрении. Кроме того, результаты работы использованы в рамках реализации проекта министерства образования и науки Российской Федерации по теме: «Многоагентная технология интеллектуального анализа данных и извлечения знаний», код проекта 75103, а также проекта «Разработка теории и методов исследования самовосстанавливающихся систем» аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» министерства образования и науки Российской Федерации, код проекта 2.1.2.7828.
9 Апробация работы. Основные положения и результаты
диссертационной работы докладывались и обсуждались на международных конференциях по мягким вычислениям и измерениям SCM'2006 и SCM'2007, Санкт-Петербург, 2006-2007 г. г, конференциях профессорско-преподавательского состава СПбГЭТУ «ЛЭТИ», Санкт-Петербург, 2004-2007 г.г.
Публикации. Основные теоретические и практические результаты диссертации опубликованы в 4 работах, среди которых 1 работа в ведущих рецензируемых изданиях, рекомендуемых в действующем перечне ВАК, 2 -разделы книг, 1 работа - в материалах международной конференции.
Структура и объем диссертации. Диссертация состоит из введения, 4 глав с выводами и заключения. Она изложена на 147 листах машинописного текста и содержит 61 рисунок, 5 таблиц, 2 приложения, список литературы из 59 наименований.
Формальное описание задач интеллектуального анализа данных
Интеллектуальный анализ данных — область знаний, относящаяся к обработке данных, изучающая поиск и описание скрытых, нетривиальных и практически полезных закономерностей в исследуемых данных. Методы интеллектуального анализа данных получили особое развитие вследствие явления, получившего название информационного взрыва. Информационный взрыв - лавинообразное нарастание количества информации, накапливаемой в различных областях человеческой деятельности, и связанное с развитием средств вычислительной техники, особенно, средств хранения данных. Одним из следствий информационного взрыва явилось невозможность обработки всей накапливаемой информации при помощи имеющихся методов (в основном статистических). Важное отличие интеллектуального анализа данных от традиционных методик связано с выявлением при его помощи скрытых закономерностей в данных, в то время как другие методики занимаются параметрической оценкой уже известных закономерностей. Актуальность интеллектуального анализа выражается в большом количестве работ и конференций по данной тематике. Задачи интеллектуального анализа делятся на группы по типу искомых закономерностей. Среди задач различают [3]: Классификация — это отнесение объектов (наблюдений, событий) к одному из заранее известных классов. Кластеризация — это группировка объектов (наблюдений, событий) на основе данных (свойств), описывающих сущность объектов. Объекты внутри кластера должны быть «похожими» друг на друга и отличаться от объектов, вошедших в другие кластеры. Чем больше похожи объекты внутри кластера и чем больше отличий между кластерами, тем точнее кластеризация. Регрессия, в том числе задачи прогнозирования. Установление функциональной зависимости между зависимыми и независимыми переменными. Поиск ассоциативных правил — выявление закономерностей между связанными событиями. Примером такой закономерности служит правило, указывающее, что из события X следует событие Y. Такие правила называются ассоциативными. Впервые это задача была предложена для нахождения типичных шаблонов покупок, совершаемых в супермаркетах, поэтому иногда ее еще называют анализом рыночной корзины. Представленные задачи по назначению делятся на описательные и предсказательные.
Описательные задачи уделяют внимание сути зависимостей в исследуемых данных. Результат решения таких задач представляет собой эмпирическую модель данных и должен быть хорошо понятен и интерпретируем. Как правило, найденные закономерности описывают конкретный процесс, порождающий анализируемые данные, и не обобщаются для других процессов без дополнительного анализа. К описательным задачам можно отнести поиск ассоциативных правил и кластеризацию. В ходе решения предсказательных задач по исследуемым данным строится предсказательная модель. Построенная модель не обязательно хорошо интерпретируема, но может быть обобщена на другие данные. К подобным задачам относятся классификация, регрессия и, отчасти, поиск ассоциативных правил. Разделение на описательные и предсказательные задачи достаточно условно. Одни и те же задачи в зависимости от анализируемых данных можно отнести как к описательным, так и к предсказательным.
Кроме того, хотя решение описательной задачи интеллектуального анализа, является ценным само по себе, особый интерес представляет решение двухэтапной задачи интеллектуального анализа состоящей из построения предсказательной модели во второй части решения при помощи описательной модели, полученной в первой части решения. Примером такого анализа может служить связка кластеризации и последующей классификации по полученным кластерам. Способы решения задач интеллектуального анализа данных можно разделить на «обучение с учителем» и «обучение без учителя». Данные термины связаны с предоставлением («учителем») или непредоставлением дополнительной информации об анализируемых данных. Так решение задачи классификации относится к обучению с учителем, поскольку всегда предполагает наличие информации о классовой принадлежности каждого из элементов исследуемого множества. Задача кластеризации может быть отнесена к обучению без учителя, поскольку в идеальном случае не требует предоставления дополнительной информации. Кроме того, обучение с учителем часто связано с этапом уточнения решения, качество которого обеспечивается экспертом или специальной адаптивной процедурой. В задачах регрессии и классификации требуется определить значение зависимой переменной объекта на основании значений других переменных, характеризующих данный объект. Пусть дано конечное множество объектов 1= {i\,i2,...,ij,...i„}, каждый из которых характеризуется некоторым признаковым описанием (ii ,... ,...,vfflti), где Хк =Хк иХк- допустимое множество значений признака.
Пусть значения признаков (xijc2,---jCk,---Jm) известны. Тогда задача заключается в определении по известным признакам неизвестного признака д:„,+1. Если множество Хт+\ значений признака хт+1 конечно, то задачу называют классификацией. Если Хт+\ счетно или имеет мощность континуума, то говорят о задаче регрессии. Задача поиска ассоциативных правил заключается в обнаружении часто встречающихся наборов объектов в большом множестве таких наборов, а также закономерностей в их появлении. Дано конечное множество объектов /= {/ь/ г,..., ,,.../„} Пусть каждому наблюдаемому событию соответствует некоторое подмножество Ти множества /. Множество Th назовем событием. Рассмотрим конечное множество D всех наблюдаемых событий. Пусть мощность D равна т.
Построение шкалы нечеткого отношения эквивалентности как алгоритм анализа данных
В предыдущем разделе была представлена теоретическая база для исследования взаимосвязей образцов данных. В этом разделе будет представлен обобщенный алгоритм анализа данных с использованием нечеткого отношения эквивалентности и шкалы данного отношения (рис. 2.3). Дано множество образцов данных Х= {х}. Найти шкалу нечеткого отношения эквивалентности на множестве X. Перед описанием алгоритма необходимо договориться об используемых в алгоритме t-норме и t-конорме.
Будем использовать MIN-норму и МАХ-конорму. Алгоритм: 1) построить для каждого образца данных нормальную меру сходства (определение 18) по формуле 2.4; 2) построить относительно каждого образца данных на основании нормальной меры сходства относительную меру сходства для пар образцов данных (определение 19) по формуле 2.6; 5) построить для нечеткого отношения эквивалентности шкалу, как упорядоченное по возрастанию множество различных элементов матрицы этого отношения. Конец алгоритма. Построенная шкала нечеткого отношения эквивалентности порождает семейство отношений эквивалентности в классическом смысле.
С увеличением уровня эквивалентности получается все более четкие отношения и, соответственно, более детальные разбиения множества X. Каждое последующее разбиение получается из предыдущего, при этом классы эквивалентности, соответствующие более высокому уровню отношения, являются частями соответствующих классов более низких уровней. Кроме того, чем меньше уровень эквивалентности, тем меньше классов эквивалентности мы получаем и наоборот. Чем больше разность между соседними уровнями эквивалентности, тем лучше обособленны кластеры.
В заключение, продемонстрируем преимущества алгоритма на базе нечеткого отношения эквивалентности перед прочими алгоритмами построения разбиения. Для примера возьмем данные представляющие собой две вложенные окружности (рис. 2.4); алгоритм разбиения, использующийся для сравнения - Fuzzy C-Means. Как видно из рисунка 2.5 алгоритм Fuzzy C-Means разбил исходное множество на два пересекающихся кластера, причем каждый кластер содержит ровно половину от каждой окружности. Более того, даже увеличивая количество кластеров, не удается получить удовлетворительного решения. С другой стороны, используя алгоритм на базе нечеткого отношения эквивалентности для разбиения входного множества на два кластера, получим две вложенные окружности, что является наилучшим из возможных решений. 1) Даны определения нечетких отношений толерантности и эквивалентности, порождаемых из свойств исследуемых данных и составляющих основу предложенного метода кластеризации. 2) Предложены метод и алгоритм кластеризации на базе нечеткого отношения эквивалентности, которые не делают допущений о форме кластеров и наличии в них центров и лишены недостатков традиционных методов. 3) Алгоритм кластеризации на базе нечеткого отношения эквивалентности позволяет эффективно выявлять в данных кластеры произвольной формы.
Критерии оценки качества решения задачи кластеризации (центроидные методы)
Как уже было сказано, важным элементом адаптивной методики является критерий оценки качества, используемый при выборе наилучшего решения. В общем виде, критерий оценки качества решения задачи кластеризации - это численный показатель, вычисляемый по результатам кластеризации на данной итерации, суть которого — количественное выражение качества решения (в терминах этого критерия). Для определения критериев, которые подходят для использования в рамках адаптивной методики, разберем более подробно известные критерии [21,22]. где щ — соответствующий элемент матрицы принадлежности, X - входное множество, С - множество кластеров.
Как видно из формулы, единственным аргументом данного критерия является матрица принадлежности, полученная на данной итерации поиска решения. Рассмотрим значения, которые может принимать данный критерий. Для этого выделим сумму Из определения функции принадлежности и ее свойств имеем: Найдем экстремумы суммы (3.1) и условия, при которых они достигаются. Для этого перепишем сумму, учитывая, что Продифференцируем (3.4) по щ (/= 1,...,С -1) и приравняем каждое из полученных уравнений 0. Получим систему из (С - 1) уравнений: Из (3.5) видно, что мл = ид =...= м,сі-і. Учитывая это, получаем Значит, м,у= СГ (/= 1,...,С - 1). Учитывая (3.3), м,С = jCj"1. Таким образом, возможный экстремум (3.1) имеем в точке щ=\С\л (j=\,...,\C\). Значение второй производной по каждой из переменных константно и равно 4. Значит, в найденной точке имеем минимум, равный \С\Л. Значение же критерия при данных аргументах также равно \С\Л. На границе области определения (uip = 1, w«7 = 0, p,q=\,...,\C\, p q) критерий равен 1. Таким образом, можно заключить, что коэффициент разбиения принимает значения из [С -1,1], причем \С\Л соответствует случай максимальной неопределенности, когда все элементы входного множества с равной степенью принадлежат каждому из кластеров, а 1 - максимально четкое разбиение. Как видно из области значений критерия, у него есть неустранимый недостаток при оценке разбиений с разным количеством кластеров - область значений коэффициента разбиения напрямую зависит от выбранного количества кластеров. Энтропия разбиения выражается следующей формулой где щ — соответствующий элемент матрицы принадлежности, X - входное множество, С — множество кластеров.
Определим, какие значения принимает критерий в зависимости от аргументов. Для этого рассмотрим сумму Исходя из (3.2) понятно, что сумма (3.6) неотрицательна и ограничена сверху некоторым значением. Найдем ее экстремумы. Очевидно, что (3.6) принимает минимальное значение, по крайней мере, при условии, что и1р = \, а ищ = 0, p,q=l,...,\C\, p q. Найдем остальные экстремумы. Для этого перепишем сумму, учитывая (3.3) Продифференцируем (3.7) по щ (j= 1,...,C-1) и приравняем каждое из полученных уравнений 0. Получим систему из (С - 1) уравнений: Легко заметить, что она выполняется, лишь когда щ равны друг другу. Учитывая это наблюдение, запишем Каждое из уравнений выполняется тогда и только тогда, когда аргументы под знаком логарифма совпадают, из чего можно заключить, что ии = \С\ 1 (/= 1,...,1 С - 1). Учитывая (3.3) u,lQ = \С\ 1. При таком решении системы (3.8) примет нулевое значение и производная от (3.7) по щц . Выясним, какого рода особая точка найдена. Для этого найдем (С - 1) вторых производных суммы (3.6), учитывая (3.3): Из условия (3.2) видно, что (С-1) производная при м,уе(0,1) неположительна. Аналогичное свойство можно установить и для второй производной по щс\.
Таким образом, сумма (3.6) достигает единственного экстремума при щ = \С\ \ и данный экстремум - максимум, равный In \С\. Подставляя значение суммы (3.6) в формулу энтропии разбиения, получим In \С\. Данное значение критерия по смыслу соответствует наихудшему по информативности случаю: все значения функций принадлежности одинаковы. Минимальное значение данного критерия (равное 0) будет получено в том случае, если для каждого элемента входного множества найден кластер, принадлежность которому равна 1, что соответствует четкому разбиению. Таким образом, чем меньше значение данного критерия, тем более четкое разбиение мы получаем. Тем не менее, сравнивать кластеризации, полученные для разного количества кластеров при помощи данного критерия, некорректно, поскольку диапазон его значений для каждой кластеризации будет разным. Более правильным будет использовать следующий критерий.
Исследование критериев на предопределенных наборах (центроидные методы)
Второй набор данных представляет собой широко известное тестовое множество [23,24]. Оно состоит из 3 классов по 50 элементов в каждом. Каждый из классов - некоторый вид ириса. Один класс линейно отделим от двух других. Другие два класса линейно неотделимы друг от друга. Каждый входной вектор имеет четыре атрибута: длина чашелистика (см), ширина чашелистика (см), длина лепестка (см), ширина лепестка (см). Иллюстрация (рис. 3.6) в виде проекций подтверждает тезис о слабой отделимости 2 из трех кластеров: на всех проекциях явно видны лишь два отдельных подмножества. Для целей эксперимента использовался алгоритм Fuzzy C-Means. Для каждой из итераций высчитывались значения коэффициента разбиения (рис. 3.8), модифицированной энтропии разбиения (рис. 3.9) и эффективности разбиения (рис. 3.10). Черным цветом выделен искомый экстремум критерия, штриховкой - не совпадающее с ним значение критерия качества при известном количестве кластеров. Данное множество более сложно для кластеризации, тем не менее, один из критериев - эффективность разбиения - показал верное значение. Более внимательно рассматривая коэффициент разбиения при использовании на обоих наборах данных, можно заметить, что на малых значениях количества кластеров, данный критерий дает ошибочные значения.
Очевидно, это связано с областью значений [С ,1]. Можно попробовать, не меняя характера критерия, сдвинуть его область значений таким образом, чтобы зависимость от количества кластеров была связана не с началом указанного отрезка, а с его окончанием. С этой целью вычтем из коэффициента разбиения 1С]"1. Полученный критерий назовем модифицированным коэффициентом разбиения. Область его значений будет лежать в отрезке [О, (JCJ - 1)/С]. Вычислим значения этого критерия для полученных разбиений. Как видно из рисунков 3.11 и 3.12, преобразование коэффициента разбиения дало положительный эффект. В обоих случаях, при помощи данного критерия можно определить оптимальное количество кластеров. Описанный в данном разделе критерий был специально разработан для метода кластеризации, основанного на нечетком отношении эквивалентности. Представление результатов решения задачи кластеризации при использовании нечеткого отношения эквивалентности Как уже было отмечено в главе 2, при использовании нечеткого отношения эквивалентности для решения задачи кластеризации, в качестве результатов получаются два объекта: матрица нечеткого отношения эквивалентности и шкала уровней эквивалентности. В реальных задачах количество уровней в шкале эквивалентности близко к мощности исследуемого множества. Значит, именно такое число различных решений можно получить. В отличие от центроидной кластеризации, в данном случае решения можно представлять дендрограммой. Важно отметить, что не все классы эквивалентности, получаемые в результате кластеризации, являются практически полезными.
Специфика данной кластеризации состоит в том, что при повышении уровня эквивалентности, новое разбиение на классы получается из предыдущего путем разделения одного или нескольких классов (см. рис. 3.13). Как правило, классы эквивалентности значительно различаются по мощности (особенно в первой половине шкалы отношения). Группу наиболее мощных классов можно назвать практически полезными кластерами. Данную группу необходимо уметь отделять от остального множества классов эквивалентности. Пусть С={с\,...,сп} — множество всех классов эквивалентности, полученных для данного уровня эквивалентности, СсеС - множество всех практически полезных кластеров. Необходимо определить минимальную мощность класса эквивалентности ТН, при которой его можно считать практически полезным кластером. В этом случае Сс= {Vc,eC: \с,\ ТН}, Для определения ТН предлагается следующая процедура: 1) классы эквивалентности сортируются по убыванию мощности; 2) для каждой пары отсортированных классов вычисляется где первый множитель - отношение двух соседних по мощности классов, а второй - весовой коэффициент, задача которого (при прочих равных) -сместить максимум WR ближе к началу последовательности; 3) по максимуму WR определяется элемент в отсортированной последовательности классов. Его мощность будет равна ТН; Данная процедура нуждается в пояснениях. Исходя из определения, практически полезные кластеры будут находиться в начале отсортированной последовательности полученной на первом шаге. Надо определить, где заканчиваются кластеры и начинаются все остальные классы эквивалентности. Т.е. найти последний в ряду практически полезный кластер с,. Для этого вычисляется параметр WR — взвешенное отношение мощностей соседних по мощности классов эквивалентности. В WR помимо отношения двух соседних по мощности классов входит весовой коэффициент задача которого (при прочих равных) - сместить максимум WR ближе к началу последовательности. Таким образом, реализуя описанную выше процедуру, для каждого разбиения на классы эквивалентности можно выделить группу практически полезных кластеров, что будет являться важным элементом решения задачи кластеризации. Другой числовой характеристикой разбиения будет являться отношение суммарной мощности кластеров к общей мощности множества.
Назовем его коэффициентом разбиения. 3.4.2 Построение критерия оценки качества разбиения, полученного с использованием нечеткого отношения эквивалентности В подразделе 3.4.1 было подробно рассказано о дополнительных результатах кластеризации - практически полезных кластерах и коэффициенте разбиения. Таким образом, для каждого уровня отношения эквивалентности имеется следующий набор характеристик. 1) Уровень эквивалентности EL,. Чем выше этот уровень, тем более схожи объекты внутри классов эквивалентности, тем качественнее разбиение. 2) Множество практически полезных кластеров. Чем больше будет выделено таких кластеров, тем лучше. 3) Коэффициент разбиения. Чем он выше, тем качественнее разбиение. В общем случае, по мере увеличения уровня эквивалентности множество практически полезных кластеров увеличивается, но уменьшается коэффициент разбиения. Исходя из этого, можно сформулировать критерий наилучшего разбиения. Наилучшим разбиением назовем такое разбиение, для которого величина качества разбиения достигает максимума, где EL, - уровень эквивалентности, Сс = {сс} — множество практически полезных кластеров, а последний множитель -коэффициент разбиения. Формула для качества разбиения, как и процедура получения практически полезных кластеров, выведена эмпирическим путем на основании общих соображений о том, какое разбиение является полезным и наиболее качественным.
