Алгоритм автоматической классификации объектов при априорно не заданном числе классов

Задача разбиения заданного множества объектов на непересекаюшиеся и непустые подмножества представляет собой задачу автоматической классификации объектов при априорно не заданном числе классов [2, 11,21]. Постановка 252

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

• - объекты внутри каждого класса должны быть максимально близки;
• - количество классов должно быть минимальным;
• - классы должны быть заполнены равномерно.

Каждый вариант формирования классов связан с известными потерями. В данном случае составляющими критерия качества классификации

Q=A(g)+ Q(m)+D(u) (4.29)

будут следующие функции потерь: 4(g) - от различия объектов внутри классов; Q(m) - от числа классов; D(v) - от разброса классов по мощности. Очевидно, что оптимальному варианту формирования классов соответствует минимум критерия качества классификации (30). Решение задачи автоматической классификации будем проводить на основе оптимизационной модели, минимизирующей критерий качества классификации <2. Для этого осуществим формализованную постановку задачи и рассмотрим вопросы построения оптимизационной модели. Функциональное состояние ТОУ описывается некоторой совокупностью параметров. Экспериментальные данные, полученные в результате проведения промышленных экспериментов, представляются в виде множества

и.= й¹. ,и'.= , <=А(г_;), г-Гк}, j=17, (4.зо)

где u_kj - значение к -го параметра, характеризующего / - й объект г, -го типа j -го признака (к = l,K_)t l = ,F, F = F(r_j))_

Введем в рассмотрение К, - мерное метрическое пространство, в котором каждому объекту по вектору значений его параметров ставится в соответствие точка в этом пространстве. Количественной характеристикой меры сходства или различия объектов естественно считать расстояние между соответствующими точками метрического пространства. Таким образом, группе однородных по совокупности параметров объектов соответствует компактное множество точек в этом пространстве. Способ вычисления расстояния определяется введенной в пространство метрикой. Выбор ее вида производится с учетом специфики классифицируемых объектов. Расстояние между / -м и q -м объектами /, <7 = 1, F, количественно характеризующее их различие, вычисляется по одпо-му из следующих выражений;

(4.31)

с,_ч=

• *=1
• (4.32)
• (4.33) где u'_kj, - нормированные значения к - го параметра / -го и q -го объекта со

ответственно; /к - коэффициент, характеризующий информативную значимость ("вес") к -го параметра.

Естественно, что приведенные выражения (4.31)- (4.33) нс исчерпывают всех способов вычисления величин C_lq, тем нс менее вопрос о выборе количественной меры различия будем считать решенным. В результате сформируем матрицу С =|| С_1(/1|, причем она будет симметричной (т.с. C_lq = C_ql), с нулевыми элементами на главной; диагонали (C_lf = 0), и все ее элементы неотрицательны (Q,>0 для V/,

Определение значений коэффициентов информативности /к представляет собой достаточно сложную задачу, имеющую самостоятельное значение, и в общем случае осуществляется на основе анализа степени неоднородности множества объектов по каждому параметру. В дальнейшем будем определять значения/* на основе подходов, изложенных в [33, 98].

Нормировка значений параметров объектов производится по одному из следующий выражений:

<-min(«p

Ц =--

max

(4.34)

и?: —min и?.

KJ KJ

^uh =

(4.35)

= _к

(4.36)

к -го па-

^ukj —

1 ^г

где u_kj = ^7 / . " среднее значение к -го параметра;

^F ц=

-11/2

среднеквадратическое отклонение

рамстра.

Каждому варианту разбиения множества U_j на классы ставится в однозначное соответствие булева матрица решений X =|| x_qi || с элементами

{1, если объект q отнесен к классу Z(/ = l,/n) п (4.37)

0, в противном случае.

Для рассмотрения процедуры разбиения множества объектов при априорно нс заданном числе классов введем булевы переменные w_m(m = 1,F):

{1, если число классов равно т;

_п (4.38)

0, в противном случае.

Общее различие между объектами внутри классов выражается следующим образом:

I F т F F Г

? = ^{г = 1}’ (4-39)

т= /=1 q= /=1 ш=1

Мерой разброса классов по мощности является дисперсии их мощностей. г

Поскольку мощность класса i равна Л ⁼ > дисперсия v мощностей классов

д=1

при априорно не заданном их числе определяется по формуле

m)

(4.40)

Количество классов определяется величиной пг.

F

т = V wvv„ т •

(4.41)

»г=1

Условие, что каждый объект 1(1 = 1,F): должен быть отнесен к одному и

только одному классу, приводит к ограничениям вида т ___

^Л„ = 1, l = ,F. (4.42)

1=1

Условие, требующее, чтобы число объектов в каждом классе i было не менее одного и не более (р, имеет вид

F F

/=1’Е,т'-’

(4.43)

/=1 т=1

где (р<(р<(р

F / tn, при F кратном tn;

F / tn +1, в противном случае;

(р = F - tn +1.

Условие, состоящее в том, что число классов должно быть однозначно определенным, имеет вид

F

Еи'» = 1-- (4-44)

т=1

Тогда в терминах дискретного программирования оптимизационная модель задачи классификации множества U_} при априорно не заданном числе

классов имеет вид

(4.45)

при ограничениях (4.42)-(4.44). Далее полагаем A(g) = g, Q(tn) = tn, D(v) = u.

Таким образом, задача классификации объектов при априорно нс заданном числе классов сведена к оптимизационной модели с целевой функцией (4.45) и ограничениями (4.42) - (4.44). Структурная схема построения оптимизационной модели приведена на рис.27.

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

Общее число вариантов разбиения множества объектов (7' = , I = 1, F, на априорно нс заданное число непустых нспсрссскающихся

F

классов равно (F, т), где 5 (F, т) - числа Стирлинга второго рода [56]: т=1

I ^,п n^F

5(Г,/ц) = -?(-1Г"-—L (4.46)

Даже при малых F их число очень велико, что делает нереальным полный перебор вариантов. В этих условиях необходим подход, позволяющий проводить направленный автоматический перебор.

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

[1, — (1, — — m = .F и д' = < / = 1, F, i = l,m

|0, " [О,

на случайные булевы переменные й’_т и л;,, имеющие следующие распределения:

P(w_m = О = А,.,. P(w_m = 0)^„_, + q^ = 1;

V 1 ГТ (4.47)

ЛА,„⁼¹> z» = 1. F;

/п=Г

В этих целях генерируется значение случайной величины ? , равномерно распределенной на интервале (0,1) [96]. Далее сравниваем < с р„. Если I < р,. , то т_к = 7; если ? > р„. , то сравниваем ? с р_ц. + р„,₂. Если |<р_н. + р„.,, то т„ = 2; если нет, то сравниваем ? с р_к< + p_w + р и т.д. до тех пор, пока /п„(п=1,77) не получит конкретного значения. Тогда w =1, остальные и>_ш = 0, т * (/» = 1, F)

Комбинации уровней варьируемых переменных х_Г1 формируются по аналогичной алгоритмической схеме, только в этом случае генерируется последовательность псевдослучайных чисел ?,(/ = 1, F). В результате будем иметь х_м=1, остальные х_п =0. = 1,F. i = Таким образом, формируемые

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

Управление перебором вариантов организуется с помощью объективных (по величинам приращений целевой функции) и субъективных 1 локальных прогностических оценок направления движения к экстремуму [51, 62]. С этой целью перестраиваются законы распределения (4.47) и (4.48), на основе которых моделируются реализации случайных булевых переменных й>„, и х_е.(т = 1,F, I = 1,F, i =

Объективные прогностические оценки при реализации вычислительной процедуры на ЭВМ будем получать из локальных улучшений для задач стохастической оптимизации.

Основой решения сформулированной выше задачи автоматической классификации при априорно не заданном числе классов является оптимизация псевдобулевой функции

Q(X, w)->min или -Q(X, и») —>max;

д-,(Х)<^, я,(Х)>1, i = Vm,

где X=[X^l,...,X',...,X^f], Х'=Ц,х₍₁,...,х_(/,...,х,_ш)

и' = [и'₁,...,и'_1г,...,и'_/.], I = ,F, i = m=l,F;

fl, fl,

[о. ^и’'^л~|о.

Для построения рандомизированной процедуры поиска решения заменим булевы переменные и», и х„ на случайные булевы переменные й’„, и х,,, имеющие распределения (4.47) и (4.48), т.е. перейдем от задачи (4.48) к ее вероятностному аналогу. Построение алгоритма решения будем проводить на основе подхода, изложенного в [31]. Но сначала для учета ограничений введем штрафную функцию Ла1ранжа в виде

Ф(Х, Г) = -Q(x, w) + ? У_и[<р- л, (X)] +

(4-49)

+Ег4^я’<<^х)-¹]’ /?1

где Г=[Г¹. Г²]. Г¹=(уц,..., у и,..., у₇,„), ^=('/21,..., y_2i,..., у_2т) - множители Лагранжа; уц, у₂,->0, i = 1, т .

Запишем конкретный вид функции Лагранжа для рассматриваемой задачи:

ф(%, D=-1 х ч, Ё Е Е ^хЛ^х« - Е ^mw'- ~ “ /П-1 Г=1 <7=1 /=1 Л1=1

-Ёх

m=l

nt

+Ё/2.'

r»l

nt

-E⁽E^x«^_“^{): +}E^ ^f-"^!+1-E^ ⁺ m~{ 77 m J н L mJ

Ex/.-1 ?

(4.50)

Поиск оптимальных значений булевых переменных x_{i осуществляется в соответствии со следующей итеративной процедурой:

Л /=/,„ i=i„ (4.51)

где л,, - случайная булева переменная, полученная на h - й итерации;

• 1 - случайная булева величина, играющая роль шага движения;
• 1 <т„ ^{- случайная булева функция.}

Случайные величины, определяющие направление движения, находятся из условия локального улучшения [103]

М Ф(Х'"') -М Ф(Х") >0;

.....X^f],x'^(A1'⁾=(X,_l,...,xr'--^„); (4.52) х" = [ ххX^F ], X= (x, x';₂,..., x,„)

Движение (4.52) в вероятностных характеристиках выполняется следующим образом:

р':¹=р':„+< [< «-(д;, ф) - р фи, 0.53) где Дд Ф - первая реализация случайной величины Д_/г- О ;

Д„Ф = Ф(Х‘/х‘=1)-Ф(%^Л/х,‘=0), /=/,„ / = /,;

Полный вероятностный алгоритм получается на основе объединения (4.53) и (4.56):

=< + {фд;,ф) - Р^х

хх(-д-² ФД‘Ф)]}[^«(Д* ф)-_р>(-А-' ф)]. ^{,4 >}''

Для эффективной работы данного алгоритма необходимо осуществлять управление выбором координат случайного вектора X =1 Х',...,Х' ,...,Х'J с целью определения направления поиска, т.е. выбором номера объекта I = 1, F, привлекаемого к дальнейшему поиску. Для этого введем булевы переменные

_z f 1, если объект с номером / привлекается к поиску

X ~ | —

[О, в противном случае (/ = 1,F).

Заменим их на случайные булевы переменные X', имеющие следующее распределение:

Р(Х' = 1) = р_г, Р(Х'=0) = _??, р_>; +?,,=!;

< , (4.58)

i-i

Для этого генерируется значение случайной величины ?, равномерно распределенной на интервале (0,1). Далее процедура реализуется по описанной алгоритмической схеме. В результате получаем X¹¹' =1, остальные Х'=0,/ = /„(/= Г7).

Процедура настройки вероятностей Р, (третий уровень вероятностного

алгоритма) с учетом условия локального улучшения имеет вид Р? = Р"' ⁺ Р>.’ ^ф^^ф) - Р" ^фА,’Ф)];

• (4.59)
• 1 = '^ i = i„

где А, - случайная булева величина, играющая роль шага движения I на третьем уровне; А₍’Ф - третья реализация случайной величины А₍,Ф.

На всех уровнях вероятностного алгоритма необходимо сохранение условий нормировки. Приведем порядок дополнительной обработки значений вероятностей на примере третьего уровня. Условием нормировки является ZX' ⁼¹’

/=1

А, - р¹', / p'Z', = G = p^q^'lG.

Т! (4.60)

I* In

На каждой итерации рассмотренного вероятностного алгоритма при вычислении реализаций случайной величины А,,Ф осуществляется выбор экстремального значения (рекорда) функции Ф*(л ,Г) и запоминаются значения слу чайных булевых переменных x_h(l = 1,F, i = 1,/и),, при которых получен рекорд. Данные значения будем использовать в качестве исходных для следующей итерации.

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

<+м. «'(д;, фд»-<«-(-д;, ф'^

, . . (4.61)

/ = i = t,, т=т„,

где 0,„ - случайная величина, играющая роль шага движения на четвертом уровне,

Д),Ф - первая реализация случайной величины Д,,Ф, полученная на (h + 1) -й итерации;

Д„Ф - четвертая реализация случайной величины Д_ЛФ, формируемая по значениям рекордов Ф'(X^м,Г) и Ф'(л ,Г), полученных на двух соседних итерациях.

Сохранение условия нормировки Р». ⁼' обеспечивается за счет до-И1=1

полнительной обработки значений вероятностей аналогично (4.60).

Рассмотренные вероятностные процедуры являются основой решения задачи автоматической классификации при априорно не заданном числе классов. Алгоритм решения данной задачи, структурная схема которого приведена на рис. 28-30 (соответственно первый, второй и третий сегменты), включает следующие этапы:

• 1. Предварительная обработка значений параметров состояния объектов, включающая определение коэффициентов информативной значимости параметров или их задание, нормировку значений параметров в соответствии с одной из формул (4.34) -(4.36) и формирование элементов матрицы расстояний С=||С„ || в соответствии с одной из формул (4.31)- (4.33).
• 2. Формирование значений случайных булевых переменных, имеющих, распределения (4.47), (4.48), (4.58), определение на этой основе числа классов, принадлежности объектов классам и направления поиска (выбор объекта, привлекаемого к поиску).
• 3. Формирование реализации случайной величины ДФ на основе вычисления значений целевой функции Ф(Х,Г) при направленно изменяемых значениях случайных булевых переменных Д,,. Определение экстремального значения (рекорда) целевой функции для каждого цикла оптимизации.
• 4. Вычисление коэффициентов для перестройки вероятностей случайных булевых переменных, перестройка вероятностей и их нормализация (реализация первых трех уровней алгоритма).
• 5. Реализация последнего уровня алгоритма, связанная с формированием четвертой реализации случайной на величины ДФ на основе значений рекордов целевой функции, полученных для двух соседних циклов оптимизации, а также с вычисленном коэффициентов и перестройкой вероятностей случайных булевых переменных, с помощью которых осуществляется выбор числа классов.
• 6. Сокращение числа классов за счет перераспределения объектов из малочисленных классов в ближайшие им классы, пересчет вероятностей распределения объектов между классами, которыми являются вероятности случайных булевых величин x_w(Z = l,F, i = l₉m). Пересчет организуется с учетом условия нормировки и состоит в равномерном распределении числовых значений вероятностей отнесения объектов к сокращаемым классам между значениями вероятностей отнесения объектов к оставшимся классам.
• 7. Расширение числа классов путем пересчета значений вероятностей отнесения объектов к классам, при этом вероятности отнесения объектов к новым классам задаются, как при равномерном распределении, и осуществляется нормировка значений остальных вероятностей. Случайным булевым переменным присваиваются значения, при которых было получено экстремальное значение целевой функции.
• 8. Циклы оптимизации повторяются вновь до тех пор, пока нс выполнится одно из трех условий останова, состоящих в следующем:
  • - число выполненных циклов оптимизации равно заданному;
  • - экстремальное значение целевой функции удовлетворяет заданным требованиям;
  • - относительное приращение значения целевой функции меньше заданного.

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

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

C = Or,ir) = minC,

(4.62) qeW^r,leW^s,

каждому варианту S разбиения множества объектов W -U = {U¹}(i = 1, F). на непустые нспсрссскающисся однородные классы поставим в соответствие некоторую функцию g(S).

При фиксированном числе классов L данная функция имеет вид

w(S) = fc(w;,u w,' (4.63)

/=| ^/о^ж>

где

C(W_l',UW') = C(WyW_l²_a,yW').

/₀ = 1 Г(|-1 /₀=1

Согласно требованию максимальной удаленности классов друг от друга необходимо, чтобы 97(5*) = max///(5).

Максимальное значение функции y/(S) будет соответствовать минимуму целевой функции Q (4.45). Очевидно, что max///(5) достигается при максимальных значениях членов суммы (4.63). Обозначим тах^//(5) через у//_|ОУ) и определим как

_У/_Л.,(1У) = max[C(W_t__I( W ^.,) + y/_t.₂(W И91

............................................................ (4.64) y/₁(lV) = maxCW,IVVV_I).

IV|CW

Таким образом, задача свелась к задаче динамического программирования, и для ее решения можно использовать алгоритм построения дерева кратчайших расстояний [88]. Данный алгоритм формирует конечный связный граф без петель, вершинами которого являются объекты, и вычисляет наименьшую сумму расстояний между ними. Разрезание дерева по ребрам максимальной длины приводит к получению искомых классов. Задача нахождения кратчайшего пути и определения его длины разбивается на следующие этапы:

• 1. Первой вершине // = 7 (работа алгоритма начинается с первого объекта) присваивается окончательный признак wj" =0 (нулевое расстояние до самой себя), а каждой из оставшихся вершин присваивается временный признак и><^п=оо, (/ = ГК /=/,).
• 2. На каждом h -м шаге вершине /_Л с временным признаком присваивается окончательный признак и вычисляются длины ребер, связывающие вершину с теми вершинами, для которых w, ⁰ > 0, (/= 1, F), причем, поскольку граф нс должен содержат петель, полагаем, что ^(С_/Л/А) = -1. Результатом является последовательность длин {w(C_//f/)}, где w(C_/A/) - длина ребра, соединяющего вершины l_h и I, Каждой вершине, не имеющей окончательного признака, присваивается новый временный признак, J определяемый по формуле
• 1г;^Л> = тт{и’;*^ч,,и<С,_ы)},(/ = Г7), /*/Л. (4.65)

Затем находится вершина q^ для которой и^>0, и ей присваивается окончательный признак = min w_g, после чего фиксируется номер вершины q_h и длина ребра. Процесс продолжается до тех пор, пока последней вершине не будет присвоен окончательный признак.

При разбиении множества объектов на заданное число классов L последовательно находим L - 1 ребро, длина каждого из которых больше или равна длине любого из оставшихся, и выбираем L - 1 вершину с максимальными значениями признаков. Пусть это будет Тогда в первую группу

попадут объекты с номерами во вторую - элементы с номерами

ИТ.Д.

Если разбиение множества объектов производится на априорно нс заданное число классов, то необходимо найти среднюю длину ребер w_{, а затем найти ребра и соответствующие им вершины, длины которых удовлетворяют условиям}

> и-;.,, tv, > w,_+l и vv, > »v_cp, (/ =2,F).

Число таких ребер определит число искомых классов; сами классы находятся так же, как при их заданном числе.

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