Функционалы качества разбиения. Критерии определения оптимального числа классов

При использовании различных методов кластерного анализа для одной и той же совокупности могут быть получены различные варианты разбиения. Существенное влияние на характеристики кластерной структуры оказывают, во-первых, набор признаков, по которым осуществляется классификация, во-вторых, тип выбранного алгоритма. Например, иерархические и итеративные методы приводят к образованию различного числа кластеров. При этом сами кластеры различаются и по составу, и по степени близости объектов. Выбор метрики расчета расстояния также влияет на результат разбиения. Возникает задача выбора «лучшего» разбиения. С этой целью вводится понятие так называемого функционала качества разбиения , где – результат разбиения объектов на p классов.

Под наилучшим разбиением понимается то разбиение, на котором достигается экстремум выбранного функционала качества. Выбор того или иного функционала качества, как правило, осуществляется весьма произвольно и опирается скорее на эмпирические и профессионально-интуитивные соображения, чем на какую-либо строгую формализованную систему. Рассмотрим наиболее часто используемые функционалы качества.

1. Сумма внутриклассовых дисперсий:

,

где – число классов;

– l -ый класс в классификации ;

– центр класса .

2. Сумма попарных внутриклассовых расстояний между объектами:

.

3. Обобщенная внутриклассовая дисперсия:

,

где – оценка дисперсии -ого признака в l -ом классе.

При использовании методов кластерного анализа возникает задача определения оптимального количества классов. Частично это позволяет сделать уже визуальный анализ дендрограммы: например, довольно большой разрыв между уровнями, соответствующими разбиению на и разбиению на классов говорит о том, что оптимальное количество классов равно . Можно использовать и более формальные критерии, которых в литературе известно более тридцати. Исследования показали, что одними из наиболее эффективных являются индекс Калински и Харабаза и индекс Дуды и Харта.

Индекс Калински и Харабаза сравнивает степень «разброса» данных внутри кластеров и между кластерами и рассчитывается как скорректированное на количество классов p и объем выборки n отношение следа матрицы межгруппового рассеяния В к следу матрицы внутригруппового рассеяния W:

.

То значение , при котором индекс принимает максимальное значение, и есть оптимальное количество классов.

Для расчета можно также использовать формулу следующую формулу:

,

где ,

– сумма квадратов расстояний от объектов до центров их классов;

– количество объектов в классе , ;

– среднее значение j -го признака в классе , ;

– сумма квадратов расстояний от объектов до общего среднего;

– среднее значение -го признака, .

Чем больше значение данного индекса, тем лучше разделены классы.

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

4.2 Дискриминантный анализ

Дискриминантный анализ, в отличие от кластерного анализа, предназначен для решения задачи «классификации с обучением», состоящей в отнесении каждого из заданного множества объектов к одному из заранее известных классов. Решение этой задачи требует наличия помимо статистической информации об объектах классификации обучающих выборок, т.е. объектов, для которых априори известно, к какому классу они принадлежат. При этом под классом в дискриминантном анализе понимается генеральная совокупность, описываемая одномодальной плотностью распределения (или одномодальным полигоном распределения вероятностей в дискретном случае).

Итак, ставится задача отнести каждый из n объектов, подлежащих классификации, к одному из p классов. Исходная информация для решения задачи состоит из двух частей:

1) матрица типа «объект-свойство», содержащая информацию о значениях признаков для n объектов, подлежащих классификации,

,

где – наблюдаемое значение j -го признака для i -го объекта выборочной совокупности, , ;

2) обучающие выборки , Относительно объектов известно, что они принадлежат j -му классу и каждый из объектов характеризуется наблюдаемыми значениями k признаков : , . Статистическую информацию об объектах j -ой обучающей выборки можно представить в виде матрицы типа «объект-свойство»:

,

Основной принцип вероятностных методов классификации заключается в следующем: объект следует отнести к тому классу (т.е. к той генеральной совокупности), в рамках которого он выглядит более правдоподобным. Иллюстрация этого принципа для случая , представлена на рисунке 4.6. На рисунке и – плотности распределения первого класса и второго классов соответственно.

Правило классификации для проиллюстрированного случая можно сформулировать следующим образом: если , то объект следует отнести к первому классу, а если – то ко второму. Таким образом, всю числовую ось можно разбить на два интервала: – множество значений признака для объектов первого класса и – множество значений признака для объектов второго класса.

и – площади соответствующих фигур на графике

т.к. , то

Рисунок 4.6 – Графическая интерпретация принципа классификации в дискриминантном анализе

Для того чтобы рассмотренный принцип классификации практически реализовать, необходимо располагать полным описанием классов, т.е. знать закон распределения генеральных совокупностей, например, в форме плотности распределения вероятностей , Знание плотностей распределения классов позволяет находить условные вероятности отнесения объекта i -го класса к классу с номером j: . Так, в нашем примере, – вероятность отнесения объекта ко второму классу при условии, что он принадлежит первому классу.

Сформулированный принцип классификации может корректироваться с учетом удельных весов классов и потерь от неправильной классификации объектов [12].

Очевидно, что методы классификации желательно строить так, чтобы минимизировать потери от неправильной классификации объектов. Обозначим через потери, которые мы несем при отнесении одного объекта i -го класса к классу с номером j, . При . Если в процессе классификации объект i -го класса будет отнесен к классу с номером j раз, то потери составят , а величина общих потерь тогда определяется следующим образом:

. (4.1)

Для того чтобы потери не зависели от числа n классифицируемых объектов (а величина будет расти с ростом n), перейдем к удельной характеристике потерь, разделив обе части выражения (4.1) на n и перейдя к пределу по :

. (4.2)

Предел в выражении (4.2) следует понимать в смысле сходимости по вероятности величины к – вероятности отнесения объекта i -го класса к классу j и величины к – вероятности извлечения объекта i -го класса из общей совокупности объектов. Величину называют априорной вероятностью или удельным весом i -го класса.

Величина определяет средние потери от неправильной классификации объектов i -го класса. Тогда средние удельные потери от неправильной классификации всех анализируемых объектов составляют: . Средние удельные потери C называют также функционалом среднего риска, характеризующим ожидаемую величину потери при классификации объектов тем или иным алгоритмом (процедурой) классификации.

Часто полагают, что потери одинаковы для любой пары i и j, т.е. , . В этом случае стремление минимизировать средние удельные потери C будет эквивалентно стремлению максимизировать вероятность правильной классификации объектов равной . Докажем это:

Действительно, получили, что средние удельные потери C будут минимальны при максимальной вероятности правильной классификации .

Перейдем к построению процедуры классификации, т.е. решающего правила отнесения объекта, характеризующегося многомерным вектором признаков , к j -му классу. Решающее правило может быть задано разбиением k -мерного пространства действительных чисел на p непересекающихся k -мерных областей . Процедура классификации называется оптимальной (байесовской), если она сопровождается минимальными потерями (4.2.2) среди всех других процедур классификации.

Теорема. Процедура классификации , при которой потери (4.2) будут минимальными, определяется следующим образом [12]:

. (4.3)

Доказательство. Для любых классов и . Преобразуем выражение для средних удельных потерь C следующим образом:

Так как , то

где , , .

Таким образом, функционал С представляет сумму слагаемых , каждое из которых зависит от области . Минимум достигается, если подынтегральное выражение отрицательно при всех , т.е. . В силу произвольности s следует, что . Но это и означает, что

.

Таким образом, объект следует отнести к классу j, когда средние удельные потери от его отнесения именно в этот класс окажутся минимальными по сравнению с аналогичными потерями, связанными с отнесением этого объекта в любой другой класс.

Часто полагают, что величина потери зависит только от того, к какому классу относится объект, а не от того, к какому классу он был ошибочно отнесен: . В этом случае оптимальное правило классификации упрощается. Для любых j и s получаем:

Следовательно,

.

Тогда аналогично доказательству теоремы получаем, что правило отнесения объекта к j -му классу формулируется следующим образом: . Тогда можно записать, что

.

В случае равных потерь , правило классификации приобретает еще более простой вид:

, (4.4)

т.е. максимизируется «взвешенная правдоподобность» объекта, характеризующегося вектором признаков , в рамках класса, где в качестве весов выступают априорные вероятности [12].

На практике важно не только классифицировать объект, но и вычислить с какой вероятностью он принадлежит каждому из классов, ведь одно дело, когда объект с высокой вероятностью относится к одному из классов, и совсем другое – когда объект находится на границе классов. Для этого рассчитывают апостериорные вероятности отнесения объекта в i -ый класс, позволяющие оценить величину ожидаемых потерь, связанных с классификацией рассматриваемого объекта.

Так как под i -ым классом понимается генеральная совокупность с одномодальной плотностью распределения вероятностей , то классифицируемые наблюдения в дискриминантном анализе интерпретируются как выборка из генеральной совокупности , представляющей собой смесь p классов, с плотностью распределения , где – плотность распределения i -ого класса, – априорная вероятность появления объекта i -ого класса или удельный вес объектов i -ого класса в общей генеральной совокупности, .

Выведем плотность распределения смеси для случая , . Пусть и – плотности распределения первого и второго классов соответственно. Найдем вероятность события А, состоящего в том, что объект, характеризующийся значением признака, равного , принадлежит интервалу длиной . Для этого выдвинем гипотезы: – интервал принадлежит множеству значений x, относящихся к первому классу; – интервал принадлежит множеству значений x, относящихся ко второму классу.

Тогда согласно формуле полной вероятности получаем:

.

Этот результат можно записать иначе:

при .

Сократив левую и правую части полученного равенства на , получаем:

.

Тогда, в общем случае, можно записать, что плотность распределения смеси p классов имеет вид: .

Апостериорные вероятности вычисляются по формуле Байеса: . Именно поэтому рассматриваемые процедуры классификации называются байесовскими. Тогда ожидаемые потери при классификации объекта в j -ый класс составят . Если , тогда . Если , то .

Оптимальный алгоритм классификации можно записать через апостериорные вероятности: объект относится к классу j, если . Это правило называется принципом максимума апостериорной вероятности. Можно было бы с самого начала принять принцип максимума апостериорной вероятности в качестве исходного постулата. Мы же исходили из принципа минимума среднего риска (минимума средних удельных потерь), что позволило доказать оптимальность байесовского алгоритма и обобщить его на случай произвольной матрицы потерь.

Для того, чтобы его реализовать правило классификации (4.4), необходимо знать априорные вероятности и законы распределения классов , . В статистическом варианте решения задачи классификации перечисленные характеристики заменяются оценками, рассчитанными по обучающим выборкам.

Если данные, составленные из всех обучающих выборок, можно считать случайной выборкой объемом , то оценки удельных весов классов , , можно рассчитать по формуле: .

Задача оценки законов распределения классов , , решается по-разному в зависимости от следующих случаев:

1) параметрический дискриминантный анализ: вид функций , , известен, не известны параметры распределения классов. В качестве оценки в этом случае выступает , где – оценки параметров распределения i -го класса, рассчитанные по i -ой обучающей выборке;

2) непараметрический дискриминантный анализ: вид функций , , не известен. В этом случае строят непараметрические оценки функций , например, гистограммного или ядерного типа.

Рассмотрим параметрический дискриминантный анализ в случае нормального закона распределения классов. Пусть i -ый класс () – это k -мерная нормально распределенная генеральная совокупность с вектором математических ожиданий и ковариационной матрицей общей для всех классов. Необходимо построить правило отнесения объекта, характеризующегося вектором признаков , в один из p классов [12].

Перепишем правило классификации (4.4) следующим образом: объект относится к классу j, если

. (4.5)

Прологарифмируем левую и правую часть выражения (4.5):

. (4.6)

В случае нормального закона распределения классов плотность распределения () имеет вид:

. (4.7)

Подставим (4.7) в выражение (4.6) и проведем следующие преобразования:

;

;

.

Таким образом, правило классификации (4.4) в случае нормального закона распределения классов с равными ковариационными матрицами формулируется следующим образом: объект относится к классу j, если:

. (4.8)

Для реализации правила классификации (4.8) необходимо знать параметры распределения классов , и удельные веса классов , . Если перечисленные характеристики не известны, то на основе обучающих выборок рассчитываются их оценки , , , где – среднее значение l -го признака, рассчитанное на основе i -ой обучающей выборки, . Оценка ковариационной матрицы, общей для всех классов, рассчитывается по формуле:

,

где – несмещенная оценка ковариационной матрицы, рассчитанная на основе i -ой обучающей выборки.

Тогда правило классификации (4.8) в выборочном случае формулируется следующим образом: объект относится к классу j, если

. (4.9)

Правило классификации (4.9) можно преобразовать к виду:

.

Таким образом, каждому i -му классу ставится в соответствие линейная дискриминантная функция Фишера вида:

, ,

где ;

.

Тогда объект относится к классу j, если .

Рассмотрим геометрическую интерпретацию дискриминантного анализа в случае нормального закона распределения классов. Пусть , , , . Тогда согласно правилу (4.9) объект относится к первому классу если:

. (4.10)

Геометрическая интерпретация правила (4.10) представлена на рисунке 4.7.

Рисунок 4.7 – Геометрическая интерпретация дискриминантного анализа в двумерном случае

Знак в левой части неравенства (4.10) зависит от угла . Если угол , как на рисунке, тупой, то , следовательно, объект относится ко второму классу. Таким образом, все объекты, лежащие слева от прямой, перпендикулярной вектору и проходящей через его середину, относятся ко второму классу, а все объекты, лежащие справа от прямой, относятся к первому классу. Прямая наилучшим образом разделяет два класса объектов и называется дискриминантной прямой [25]. Уравнение этой прямой имеет вид:

,

где – вектор коэффициентов дискриминантной прямой.

Найдем величину С, называемую константой дискриминации:

;

.

Таким образом, константа дискриминации С рассчитывается по формуле:

Используя полученные результаты, правило классификации (4.10) принимает вид: объект относится к первому классу если:

;

;

или .

Снимая ограничения на число признаков, удельные веса классов и ковариационную матрицу, объект относится к первому классу если:

.

Дискриминантная функция в k -мерном случае имеет вид: , где вектор коэффициентов дискриминантной функции определяется следующим образом: . Уравнение плоскости (гиперплоскости), разделяющей два класса, имеет вид: . Константа дискриминации С рассчитывается по формуле: , где , . По-прежнему, если , то объект относится к первому классу, иначе – ко второму.

Замечания:

1. дискриминантная функция является линейной в случае нормального закона распределения классов, в общем случае она может быть и нелинейной. Это зависит от геометрического расположения разделяемых классов в пространстве дискриминантных переменных;

2. если заранее не известно, что , то предварительно необходимо проверить гипотезу о равенстве ковариационных матриц генеральных совокупностей.

Пример решения задачи на тему «Параметрический дискриминантный анализ»

Деятельность предприятий машиностроительной отрасли характеризуется двумя показателями:

– рентабельность, %;

– производительность труда, тыс. р./чел.

По двум обучающим выборкам объемами 60 и 40 из генеральных совокупностей, распределенных по нормальному закону с равными ковариационными матрицами, рассчитаны оценки векторов математических ожиданий и ковариационных матриц:

; ;

; .

Предприятия первого класса характеризуются высоким уровнем организации управления производством, предприятия второго класса – низким уровнем организации управления производством. К какому классу относится предприятие, рентабельность которого составляет 14%, а производительность труда – 6, 5 тыс. руб. на одного человека, если потери от неправильной классификации объекта первого класса во второй и наоборот равны.