Принятие решений

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

, (2.29)

где mS – центр класса

wS. Оптимальным вариантом классификации считается тот, при котором функционал Ф(Xj, mS) принимает наименьшее значение. Выбор такого критерия обосновывается распространенными интуитивными правилами «ручной» группировки. Обычно специалисты объединяют в одну группу объекты мало отличающиеся друг от друга или от «типичного» объекта (ближайшего к центру класса).

Из данной выборки (2.28) случайным образом отбирается k объектов, которые принимаются за центры классов, обозначим их через

.

Для каждого выбранного объекта находится ближайший элемент выборки Xic (ближайший сосед):

.

объединяются в один класс, если расстояние между ними не больше заданного порогового значения r0. При этом вычисляются новые центры классов. Если это расстояние больше r0, то выбранный объект образует новый класс. Если расстояние между центрами двух классов меньше другого априорно заданного порогового значения r'0 (r0 > r'0), то соответствующие классы объединяются.

Процесс продолжается до полного перебора точек множества (2.28). Результат классификации зависит от порядка первоначального выбора объектов исследуемого множества, от заданных пороговых значений r0, r'0. В качестве критерия качества классификации можно взять минимум функционала (2.29).

Этот алгоритм предназначен для выделения классов довольно причудливой формы (рис. 2.12), которые не может выделить ни один из алгоритмов семейства FOREL. На рис. 2.12 человек довольно легко выделит три класса, три таксона. При этом интересно установить, какие критерии качества таксономии он использует, как он определяет наиболее «естественное» число таксонов, их форму и границы. Ответив на эти вопросы, можно составить алгоритм, моделирующий действия человека, проводящего классификацию на плоскости. Естественно предположить, что человек использует некоторую меру близости точек r, считая, что таксономия тем лучше, чем меньше расстояние между точками одного таксона. Он тем увереннее делает таксономию, чем дальше одни группы близких точек отстоят от других групп, т.е. мера взаимной удаленности таксонов z тоже играет важную роль.

Психологические эксперименты показали, что человек не всегда объединяет точки в таксон по правилу: «ближний к ближнему».

На рис. 2.13 пятая по счету слева точка ближе к четвертой точке, чем к шестой. Однако при разделении этого множества точек на два таксона люди обычно проводят границу Г между четвертой и пятой точками. По-видимому, человек обращает внимание на локальные изменения (скачки) плотности точек l.

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

Эксперименты показали, что хорошее совпадение получается, если в основу алгоритма таксономии положить меры, использующие свойства кратчайшего незамкнутого пути (КНП). КНП – это граф, который соединяет все точки множества X(n) и при этом не имеет циклов, а сумма длин всех его ребер минимальна. Существует эффективный алгоритм построения КНП. Пример КНП для точек рис. 2.14а дан на рис. 2.14б.

а б

Если разрезать k-1 ребер КНП (т.е. удалить их), то будет выделено k таксонов. Мерой близости объектов внутри одного таксона можно считать среднюю длину ребер КНП, соединяющего все точки данного таксона,

, s = 1, 2, …, k,

где – длина i-го ребра, – число объектов в таксоне .Общей мерой близости внутренних точек таксонов будем считать среднюю длину всех внутренних ребер

.

Среднее расстояние между таксонами определяется по КНП как средняя длина ребер, соединяющих таксоны

.

Через КНП определяется и мера локальной «неоднородности» расстояний между точками li. Для каждого i-го ребра длины ai фиксируется прилегающее к нему ребро минимальной длины bmin, тогда

, i Î {1, 2, …, n – 1}.

Чем меньше li, т.е. чем больше различие в длинах соседних ребер, тем с большим основанием можно считать, что граница между таксонами пройдет по ребру ai.

Задается пороговое значение l0 < 1. Если

li < l0, i Î{1, 2, …, n-1}, (2.30)

то граница между таксонами пройдет по ребру ai, т.е.

, sÎ{1, 2, …, k-1}.

li, для которых выполняется условие (2.30), обозначим через . Тогда мера неоднородности на границах таксонов представима в виде

.

Общий критерий качества в алгоритме KRAB – максимум функционала

. (2.31)

Проверка на двухмерных примерах показала, что чем лучше таксономия, тем больше значение функционала V в (2.31).

Алгоритм КРАВ работает так. Вначале проводится КНП между всеми точками данного множества. Если число таксонов задано, то путем перебора находятся такие k-1 ребер, проведение границ по которым дает максимальное значение функционала V в (2.31).

Если число объектов и количество таксонов велико, перебор становится слишком трудоемким. Для его сокращения используется предварительный отбор ребер претендентов, по которым могут пройти границы. Это делается путем отбора таких ребер, для которых , – некоторое пороговое значение, которое варьируется. Из рассмотрения исключаются ребра, размер которых меньше ребер, примыкающих к ним.

 Скачать реферат