|
p align="left">Алгоритм ядерной аппроксимации функции плотности распределения имеет следующий вид: 1 Задается множество точек ; 2 Полученное множество точек упорядочивается по возрастанию: ; 3 Определяется «ядерная» аппроксимация функции плотности распределения: (1.9) где - количество точек исходной выборки, попавших в интервал . Замечание: значение k берется из интервала [3; 7]. 1.1.3 Оценка функции распределения с помощью нормальной вероятностной бумаги. Пусть даны N наблюдений x1,...,xN, извлеченные из генеральной совокупности с функцией распределения F(t). Этап 1. Исходная выборка значений упорядочивается по возрастанию. В результате получается последовательность x(1) ,..., x(N). Этап 2. Для каждого значения x(i), на плоскости отмечается точка (x(i), i/N) (см. рисунок 1.1). Для того чтобы определить расположение этой точки, находится значение Vi=Ф-1(i / N), которое откладывается по оси V. Рисунок 1.1 - Нормальная вероятностная бумага Этап 3. Если точки (х(i) ,i/N) в какой-то мере ложатся вдоль некоторой прямой, то можно грубо считать генеральную совокупность, из которой извлечена данная выборка, нормальной. В противном случае надо подыскать преобразование переменной, например, логарифмирование, извлечение корня и тому подобное, в результате которого выборка бы соответствовала нормальному распределению. Этап 4. В случае принятия гипотезы о нормальности распределения осуществляется оценка параметров распределения. В качестве оценки центра берется медиана выборки, которая соответствует вероятности р=0.5. Оценка стандартного отклонения , где - оценка 0.84 квантиля распределения, полученного при V=1. 1.2 Основные теоретические сведения по теории классификации1.2.1 Основные понятия кластерного анализа и проблема измерения близости между объектами. В общем виде задачу классификации исследуемой совокупности объектов O={Oi}, , где для каждого объекта замерены значения p параметров, т.е. каждый объект Oi описан вектором Xi = (xi1,...,xi), можно сформулировать как задачу поиска такого разбиения S заданной совокупности на непересекающиеся классы S1,....,Sk: , Si Sj = , ij , (1.10)при котором функционал качества Q(S) достигает экстремального значения на множестве A допустимых правил классификации [6]. В качестве Q(S) используют критерии, минимизирующие межгрупповое сходство и одновременно максимизирующее внутригрупповое сходство. Состав множества A зависит от предварительной (априорной) выборочной информации об этих классах. Итак, задача классификации формально сводится к нахождению разбиения S*.Q(S*) =min Q(S), S A (1.11) Заметим, что при этом число k может быть и неизвестно. При любых трактовках кластеров и для различных методов классификаций неизбежно возникает проблема измерения близости объектов. С этой проблемой связаны следующие трудности: неоднозначность выбора способа нормировки и определения расстояния между объектами. Нормировка представляет собой переход к некоторому единообразному описанию всех признаков и связана с введением новых единиц измерения, допускающих формальное сопоставление объектов. Перечислим наиболее распространенные способы нормирования показателей (переход от исходных значений x к нормированным z): z1 = (x -) / , (1.12) z2= x /, (1.13) z3=x / x , (1.14) z4=x / xmax, (1.15) z5=(x-)/ (xmax - xmin), (1.16) где , - среднее и среднеквадратичное отклонение x, соответственно; x - некоторое эталонное (нормативное) значение x; xmin , xmax - наименьшее и наибольшее значения x. (1.17) Расстоянием (метрикой) d между объектами a и b в пространстве параметров называется такая величина d(a,b), которая удовлетворяет аксиомам: A1.d(a,b)>0, d(a,a)=0 (рефлексивность); (1.18) A2.d(a,b)=d(b,a) (симметричность); (1.19) A3.d(a,b)+d(b,d) d(a,b) (правило треугольника) (1.20) Рассмотрим основные способы определения близости между объектами для количественных шкал. 1 Линейное расстояние: (1.21) 2 Евклидово расстояние: (1.22) 3 Обобщенное степенное расстояние Минковского: (1.23) 4 Расстояние Махаланобиса: , (1.24) где Xi = (xi1,...,xip); W = (ij), элементами которой являются: - ковариационная матрица. Содержательно линейное расстояние (1.21) оправдано, например, при многокритериальной оценке качества продукции, при нормировке по эталонам типа z3 (1.14), при определении расстояния между домами по кварталам. С его помощью лучше всего выделяют «плоские» классы, расположенные почти на гиперплоскостях, особенно, если они ортогональны каким-либо координатным осям. Евклидово расстояние (1.22) является самой популярной метрикой в кластер-анализе. Оно отвечает интуитивным представлениям о близости. Геометрически оно лучше всего объединяет объекты в шарообразных скоплениях, которые типичны для слабо коррелированных совокупностей. Обобщенное степенное расстояние (1.23) представляет интерес, как математическая универсальная метрика. Расстояние Махаланобиса является своеобразной конструкцией. Если считать, что все признаки не коррелированны (т.е. ij=0, ij), то , где - разница значений i-го признака у 2-х объектов, т.е. на каждой оси расстояние уменьшается пропорционально дисперсии. Это приводит к своеобразному уравниванию признаков, напоминающему процедуру нормирования z1 (1.12). Другая особенность этого расстояния в его «контекстном» характере. Матрица ковариаций W в формуле (1.23) делает расстояние между двумя точками зависимым от расстояний между другими точками. Рисунок 1.2 - Общая схема выбора способа измерения близости между объектами На рисунке 1.2 приведена общая схема определения способа измерения близости между объектами. 1.2.2 Типы методов кластер - анализа. Существует огромное количество алгоритмов кластер - анализа. Они отличаются вычислительными приемами и концепциями [1,6].Точной постановки задачи кластер - анализа нет. Единая теория находится в стадии становления. Для создания теории необходимо уметь учитывать разные конфигурации точек и предъявляемые к разбиениям требования.Требования к хорошей классификации формируются двумя способами: в терминах определений отдельных кластеров; в виде некоторого функционала, оптимальное значение которого соответствует лучшей классификации.Ниже на рисунке приведены сочетания классов на плоскости, которые трудно четко разделить, так как необходимо учитывать разнообразные обстоятельства: расстояние между точками класса C больше, чем межклассовые расстояния некоторых точек в классах В и С, среднее значение в классах Е и F, K и H одинаковы; классы P и Q соединены цепочкой, которую надо выделить.Рисунок 1.3- Сочетания классов на плоскостиПрежде чем строить теорию, учитывающую подобные конфигурации точек, надо осознать природу требований, предъявленных к разбиениям. Границы классов на рисунке 1.3 приведены именно такими в соответствии с интуитивными представлениями о том, что кластер - скопление точек - представляет собой некоторую целостность (образ), чем-то отличающийся от другого скопления точек. Причем кластеры могут касаться друг друга (B и C, L и M) и пересекаться (K и H). Различать подобные кластеры формальным образом трудно. Это означало бы машинную реализацию чисто человеческого процесса распознавания образов.40-летние попытки решить задачу «структурной классификации» привели к тому, что традиционную для статистики проблему выделения однородных групп стали называть распознаванием образов без учителя (самообучением).Основой 1-го направления решения задачи структурной классификации является: ѕ формулировка понятия кластера в смысле такого скопления точек, которое обладает некоторым свойством, например, в котором среднее межточечное расстояние меньше среднего расстояния от данных точек до остальных;ѕ разбиение совокупности на части, представляющие собой кластер.Алгоритмы, ориентированные на кластеры с заранее заданными свойствами, называют процедурами прямой классификации. Сам подход называют эвристическим, но некоторые алгоритмы находят локальный экстремум определенному функционалу.Требования к хорошей классификации предъявляют не только в терминах определения отдельных кластеров.Они могут быть сформулированы в виде некоторого функционала, экстремальное значение которого соответствует наилучшей классификации. Это второе - оптимизационное направление. Здесь возникает чисто математические проблемы, определение свойства функционала, путем достижения оптимума, трудоемкости алгоритма. Редко в этих задачах нужен глобальный оптимум.В кластер - анализе нет четкой связи между функционалом и действительной целью исследователя, так как она не может быть точно сформулирована в условиях исходной неопределенности в данных.Эти два подхода: прямой и оптимизационный являются разными способами формализации представления о хорошей классификации.Было выявлено, что некоторые эвристические процедуры оптимизируют определенные функционалы. Резкой границы между подходами нет, наоборот есть предположение, что каждая прямая процедура на самом деле доставляет экстремум какой-то функции, которую надо отыскать. И каждому функционалу соответствует свое определение кластера.1.2.3 Систематизация алгоритмов. Ее приходится вести по нескольким качественным признакам.1 Характер отношений, которые отыскиваются как результат классификации.1.1 Разбиение с непересекающимися классами (отношение эквивалентности). Объекты внутри класса тождественны, объекты разных классов нет.1.2 Разбиение с пересекающимися классами. Задаются по-разному: введение степени принадлежности объекта к классу в духе теории размытых множеств, определением вероятности принадлежности объекта к классу или перечнем объектов в зоне пересечения.1.3 Иерархическое дерево Процедуры классификации отыскивают целую систему вложенных разбиений. С их помощью получают и обычные разбиения, задав число классов, порог...2 Степень участия человека в процедуре выделения кластеров.2.1 Человек не принимает участия в работе алгоритма, т. е. машинным способом получается готовый результат, в процессе работы алгоритма он не вмешивается.2.2 Человек участвует в процессе получения разбиения. ЭВМ выдает информацию, по которой человек принимает решение о разбиении (Это метод визуализации).3 Характер априорных сведений (задаваемых параметров) для работы алгоритма.3.1 Априорные сведения отсутствуют (свободная классификация). Их отсутствие необходимо для выделения естественной, а не навязанной структуры исходных данных. Очень мало таких алгоритмов, они имеют человеко-машинный характер.3.2 Задано число классов.3.3 Заданы пороговые значения величины близости объектов (классов).3.4 Заданы комбинированные сведения (число классов и пороги разных типов).4 Характер работы алгоритма. По способу построения классов: эталонный и неэталонный. По зависимости от порядка просмотра точек: последовательные и параллельные.4.1 Остановимся на делении алгоритмов по способу построения кластеров: эталонные и неэталонные. В процедурах эталонного типа на множестве объектов задается несколько эталонов - исходных зон, полей, с которых начинает работу алгоритм. После задания (машинного или человеко-машинного) эталонов алгоритм проводит классификацию, иногда меняя эталоны определенным способом.Существует множество процедур кластеризации, работающих по иному принципу: иерархические алгоритмы, процедуры диагонализации, разрезание графов.4.2 Другая особенность алгоритмов - зависимость результатов от порядка просмотра точек. Она характерна для эталонных алгоритмов.Есть процедуры, зависящие от порядка просмотра, например иерархическая. Задача определения трудоемкости алгоритмов изучена слабо. Общую классификацию процедур на быстры и медленные, требующие большой и малой памяти можно заменить делением на параллельные и последовательные процедуры.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8
|
