- •92 Двоенко с.Д. Методы анализа бмд
- •4. Задачи классификации и кластер-анализа
- •4.1. Постановка задач классификации и кластер-анализа
- •4.2. Байесовское решающее правило классификации
- •4.3. Вероятности ошибок байесовского классификатора
- •4.4. Формирование решающего правила как обучение распознаванию образов
- •4.5. Восстановление плотностей распределения классов
- •4.6. Восстановление функций степени достоверности
- •4.7. Минимизация среднего риска
- •4.8. Линейные разделяющие функции
- •4.9. Область решений линейной разделяющей функции
- •4.10. Алгоритмы построения разделяющих гиперплоскостей
- •4.11. Алгоритм построения оптимальной разделяющей гиперплоскости
- •4.12. Алгоритмы кластер-анализа
92 Двоенко с.Д. Методы анализа бмд
4. Задачи классификации и кластер-анализа
4.1. Постановка задач классификации и кластер-анализа
Пусть производятся наблюдения над некоторыми объектами , принадлежащими некоторой генеральной совокупности. Пусть каждый объектпоявляется случайно и независимо от другого и объективно принадлежит одному изmклассов. Требуется, при появлении очередного объекта, определить его принадлежность к одному из классов.
Заметим, что число Nнаблюдаемых объектов здесь принципиально не ограничено:, то есть решением задачи классификации должен быть способ определения принадлежности к некоторому классу каждого вновь появившегося объекта независимо от остальных. Такой способ реализуется в виде так называемого решающего правила.
Решающее правило представляет собой некоторую функцию , принимающую значения на множестве классов, гдепри. Пусть результат наблюдения объектапредставленn- мерным вектором. Тогда решающая функциядоступна нам в виде функции, причем мы хотим, чтобы выполнялось условиепри.
Наиболее общим подходом к решению задачи классификации является вероятностный подход к поиску решающего правила классификации. При вероятностном подходе предполагается, что в n-мерном пространстве заданаm- модальная плотность распределения вероятностей, где локальные максимумы плотности распределения характеризуют локальные сгущения объектов в пространстве. В данном случае областилокального сгущения объектов являются, вообще говоря, пересекающимися, накрывающими в совокупности все пространство, и не являются в этом смысле классами. Классификация порождается решающим правиломв виде непересекающихся областейтакже накрывающими в общем случае все признаковое пространство, гдепри.
Основой вероятностного подхода к поиску классификации методом принятия решения о классе объекта является байесовская теория принятия решений.
Но построение вероятностного решающего правила часто сопряжено с определенными практическими трудностями, так как требует полного знания всех соответствующих распределений вероятностей или их параметров. Если ввести упрощающее предположение, что вероятностные меры сосредоточены в ограниченных областях признакового пространства, то для выработки решающего правила можно применить детерминистский подход. В этом случае предполагается, что области не пересекаются, то есть, и образуют разбиениеn-мерного пространства наmклассов. Для построения детерминистского решающего правила требуется лишь знание характеристик, описывающих взаимное расположение областейв признаковом пространстве.
Как уже упоминалось ранее, результаты совокупности наблюдений обычно представлены матрицей данных . Фиксированное число наблюденийNдает возможность построить классификацию данной совокупности изNобъектов не на основе решающего правила, а сразу, непосредственно перечислением номеров классов объектов. Методы построения классификации сразу перечислением решают так называемую задачу кластер-анализа. Особенность задачи кластер-анализа состоит в том, что ее решение получается при анализе одновременно всей совокупностиNнаблюдаемых объектов. Следовательно, методы кластер-анализа основаны на изучении характеристик взаимного расположения классов как локальных сгущений объектов в признаковом пространстве.
Но отсутствие явно заданного решающего правила приводит к необходимости вновь решать задачу кластер-анализа для всех Nнаблюдений при добавлении нового наблюдения к исходной матрице данных. При этом оказывается, что классификация ранее наблюденных объектов может измениться. Это приводит нас к проблеме устойчивости кластерного решения. При наличии решающего правила классификация ранее наблюденных объектов не изменяется, и их не требуется вновь анализировать - про них можно забыть.
Отметим далее, что при наличии решающего правила алгоритм классификации представляет собой простейшую процедуру отнесения объекта к тому классу, номер которого указан решающим правилом. При отсутствии решающего правила для получения классификации перечислением требуется разработать специальный алгоритм. Очевидно, что алгоритмов может быть много, в зависимости от того, что понимается под характеристиками взаимного расположения классов, а также от способов получения перечисления номеров классов. В свою очередь, разнообразие алгоритмов кластер-анализа приводит к тому, что на одних и тех же данных порождаются, вообще говоря, различные классификации. Добавим, что многие алгоритмы кластер-анализа довольно просты, что весьма привлекательно на практике, но результат их работы может и не иметь достаточного статистического обоснования.