Содержание к диссертации
Введение
Глава 1. Коллективные решения задачи кластерного анализа 16
1, Оптимальные комитетные решения, построенные по матрицам оценок 16
2, Построение оптимальных комитетных решений задач кластерного анализа 18
3. Подход к построению коллективного решения, основанный на повторной кластеризации результатов традиционными методами и их модификациями 24
4. Взаимосвязь комитетного синтеза и подхода, основанного на повторной кластеризации 27
Глава 2. Коллективные решения задачи кластерного анализа на основе восстановления компонент смеси по выборке объектов 29
1. Постановка задачи, идентифицируемость компонент 29
2. Одномерная задача восстановления параметров смеси 31
3. Алгоритмы решения задачи восстановления параметров смеси 37
4. Оптимальные коллективные решения на множествах одномерных решений 41
5. Практическая реализация алгоритмов решения задачи восстановления параметров смеси 43
Глава 3. Алгоритмы кластеризации, основанные на поиске оптимальных покрытий 48
1. Постановка задачи 48
2. Свойства задачи построения покрытия 51
3. Решение задачи построения оптимального покрытия 52
Глава 4. Результаты экспериментов 55
1: Сравнительные эксперименты на модельных задачах 55
2. Сравнительные эксперименты на реальных задачах 59
Глава 5. Универсальная программная система интеллектуального анализа данных, распознавания и прогноза распознавание 64
1. Возможности системы распознавание 66
2. Структура программы 70
3. Практическое применение 77
Заключение 80
Литература
- Построение оптимальных комитетных решений задач кластерного анализа
- Одномерная задача восстановления параметров смеси
- Свойства задачи построения покрытия
- Сравнительные эксперименты на реальных задачах
Введение к работе
В настоящее время кластерный анализ является важным разделом интеллектуального анализа данных. Не требуя априорных знаний о сущности рассматриваемых явлений, процессов или ситуаций и используя минимальную о них информацию в виде выборок описаний имеющихся прецедентов-наблюдений, методы кластерного анализа (классификации, таксономии, самообучения, обучения без учителя) позволяют находить практически ценные знания о природе объекта исследования (кластеры объектов, иерархические структуры в данных, эталонные объекты и «выбросы», и др.).
Интенсивные исследования в области кластерного анализа продолжаются с 60-х годов 20-го века в ведущих научных организациях, учреждениях и университетах мира. К настоящему времени сформировалось несколько подходов в кластерном анализе. Один из первых научных коллективов в области кластерного анализа был образован в Новосибирске под руководством Н.Г.Загоруйко [9, 10]. Алгоритм ФОРЕЛЬ позволяет решать задачу кластеризации заданной выборки векторных признаковых описаний объектов с помощью следующей итерационной схемы. Фиксируется положительное число (радиус гипершара), некоторая метрика в пространстве признаковых описаний и произвольный эталон обучающей выборки. Определяется подмножество векторов, принадлежащих гипершару с центром в заданном эталоне, и вычисляется средний вектор по данному множеству векторов. Данный средний вектор принимается за центр нового гипершара. Далее процесс повторяется. Критерием останова является достижение ситуации, когда центры гипершаров на двух последовательных итерациях совпадают. Объекты, принадлежащие «конечному» гипершару принимаются за объекты первого кластера, они исключаются из обучающей выборки и процесс повторяется сначала. Найденные в итоге число кластеров (и сами кластеры) будут зависеть от выбора метрики, начальных эталонов, радиусов гиперсфер. Другая группа методов, разработанная данной научной группой, основана на поиске таких разбиений выборки, которые минимизируют некоторый эвристический функционал качества разбиения. Функционал качества определяется как результат попытки формализации тех принципов, которыми руководствуется неформально человек при кластеризации плоских выборок, имеющих некоторую кластерную структуру. В данном критерии объединяются такие естественные соображения как «метрическая близость объектов одного кластера», «удаленность объектов разных кластеров», «число объектов одного кластера не должно многократно превышать число объектов другого кластера», «близость к граничному объекту объектов других кластеров должна быть существенно меньше чем близость к некоторым соседям из «своего» кластера». Оптимальная кластеризация находится как разбиение, минимизирующее заданный критерий. При этом перебор вариантов возможных разбиений основан на различных разрывах построенного по выборке минимального покрывающего дерева [9,10].
Простым, быстрым и широко известным является метод к - внутригрупповых средних, предложенный несколькими авторами примерно в одно и то же время 40-50 лет назад. На пространстве признаковых описаний объектов задается некоторая метрика. Строится начальное разбиение выборки на / группировок. Для каждой группировки вычисляется средний вектор. Далее осуществляется модификация группировок, а именно - объекты, ближайшие к определенному среднему вектору, попадают в одну группировку. Далее снова вычисляются средние вектора по каждой группировке и процесс повторяется. Кластеризация считается построенной, если для объектов каждой группировки ближайшим из средних является средний элемент именно данной группировки.
Обширный класс алгоритмов кластеризации связан с формализацией критерия качества разбиения и поиска разбиения выборки объектов, минимизирующего данный критерий. В качестве подобного критерия при фиксированном числе кластеров часто используют сумму квадратов, отклонений- объектов- группировок от средних. Ряд критериев, в том числе инвариантных относительно линейного невырожденного преобразования признакового пространства, основан на использовании матриц внутригруппового рассеяния (след, определитель, и другие) [I].
Иерархические кластеризации строятся на последовательном объединении близких группировок (агломеративные процедуры) или расщеплении множеств объектов на более мелкие (делимые процедуры) [1].
Существуют эффективные статистические методы кластерного анализа, В статистических моделях предполагается, что имеется конечное число / кластеров, априорные вероятности которых не известны. Для каждого кластера существует многомерная функция плотности распределения объектов, известная с точностью до набора числовых параметров. Считается, что кластеризуемая выборка объектов получена согласно данным вероятностным параметрам и функциям. Тогда задача нахождения неизвестных вероятностных параметров по заданной выборке объектов формулируется как задача поиска компонент смеси по заданной смеси. В ряде случаев, когда плотности компонент идентифицируемы, а функции плотностей являются дифференцируемыми, данная задача может быть успешно решена (например, с помощью метода максимального правдоподобия). После нахождения вероятностных параметров, кластеризация выборки осуществляется с помощью байесовского правила [1].
В методе динамических сгущений, являющимся далеким обобщением метода к -внутригрупповых средних, «среди всех разбиений на / кластеров следует найти разбиение, относительно каждого кластера которого заданное «ядро» оказалось бы наиболее представительным» [79]. Существуют подходы, основанные на использовании теории графов и различные эвристические подходы (метод к-эталонов, метод взаимного поглощения, и другие) [80].
Следует признать, что в настоящее время не существует универсальных методов кластерного анализа..Каждый отдельный метод использует "свое подмножество" из множества общеизвестных метрик, функций близости, критериев оптимальности, методов оптимизации, способов выбора начальных приближений, способов работы с разнотипными признаками, и т.п. Основные проблемы их практического применения связаны с трудоемкостью и многоэкстремальностью возникающих оптимизационных задач, нахождением вырожденных решений, сложностью сравнения и интерпретации решений, полученных различными алгоритмами. Кроме того, как правило, для каждого известного метода кластеризации можно привести пример задачи, имеющей выраженную кластерную структуру, но при решении которой данным методом полученное решение не соответствует реально существующим группировкам данных.
В ситуациях, когда при решении одной и той же задачи кластеризации различными алгоритмами находится множество существенно отличающихся решений, перспективным направлением исследований является разработка методов синтеза коллективных решений [2]. Коллективные подходы для решения задач кластерного анализа позволяют объединить в рамках единого формализма разнотипные алгоритмы кластеризации и находить оптимальные коллективные решения, в которых компенсируются неточности каждого из используемых базовых методов. Использование в качестве коллектива исходных решений набора локально-оптимальных кластеризации позволяет существенно расширить размерности решаемых практических задач.
В настоящей работе обобщается метод нахождения комитетных коллективных решений, а также исследуется подход к синтезу коллективных кластеризации, основанный на исследовании внутригрупповых расстояний различных кластеров.
Теория синтеза коллективных комитетных решений задачи кластерного анализа, впервые была предложена в [2]. Согласно ей, сначала для кластеризации произвольных объектов независимо применяются некоторые алгоритмы A1,...tAk. Далее результаты их применения специальным образом обрабатываются (решение оптимизационных задач на перестановках) и формулируется окончательное коллективное решение об отнесении объектов к одному из кластеров.
В настоящей работе обобщается метод комитетного синтеза для алгоритмов кластерного анализа, представимых в виде:
A(Jm) = K(rR(Jm)),
где Jm - таблица признаковых описаний объекта, R - оператор, переводящий таблицу признаковых описаний в матрицу оценок степени близости объектов к каждому из кластеров, а г - решающее правило. Данная форма представления является аналогичной записи алгоритмов распознавания в алгебраической теории распознавания [45, 56, 58]. Для данного общего случая вводятся определения операторов синтеза коллективных комитетных решений и критерии их качества. Получена верхняя оценка вариации функционала качества и разработан эффективный алгоритм комитетного синтеза, основанный на последовательной минимизации данных оценок.
Предложен подход для построения коллективных решений задачи кластерного анализа, основанный на использовании в качестве процедур коллективного синтеза известных методов кластеризации или их модификаций. Предложен и апробирован один алгоритм данного типа, основанный на идеях метода к-внугригрупповых средних. Обобщение комитетного синтеза коллективных кластеризации на случаи, когда исходный коллектив алгоритмов вычисляет матрицы оценок объектов за каждый кластер, новые алгоритмы построения коллективных решений в задаче кластерного анализа и составляют содержание первой главы диссертации.
Во второй главе рассматривается задача построения исходного набора кластеризации. Одним из естественных подходов к формированию коллектива кластеризации для последующего их склеивания является использование результатов анализа выборки по отдельным признакам, возможно, при определенных гипотезах о кластерных структурах. Если предполагать, что искомые кластеры имеют эллипсоидную или параллелепипедную форму, тогда удобно использовать аппарат статистической теории классификации без учителя, когда «функции плотносга» кластеров можно аппроксимировать функциями Гаусса.
В рамках статистической модели предложено использовать в качестве набора базисных кластеризации результаты независимого анализа отдельных признаков. При восстановлении одномерных компонент смеси развивается подход, основанный на предположении, что функциональный вид плотностей распределения объектов внутри кластеров и число кластеров известны и, единственное что надо узнать - это значение вектора неизвестных параметров. Традиционные методы нахождения неизвестных параметров, такие как метод «оценки по максимуму правдоподобия» и др., в случае решения задачи большой размерности, могут давать неудовлетворительные решения, существенно зависящие от удачного выбора начального приближения. Для рассматриваемой задачи параметрического восстановления плотностей компонент смеси разработан общий генетический алгоритм решения, не предъявляющий существенных ограничений к виду функций плотностей. Показано, что построение оптимальных комитетных кластеризации на базе восстановленных признаковых компонент смеси и обучающей выборки является новым способом построения байесовских решений для объектов обучающей выборки. Для случая равномерных распределений получены достаточные условия идентифицируемости смеси, предложен полиномиальный алгоритм восстановления плотностей, приведены примеры неидентифицируемых смесей. Описаны алгоритмы практического восстановления компонент смеси.
В третей главе рассматривается подход к решению задачи кластерного анализа, основанный на оптимальном покрытии выборки объектов системой гипершаров различного радиуса. Следует заметить, что многие традиционные методы кластерного анализа решают задачу путем построения разбиения выборки объектов в соответствии с некоторым, оптимальным- правилом.- Однако- в- ряде практических случаев -постановка задачи как задачи поиска оптимального покрытия может оказаться предпочтительнее задачи поиска оптимальных разбиений. Примерами подобных ситуаций являются случаи, когда возможность пересечения кластеров обусловлена самой природой практической задачи (объекты разных кластеров эквивалентны согласно различным отношениям эквивалентности), наличием «выбросов» и «шумовых» объектов. Под последними можно понимать те объекты, для которых отнесение в один из кластеров не является более предпочтительным чем отнесение в другой. В таких случаях решение об их принадлежности двум (или нескольким) кластерам может быть более правильным, чем «искусственное» зачисление в один из кластеров. Тогда задача кластеризации решается в два последовательных этапа: нахождение оптимального покрытия и построения по данному покрытию окончательного разбиения — кластеризации выборки. Данная задача на покрытия является многоэкстремальной, но здесь может быть эффективно применена идеология синтеза коллективных решений на базе множества приближенных локально-оптимальных решений.
Четвертая глава посвящена изложению результатов численных экспериментов. Эксперименты проводились на модельных и реальных практических задачах. В качестве модельных задач рассматривались смеси выборок, порожденные генератором случайных чисел согласно нормальному закону распределения и при гипотезе о статистической независимости признаков. Параметры распределений выбирались такими, чтобы точность решения задачи классификации с учителем на данных выборках была выше 99%. Обоснование применения смесей нормальных распределений для решения реальных задач кластерного анализа содержится в [12-14], где отмечается, что использование таких смесей только в качестве первой аппроксимации неизвестной функции плотности вероятности дает удовлетворительные результаты. Кроме того, известно существование реальных объектов в биологии, медицине, психологии, астрономии и других областях, распределение которых есть смесь нормальных распределений [15,16]. Идея применения конечных смесей нормальных распределений для решения задач распознавания развивалась в работах зарубежных и отечественных исследователей: Г.С. Себестиана, Дж. Ту, Р. Гонсалеса, Д.А. Хартигана, Т.В. Андерсона, Л.Д. Мешалкина, Л.Г. Малиновского, Ш.Ю. Раудиса и других [12,13,16-23].
Для данного типа задач безусловным лидером по качеству решения задач кластеризации должен быть метод максимального правдоподобия. Действительно, данный факт подтверждался на серии многих экспериментов при малых и средних размерностях задач. Однако при большом числе признаков и кластеров явным лидером становится метод коллективных к-средних.
При решении практических задач, для которых статистическая модель классификации становится неприемлемой, применение метода максимального правдоподобия дает отрицательные результаты. В то же время, решения, полученные с помощью предложенных в диссертации алгоритмов являются достаточно высокими относительно результатов, полученных методами распознавания (классификации с учителем).
Пятая глава диссертации посвящена разработке программной системы анализа данных и распознавания по выборкам прецедентов, в которой была сделана попытка аккумулировать основные подходы (в том числе коллективные) для решения задач распознавания и кластерного анализа в рамках общей формализации исходных данных и полученных решений. Заметим, что обычно различные методы анализа данных в качестве исходной информации используют лишь наборы описаний-наблюдений объектов (прецедентов, ситуаций, предметов), при этом каждый отдельный объект записывается в виде вектора значений отдельных его свойств-признаков. Выборки признаковых описаний являются простейшими стандартизованными представлениями первичных исходных данных, которые возникают в различных предметных областях в процессе сбора однотипной информации, и которые могут быть использованы для решения следующих задач:
1. распознавание (диагностика) ситуаций, явлений, объектов или процессов с обоснованием решений;
2. кластерный анализ и исследование структуры данных;
3. выявление существенных признаков и нахождение простейших описаний;
4. нахождение эмпирических закономерностей различного вида;
5. построение аналитических описаний множеств (кластеров) объектов;
6. нахождение нестандартных или критических случаев;
7. формирование эталонных описаний образов.
Разработки программных систем анализа данных активно ведутся в России и ведущих зарубежных странах. Прежде всего, это статистические пакеты обработки данных и визуализации (SPSS, STADIA, STATGRAPHICS, STATISTICA, SYSTAT, Олимп:СтатЭксперт Prof,, Forecast Expert, и другие), в основе которых лежат методы различных разделов математической статистики - проверка статистических гипотез, регрессионный анализ, дисперсионный анализ, анализ временных рядов и др. Использование статистических программных продуктов стало стандартным и эффективным инструментом анализа данных, и, прежде всего, начального этапа исследований, когда находятся значения различных усредненных показателей, проверяется статистическая достоверность различных гипотез, находятся регрессионные зависимости. Вместе с тем статистические подходы имеют и существенные недостатки. Они позволяют оценить (при выполнении некоторых условий) статистическую достоверность значения прогнозируемого параметра, гипотезы или зависимости, однако сами методы вычисления прогнозируемых величин, выдвижения гипотез или нахождения зависимостей имеют очевидные ограничения. Прежде всего, находятся усредненные по выборке величины, что- может, быть, достаточно- грубым представлением об анализируемых или прогнозируемых параметрах. Любая статистическая модель использует понятия «случайных событий», «функций распределения случайных величин» и т.п., в то время как взаимосвязи между различными параметрами исследуемых объектов, ситуаций или явлений являются детерминированными. Само применение статистических методов подразумевает наличие определенного числа наблюдений для обоснованности конечного результата, в то время как данное число может быть существенно больше имеющегося или возможного. То есть в ситуациях анализа в принципе непредставительных данных, или на этапах начала накопления данных, статистические подходы становятся неэффективными как средство анализа и прогноза.
В последние годы появились узкоспециализированные пакеты интеллектуального анализа данных. Для данных пакетов часто характерна ориентация на узкий круг практических задач, а их алгоритмической основой является какая-либо одна из альтернативных моделей, использующая нейронную сеть, решающие деревья, ограниченный перебор, и т.п. [55]. Ясно, что подобные разработки существенно ограничены при практическом использовании. Во-первых, заложенные в них подходы не является универсальными относительно размерностей задач, типа, сложности и структурированности данных, величины шума, противоречивости данных и т.п. Во-вторых, созданные и «настроенные» на решение определенных задач, они могут оказаться совершенно бесполезными для других. Наконец, множество задач, представляющих интерес практическому пользователю, обычно шире возможностей отдельного подхода. Например, пользователю может быть важно иметь численную характеристику надежности некоторого прогноза, но «решающее дерево» ее не вычисляет. «Нейронная сеть» выступает в роли «черного ящика», предлагающего некоторый прогноз без его обоснования. Логические методы распознавания позволяют выявлять логические закономерности в данных и использовать их при прогнозировании, но при наличии линейных зависимостей между признаками и прогнозируемой величиной точность прогноза, сделанного «линейной машиной», может быть заметно выше.
Таким образом, на настоящем уровне развития методов решения задач анализа данных, представляется предпочтительным путь создания программных средств, включающих основные существующие разнообразные подходы. В данном случае повышаются шансы подбора из имеющихся алгоритмов такого алгоритма, который обеспечит наиболее точное решение интересующих пользователя задач на новых данных. Другим важным атрибутом систем анализа и классификации должно быть наличие средств автоматического решения задач распознавания и классификации коллективами алгоритмов. Действительно, стандартной ситуацией является наличие нескольких альтернативных алгоритмов или решений, равнозначных для пользователя. Для выбора из них одного наиболее предпочтительного не хватает информации. Тогда естественной альтернативой выбору является создание на базе имеющихся алгоритмов или решений новых, более предпочтительных. Теоретические основы практической реализации идеи решения задач анализа данных коллективами алгоритмов были разработаны в ВЦ РАН в рамках алгебраического подхода для решения задач распознавания (логическая и алгебраическая коррекция алгоритмов) в 1976-1980 [45, 56, 57] и комитетного синтеза классификаций для задач кластерного анализа (автоматической классификации) в 1981-1982 годах [49, 50]. Позднее появились исследования в данной области и в других странах.
Все изложенные выше идеи легли в основу разработки универсальной программной системы интеллектуального анализа данных, распознавания и прогноза РАСПОЗНАВАНИЕ. Под универсальностью системы понимается возможность ее применения к максимально широкому кругу задач (по размерностям, по типу, качеству и структуре данных, по вычисляемым величинам). Под интеллектуальностью понимается наличие элементов самонастройки испособности-успешногоавтоматического решения задач неквалифицированньш пользователем. Для достижения данных показателей были проведены работы по объединению различных подходов в рамкой единой системы, в частности, по унификации обозначений, форматов, пользовательских интерфейсов и единых форм представления результатов обработки данных. В рамках системы РАСПОЗНАВАНИЕ разработана библиотека программ, реализующих линейные, комбинаторно-логические, статистические, нейросетевые, гибридные методы прогноза, классификации и извлечения знаний из прецедентов, а также коллективные методы прогноза и классификации. Диссертантом лично была разработана общая программная структура системы РАСПОЗНАВАНИЕ и реализованы следующие ее части: графическая оболочка, ядро системы, система составления комплексных отчетов, средства анализа объектов коллективом методов, загрузчики данных, ЕМ - алгоритм, метод к -внутригрупповых средних, комитетный метод построения коллективных решений задач кластерного анализа.
Построение оптимальных комитетных решений задач кластерного анализа
В главе рассматриваются вопросы обработки множества решений задачи кластерного анализа, независимо полученных различными алгоритмами, с целью нахождения оптимальных коллективных решений данной задачи. Исследуется выборка S = {jCj,.,., „,}, заданная таблицей признаковых описаний Л(5) = а1п Ы__ » U, на множестве вещественнозначных признаков, где п- число признаков, aw- число объектов. Пусть с помощью некоторого алгоритма кластеризации А выборка S {xlt...,xm} разбита на / кластеров или покрыта / кластерами при возможности их пересечения. Обозначим кластеры через К ...,К{. Результат кластеризации можно записать в виде информационной матрицы /= flfj , где А Є {0,1,Д}, av=\, если XJGKJ, сСд-О, если х, К}, ац = Д соответствует отказу от зачисления х( в один из кластеров. В отличие от задач распознавания, где каждый кластер имеет свое априорное смысловое содержание, в задачах кластерного анализа кластеры могут нумероваться в произвольном порядке. Поэтому произвольная информационная матрица / , отличающаяся от / лишь перестановкой столбцов, будет являться записью того же самого решения. называются
Определение: Информационные матрицы /=afJ и / = u/v эквивалентными, если они равны с точностью до перестановки столбцов.
На множестве всех эквивалентных матриц размерности mxl аксиомы рефлексивности, симметричности и транзитивности вьшолнены. Произвольная матрица шЛ определяет класс fflfJ J всех эквивалентных ей матриц [2].
Определение: Алгоритмом кластеризации А называется алгоритм, переводящий описания J„(S) объектов jclv..,:cm в класс эквивалентности ioU J о є {0,1,Д}, i = l,.,.,m, j = l /.
Символически алгоритм кластерного анализа записывается в виде: A(JJS)) = K\\ag\\J.
Рассматривается множество алгоритмов кластеризации, которые могут быть представлены в виде: A(J„) = K(rR(Jm))tToесть / = rR(Jm). Оператор R(J„) вычисляет по Jm числовую матрицу оценок степени близости объектов к каждому из кластеров: 0 Д, 1.
Оператор г называется решающим правилом над множеством матриц оценок и переводит их в информационные матрицы: AfiA )=lkl = ІГ ІІих/ II «Них/
Задача построения оптимального коллективного решения, базирующегося на результатах кластеризации выборки 5 алгоритмами Л1,...,Ля»выполняетсявдваэтапа:
1. построение отображения Jm на множество Кс классов эквивалентности orJ J, авє {0,1,Д}, / = 1,...,/я, у = 1,...,/, каждым из используемых алгоритмов.
2. Нахождение оптимального коллективного решения задачи кластерного анализа путем поиска наилучшего в определенном смысле элемента из Кс.
Будем считать, что все рассматриваемые алгоритмы Л1,..., А" используют одинаковое решающее правило г: \1,0вЬ0л,Чк,к = 1,...,1 [О, иначе. Определение: Оператор В над множеством матриц оценок 1вЛ , г = 1,...,и называется сумматором, если « у=1
Определение: Комитетным синтезом информационной матрицы / = шЛ на таблице признаковых описаний выборки объектов J„ называется ее вычисление I =r(B{Jm)) при условиях: В - сумматор, г - решающее правило. Из определения сумматора следует, что 0 bv l, і = 1,..., m, j = 1,...,1. В результате применения сумматора к набору матриц оценок, будет получена новая матрица оценок. Оператор гВ осуществляет отображение Jm на некоторое множество
Кс = рГЦ, J/. Таким образом, произведение гВ определяет новый алгоритм кластерного анализа. Теперь задача нахождения оптимального комитетного решения задачи кластерного анализа коллективом алгоритмов А ,...,А" состоит в поиске наилучшего элемента из Кс.
Оценка качества коллективных решений проводится на основе анализа соответствующих матриц оценок, по которым строится коллективное решение. Из множества всех числовых матриц оценок /О , 0 , Д, , 1, выделяют два специальных подмножества, соответствующих следующим определениям. Определение: Числовая матрица /у называется контрастной, если /?ff {0,1}, Определение: Числовая матрица \рЛ называется размытой, если &=/?,, 0 Дй1, z = l,...,m, у = 1,...,/.
Важным частным случаем размытых матриц оценок является следующая. Определение: Числовая матрица /?J если / =—, / = 1,..-,ш, 7 = 1,...,/. Контрастные и размытые матрицы имеют следующую интерпретацию. Контрастные матрицы — потенциально возможный класс матриц оценок, в которых для каждого объекта точно известно, принадлежит ли он тому или иному классу или нет. Например, контрастные матрицы, получающиеся в результате применения сумматора к информационным матрицам различных алгоритмов кластеризации, означают полное совпадение решений задачи кластерного анализа алгоритмами А1,..., А" и нумерации кластеров при вычислении Ъц. Достижение контрастных матриц оценок в комитетном синтезе считается наилучшим возможным результатом.
Одномерная задача восстановления параметров смеси
Предполагается, что объекты получены выделением состояния природы о), с вероятностью P(0)j) и последующим выделением д: в соответствии с вероятностным законом p(x\a)j,0).
Таким образом, функция плотности распределения объектов определяется как: р( 1 ) = Е/ дау, №у). (2-і) где В = (9 ...,9,). Функция плотности такого вида называется функцией плотности смеси [1]. Условные по кластерам плотности p(x\o)j,9j) называются плотностями компонент или плотностями кластеров (классов), а априорные вероятности Р((о,) - параметрами смеси [1]. Определение: Плотность р(х\9) считается идентифицируемой, если из в в (с точностью до переобозначения кластеров) следует, что существует х, такой, что р(х\9") р(х\9 )\\\ Решением поставленной задачи является нахождение значений неизвестных параметров 9 =(0 ...,9,) и априорных вероятностей кластеров Р(а }),. j = \,...,l, таких чтобы функция (2.1), построенная на них, наилучшим образом описывала исследуемую выборку. Правдоподобием исследуемой выборки объектов называется величина: p(S\e) = Ylp(x,\6).
Оценка по максимуму правдоподобия 0 - это такое значение в, которое максимизирует p(S \ в). В том случае, если функция p{S 19) дифференцируема по в, то путем приравнивания нулю дифференциала по в логарифма p(Sв), могут быть получены формулы, задающие итерационный процесс нахождения 9. Основанные на таком подходе методы, являются традиционными эффективными средствами решения задач кластерного анализа. Однако описанный подход требует решения задачи нахождения начальных приближений неизвестных параметров, а итерационная процедура градиентного спуска не гарантирует, что найденный оптимум - глобальный.
Одномерная задача восстановления параметров смеси Имеется выборка объектов S= {xlt...,xm}, заданная таблицей значений признаков принимаемых на объектах pj , где т - число объектов, а п - число признаков. При решении одномерной задачи рассматривается проекция всей выборки S на некоторый признак. Используя только одномерную проекцию, однозначное нахождение значений неизвестных параметров одномерного распределения объектов внутри каждого кластера не всегда возможно. Приведем пример задачи, которая имеет бесконечное число векторов значений параметров, задающих разные наборы компонент, соответствующих рассматриваемой выборки объектов.
Рассмотрим выборку, состоящую из двух кластеров, описываемую двумя признаками. Истинные плотности распределения объектов обоих кластеров по признакам - равномерные, они задаются следующей формулой Q,x a j J - - ti b)-a} р ( 1 ) = Т-Г їх Щ где і є {1,2} - номер признака, у" є {1,2} - номер кластера. При этом Ь[=а12, / = {1,2}, и Ъ\—а\—с, для любых /, j є {1,2}. Априорные вероятности обоих кластеров одинаковы. Р(щ) = Р( о2) = 0.5. В двумерном пространстве области ненулевых значений плотностей вероятности кластеров, выглядят следующим образом: что в точности совпадает с (2.2) и верно для любого вещественного к, 0 к 1. Таким образом, параметры исследуемой смеси объектов не могут быть идентифицируемы путем анализа одномерных проекций выборки, так как существует бесконечное число различных двумерных выборок, одномерные проекции которых будут совпадать.
Так как в рассматриваемом примере аналогичная ситуация имеет место и для другого признака, то предлагаемый метод решения не подходит для данной задачи. Заметим, что если для второго признака задача будет решаться однозначно, то после построения коллективного решения может быть получено истинное распределение объектов для многомерной выборки.
Между тем, существует класс задач, для которого решение одномерных задач восстановления плотностей распределения компонент, будет иметь единственное решение. Для случая, когда все кластеры имеют нормальные плотности распределения значений признаков объектов верно следующее утверждение [5-7].
Утверждение 1.1: Если функция плотности распределения выборок р(х\в) является суммой плотностей компонент, подчиняющихся нормальному закону распределения значений признаков объектов (с попарно неравными векторами параметров Oj и ненулевыми априорными вероятностями P( Dj)), то такое представление является единственным с точность до переобозначения кластеров. Итак, рассматривается одномерный случай поиска параметров одномерной функции плотности распределения объектов внутри кластеров по заданной выборке объектов из этих кластеров. В данном параграфе индексы, характеризующие номер признака, будут опускаться. Функцию рэ(х) назовем эмпирической функцией плотности распределения смеси / кластеров, а функцию pf(x) - эмпирической функцией плотности распределения /-ого кластера. Заметим, что формулы для рэ(х) и р?(х) справедливы при произвольном распределении объектов внутри кластеров. Таким образом, эмпирическая функция плотности распределения смеси / кластеров рэ(х) задана в виде конечного набора ее значений на интервалах [XO XI] (XI X2] —I(XN-I XN]- Требуется найти ее наилучшее приближение в виде: P3(x) p,Pi(x\eth 1=1 где pt(x j 0{) - функция плотности распределения объектов внутри кластера j , известная с точностью до значений вектора параметров 0t, а Р, - неизвестная априорная вероятность /-ого кластера. Ниже рассматриваются алгоритмы решения данной задачи для общего случая, а также конкретных видов функции плотности распределения элементов внутри кластеров.
Свойства задачи построения покрытия
В данном параграфе приводятся результаты экспериментального исследования рассматриваемых в данной работе методов на модельных задачах. Эксперименты проводились на выборках объектов, состоящих из кластеров, которые имеют нормальные плотности распределения объектов по признакам. Были проведены испытания для выборок состоящих из пяти, десяти и пятнадцати классов. При исследованиях изучалась зависимость точности решения описываемыми методами от возрастающей сложности решаемой задачи. Ниже приводятся графики зависимости точности кластеризации от числа признаков, описывающих выборку, при разном числе кластеров.
При проведении экспериментов результаты, полученные в результате применения предлагаемых в данной работе подходов, сравнивались с результатами метода основанного на принципе максимума правдоподобия. Данный метод является одним из наиболее известных классических методов нахождения параметров плотности распределения объектов. Его свойства исследовались в большом количестве работ зарубежных и отечественных исследователей [24,25].
На прилагаемых графиках по оси «X» откладывались количество признаков, которые имела кластеризуемая выборка, а по оси «Y» количество правильно классифицированных элементов в процентах. Для построения каждой точки проводились исследования набора из 10 выборок, которые были созданы генератором по одним и тем же параметрам. Значение процента правильно классифицированных объектов является средним значением по всем выборкам с одинаковыми параметрами.
Как видно из приведенных графиков при малом количестве признаков (до 20) самые лучшие результаты дает метод максимального правдоподобия. При возрастании количества признаков на первое место выходит метод коллективных к-средних. Комитетный синтез показывает результаты, которые примерно на 10% хуже других рассматриваемых методов.
Важной характеристикой любого метода является его устойчивость. Поэтому были проведены численные эксперименты, направленные на исследование устойчивости рассматриваемых в данной работе подходов. При проведении исследований результаты представляемых методов так же сравнивались с результатами метода максимального правдоподобия. Вычисления проводились для выборок, состоящих из десяти классов, при возрастающем числе признаков. Для каждого значения количества признаков обрабатывались по тридцать выборок объектов. На графиках изображены в виде точек полученные значения правильно распознанных объектов. В виде линии отображено среднее значение полученных результатов.
Как видно из приведенных графиков, для рассматриваемого интервала значения количества признаков наиболее устойчивым является метод коллективных к-средних, далее следует метод максимального правдоподобия, а затем комитетный синтез.
Сравнительные эксперименты на реальных задачах
В настоящем параграфе приводятся результаты применения описанных в работе подходов на реальных данных из различных предметных областей. Данные были взяты из открытых источников (публикации, Интернет). Вычисления проводились по следующему алгоритму. Сначала строился коллектив базовых решений путем восстановления одномерных компонент выборки объектов с использованием подхода, основанного на генетическом алгоритме. Далее строилось коллективное решение над полученными результатами одномерного анализа выборки. Для сравнения использовался алгоритм, основанный на принципе максимума правдоподобия. В целях пояснения структуры решаемых задач, приводятся проекции выборок на плоскость обобщенных признаков. Проекция строится таким образом, что бы метрические отношения между проекциями объектов в пространстве R2 максимально соответствовали метрическим отношениям объектов в исходном пространстве R".
Задача одобрения кредита. Задача состоит в оценке платежеспособности клиента банка при выдаче ему кредитной карты. Клиент описывается набором из 15 признаков, среди которых есть вещественнозначные, &-значные (к 2), бинарные. Выборка объектов состояла из 342 объектов, некоторые из которых имели пропуски в признаковом описании. Выборка состояла из двух классов включающих в себя 152 и 190 объекта. Двумерная проекция выборки на плоскости 2 и 14-ого признаков имела следующий вид:
В результате анализа выборки метод максимального правдоподобия правильно кластеризовал 73% объектов. Метод коллективных к-средних показал результат 75%, а комитетный метод - 80%.
Задача диагностики рака. Задача состоит в диагностике заболевания раком. Пациенты описываются набором из 9 &-значные (k = 10) признаков. Выборка объектов состоит из 344 объектов и является смесью двух кластеров - легкая степень заболевания (218 объектов) и тяжелая степень заболевания (126 объектов). Как и в предыдущем примере, выборка анализировалась методом максимального правдоподобия и методами построения коллективных решений на базе одномерных кластеризации
Сравнительные эксперименты на реальных задачах
В настоящем параграфе приводятся примеры результатов практического применения системы РАСПОЗНАВАНИЯ в различных предметных областях. Рассматриваемые прикладные задачи были исследованы с различной степенью глубины. Значительная часть данных была взята из открытых источников (публикации, Интернет) или была предоставлена коллегами и знакомыми. Полученные в данных случаях результаты разовых расчетов являются, как правило, «поверхностными», а точность прогноза может быть невысокой. Как правило, подобные результаты можно существенно улучшить, уточнить и доработать при более детальном ознакомлении с предметной областью или, тем более, совместном решении данных задач с их постановщиками.
Следует отметить очевидную истину: точность распознавания и прогноза, выявленные закономерности непосредственно зависят от практической постановки задачи, качества и количества имеющихся данных. Если не существует в действительности детерминированной или статистической связи между имеющейся системой признаков и распознаваемым свойством (параметром, характеристикой, объектом, ситуацией, и т.п.), то наивно рассчитывать найти то, чего не существует.
Оценка стоимости квартир. Задача состоит в автоматической оценке стоимости квартир по ее внутренним и внешним характеристикам (жилая площадь, строительный материал дома, местонахождение, этаж, удаленность от станции метро и др.). Применение методов оценки стоимости жилья по имеющимся выборкам прецедентам (совокупность расширенных описаний некоторого множества квартир плюс цена их продаж) позволяет проводить беспристрастную, независимую и точную оценку стоимости. Под расширенным описанием квартиры понимается весь стандартный комплекс параметров, которые обычно являются ценообразующими.
Примером подобной постановки является оценка стоимости жилья в пригородах Бостона [78]. Задача автоматической оценки стоимости жилья решается как задача распознавания интервала его стоимости (очень низкая, низкая, средняя, выше средней, высокая). В качестве признаков используются 13 экологических, социальных, технических показателей: число жилых комнат, доля чернокожего населения в районе, среднее расстояние до основных супермаркетов, качество воздуха и др. Для обучения использована выборка из 242 объектов, для контроля - выборка из 264 объектов.
Точность распознавания составила 77%, причем практически все ошибки были связаны с отнесением объекта в соседний класс, что естественно в силу искусственного разделения на классы. Количество грубых ошибок (отнесение не в соседний класс) составило менее 1%. Примером логической закономерности-класса наиболее дешевого жилья является конъюнкция (6.63724 = «концентрация окислов нитратов/10000000») & (1.129б = «среднее расстояние до пяти центров занятости Бостона» =2.44939) & (0,32 = «Признак В» =13.692) & (1.73 = «Процент населения низшего статуса»), выполненная на 12 из 16 эталонах первого класса. «Признак В» определяется выражением 1000(Вк -0.63)Л2, где Вк есть доля чернокожего населения.
Распознавание сортов вина. Настоящая задача является примером задачи контроля продукции пищевой индустрии. Подобные задачи могут найти широкие применения также при распознавании фальсифицированной продукции. Задача распознавания сортов вин по химическому анализу относится к хорошо поставленным задачам с легко отделимыми классами. Реальную ценность могут иметь результаты, в которых процент правильно распознанных объектов приближается к Ї00%. В данном примере исследуется выборка, объектами которой являются результаты химического анализа, выраженные в 13 признаках, таких как содержание алкоголя, яблочной кислоты, магния, цветовой оттенок и другие. Выборка разбита на 3 класса, соответствующих 3-м сортам вина, изготовленным из винограда, выросшего в одном и том же регионе Италии. Точность распознавания различными алгоритмами в режиме скользящего контроля составила 87.6-97.2%% правильных ответов, причем наилучшую точность показал метод «линейная машина». Примечание: Автор постановки задачи и данных - Forina, М. et al, PARVUS - An Extendible Package for Data Exploration, Classification and Correlation. Institute of Pharmaceutical and Food Analysis and Technologies, Via Brigata Salerno, 16147 Genoa, Italy.
