Алгоритмы классификации

2

П. Блехер, М. Кельберт

Алгоритмы классификации

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

*) Тем, кто хочет познакомиться с ней пользовке, мы советем прочесть увлекательную, хотя и не очень простую книгу М. М. Бонгарда «Проблема узнавания» (М., «Нayka», 1967).

Как классифицировать школьников?

Пусть мы хотим разделить всех школьников девятых классов данной школы по тому, как они используют свое внешкольное время. Мы просим каждого школьника и запишем, какую часть этого времени он траит на уроки и какую — на развлечения. Оставшееся время (на еду, сон, транспорт и т. д.) нас сейчас не интересует. В результате каждый школьник будет характеризоваться двумя числами: времени на уроки и времени на развлечения. Поэтому он может быть изображен точкой на координатной плоскости. Таким образом, мы приходим к чисто математическому вопросу: как разбить данные множество множеств на группы близких чисел?

К этому же вопросу приводят и многие серые прикладные задачи, только в них число координат города больше (порядка несколько десятиков).

Например, в текстильной промышленности работает огромное количество предприятий. Среди них есть

3

и специализированные фабрики с небольшим ассортиментом продукции, и комбинаты, выпускающие разнообразные изделия. Есть фабрики-гиганты, есть фабрики средних размеров, есть и небольшие местные производства. Чтобы сравнить детальность отдельных предметий и планировать их работу, необходимо классифицировать все эти предметия — разбитых их на группы однотипных предметий. Предприятия ралицются по своим экономическим показателям. Выберем среди них несколько самых важных (например, стоимость выполнения строительства отдельных предметий и фонд заработной платы) и будем проводить классификацию по ним. Число выбранных показателей обозначим через $n$.

Сопоставим каждому предметию набор чисел $(x_1; \dots; x_n)$, где $x_1$ — значение его первого показателя, $x_2$ — значение его второго показателя и т. д.

Пара чисел $(x_1; x_2)$ задает точку на плоскости, тройка чисел $(x_1; x_2; x_3)$ — точку в пространстве, а последовательность $n$ чисел $(x_1; x_2; \dots; x_n)$ по определенному считается мощной $n$-мерной пространства.

Таким образом, на этот раз мы приходим к задаче классификации точек в $n$-мерном пространстве.

Без машин трудно

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

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

Психологами проводился следующий эксперимент *. Испытемым выдавались набор карточек с теми числами, соответствующими координатам точек в пространстве. Требования разбитить точки на две естественные группы. На самом деле существовала плоскость, ищая под углом к координатным осмам, которая разбила все точки на две группы так, что расстояние от любой точки до этой плоскости было достаточно велико по сравнению с расстояниями между точками внутри каждой группы. Большинство людей по значению одной из координат, что приводило к неестественным разбиениям; правильного разбиения не удалось построить почти никакому.

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

Дерево минимальной длины

Мы сейчас описем алгоритм построения связи новой системы отрезков, соединяющей данные точки, с минимальной суммой длины (система отрезков называется связной, если

*) Этот и неокоторые другие подобные эксперименты описаны в книге Н. Г. З агору ко «Медоды расознавания и их применения» (М., «Советское радио», 1972). В этой книге можно подробнее прочесть о многохвом вопросах, о которых мы упомянам только вскользь.

4

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

Итак, путь на плоскости данных $N$ точек $A_1, \dots, A_N$. Для простоты мы будем считать, что все попарные расстояния между точками различны. Выпишем все пары точек $(A_1, A_2), (A_1, A_3), \dots, (A_{N-1}, A_N)$ и упорядочим их так, чтобы вначале шла пара с минимальным расстоянием между точками, за ней пара со вторым по величины значением расстояния и т. д. Соединим теперь первую пару точек, затем вторую пару и т. д. Если при проведении очередного отрезка появляется цикл (то есть из системы уже проведенных отрезков можно выбрать несколько отрезков, образующих замкнутую ломаную), то этот отрезок мы пропустим и перейдем к следующему и т. д. — до тех пор, пока не переберем все отрезки. Полученная система отрезков по построению не содержит циклов. (Связную систему отрезков без циклов называют деревом.)

Задача 1. Докажите, что построенная система отрезков имеет минимальную длину всех связных систем отрезков, соединяющих данные точки.

Задача 2. Докажите, что ту же система отрезков можно получить следующим, как говорят математики, до вейнены м построением: соединним все пары точек отрезками и упорядочим эти отрезки в порядке у бы ваня их длины; отбросим самый длинный отрезок, затем второй по величины отрезок и т. д.; если при отбрасывании очередного отрезка оставшиеся отрезки не образуют связного множества, то пропустим этот отрезок и перейдем к следующему и т. д. — до тех пор, пока не переберем все отрезки.

Задача 3*. Пусть среди попарных расстояний между точками $A_1, \dots, A_N$ есть совпаданное. Упорядочим произвольным образом отрезки одинаковой длины и проведем проедуру, описанную в тексте или в задание 2. Докажите, что построенная система отрезков имеет минимальную длину независящего от того, как были упорядочены равные отрезки. Разумеется, в этом случае система отрезков минимальной длины может быть неединственной.

Описанный нами алгоритм построения дерева минимальной длины

сравнительно прост, но требует большого перебора и, следовательно, должно работать вычислительной машины. Существуют более быстрые (но и более сложные!) алгоритмы.

Разбение на группы

После того как дерево Г минимально длины построено, разбение множества точек $A_1, \dots, A_N$ на группы осуществляется отрасыванием некоторых отрезков, входящих в это дерево. Естественно отрасываются достаточно длинные отрезки, но так, чтобы точки, попавшие в одну группу, были расположены как можно теснее. Это наглядное сообщение можно формилизовать, если ввести следующее величины. Пусть мы хотим разбитить множество точек $A_1, \dots, A_N$ на $k + 1$ групп. Выберем произвольные $k$ отрезков дерева Г и отбросим их (рис. 1). Мы получим $k + 1$ связных групп точек: $\Gamma_1, \dots, \Gamma_{k+1}$. Для каждой группы $\Gamma_i$ разделим сумму длины отрезков дерева Г, соединяющихся точки, входящие в нее, на число отрезков. Мы получили среднюю длину отрезков в каждой группе $\Gamma_i$. Если какая-то группа состоит из одной точки, то по определению эта средняя длина равна нулю. Обозначим вычисленные средние длины через $l_1, l_2, \dots, l_k, l_{k+1}$. Пусть, кроме того, длины отросшенных отрезков — $b_1, b_2, \dots, b_k$. Образуем величины

$$F = l_1 + l_2 + \dots + l_{k+1} - b_1 - \dots - b_k.$$

Ясно, что чем меньше величины $F$, тем теснее рассоложены точки каждой группы и тем дальше друг от друга находится разные группы.

5

этому естественно предложить следующий алгоритм: из дерева минимальной длины всеми возможными способами отбрасываем $k$ отрезков и вычисляем величины $F$; среди всех полученных разбиений выбираем то, для которого велича $F$ минимальная; если «minimalных» разбиений несколько, берем любое из них.

В результате использовых алгоритмов величины $F$ определяется, как правило, более сложным образом.

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

Чтобы справиться с этой трудностью, используются следующие идеи. Точки, расстояние между которых меньше некоторой величины $a$, стараются относительно к одной группе. Все построение проводят в два этапа. На первом этапе множество точек $A_1, \dots, A_N$ разбивают на более мелкие группы $G_1, \dots, G_m$ так, чтобы для каждой группы $G_i$ существовал круг $S_i$ радиуса $R = a/2$, содержащий все точки группы $G_i$ и только их. Как это сделать, мы обсуим ниже. На втором этапе рассматривают только центры $O_1, \dots, O_m$ кругов $S_1, \dots, S_m$ и строят дерево минимальной длины уже для множества $O_1, \dots, O_m$. Минимизируя соответствующее этому дереву величины $F$, строят разбиение на группы множества точек $O_1, \dots, O_m$ так, как это было описано выше. Тем самым мы получаем и разбиение множества точек $A_1, \dots, A_N$. А именно, две точки $A_i, A_j$ относятся к одной группе, если они лежат в одной мелкой группе $G_i$ или если центры кругов соответствуют мелких группе попали при разбиении точек $O_1, \dots, O_m$ в одну группу. Смысл этой двухступенчатой процедуры состоит в уменьшении числа исходных точек: число $m$ оказывается много меньше $N$, и также процессур уже можно реализовать на вычислительной машине.

Задча о движущемся круге

Нам осталось обсуить, как разбит множество точек $A_1, \dots, A_N$ на мелкие группы. Для решения этой задачи используется алгоритм «Форель» (он несколько напоминает один из способов ловли форели). Опишем этот алгоритм для точек на плоскости, хотя точно так же он работает и в многомерных пространствах.

Итак, пусть на плоскости даны $N$ точек $A_1, \dots, A_N$. Поместим в эти точки шарики единничной массы и нарисуем какой-нибудь круг $S_0$ радиуса $R$, в котором лежит хотя один из шариков. Пусть $O_1$ — центр тяжестки шариков, попавших в круг $S_0$, и $S_1$ — круг радиуса $R$ с центром в точке $O_1$. Пусть $O_2$ — центр тяжестки шариков, попавших в круг $S_1$, и $S_2$ — круг радиуса $R$ с центром в точке $O_2$ и т. д. Например, на рис. 2.

6

Круга по маршруту $S_0 \rightarrow S_1 \rightarrow S_2 \rightarrow \dots$ не может пронсходить бесконечно. Точки, попавшие в последний круг, мы и отнесем к первой группе. К оставшимся точкам применяется та же процедура, то есть «выпускается» новый круг, конечное положение которого определяет вторую группу. Этот процессprodолжется до тех пор, пока все точки не будут отнесены к какой-то группе.

Почему круг останавливается?

Оставшаяся часть статы посвящена доказательству того, что круг действительно «остановливается». Расматривая рисунок 2, мы замечаем, что круги $S_0, S_1, S_2$, … захватывают все большие число точки и их конечное положение соответствуют группу. Естественно предположить, что при любых расположениях точки $A_1, \dots, A_N$ и круга $S_0$ число точки, попавших в круги $S_0, S_1, S_2$, …, по крайней мере, не убывает. Рисунок 3 показывает, что это неверно; однако в некоторых случаях возможно возрасти, только кроме числа точки, попавших в круг, нужно учитывать, насолько близко к центру круга они лежат.

А именно, путь в какой-то круг $S$ с центром $O$ попали точки $A_{i_1}, \dots, A_{i_h}$; определям величины

$$F(S) = \left(R^2 - |OA_{i_1}|^2\right) + \dots + \left(R^2 - |OA_{i_h}|^2\right).$$

Чем близке точки к центру круга $S$, тем больший вклад она в величины $F(S)$. Докажем, что последовательность величины $F(S_0), F(S_1)$,

$$F(S_2), \dots$$ возрастает до тех пор, пока круг не остановится.

Для доказательства нам понадобится момент иерции и системы материалов точек $A_1, \dots, A_m$ относительно некоторых $A$ и теорема Штейнера, которая очень полезна при решении многоих задач не только из геометрии, но и из механики *).

Моментом инерции системы материалов точек $A_1, \dots, A_m$ относительно точки $A$ называется величины

$$I(A) = |AA_1|^2 + \dots + |AA_m|^2.$$

Теорема Штейнера позволяет вычислить $I(A)$, если известен момент инерции $I(C)$. этой системы точек относительно их центра тяжестки $C$. Эта теорема утверждает, что

$$I(A) = I(C) + m|CA|^2.$$

Докажем теорему Штейнера. Введем прямогольную систему координат, помещив ее начало в центр тяжестки точки $A_1, \dots, A_m$ — точки $C$. Обозначим координаты точки $A_1, \dots, A_m$ через $(x_1; y_1), \dots, (x_m; y_m)$. Тогда центр тяжестки $C$ имеет координаты $(x_1 + \dots + x_m)/m; (y_1 + \dots + y_m)/m)$, а поскольку $C$ совпадает с началом координат, то $x_1 + \dots + x_m = y_1 + \dots + y_m = 0$. Пусть точка $A$ имеет координаты $(x; y)$. Тогда

$$I(A) = \left[ (x_1 - x)^2 + (y_1 - y)^2 \right] + \dots + \left[ (x_m - x)^2 + (y_m - y)^2 \right] = \left( x_1^2 + y_1^2 \right) + \dots + \left( x_m^2 + y_m^2 \right) + m \left( x^2 + y^2 \right) - 2x \left( x_1 + \dots + x_m \right) - 2y \left( y_1 + \dots + y_m \right) = I(C) + m|CA|^2,$$

поскольку $2x(x_1 + \dots + x_m) = 2y(y_1 + \dots + y_m) = 0$. Теорема Штейнера доказана.

Докажем, что если круг $S_1$ не совпадает с кругом $S_0$, то $F(S_1) > F(S_0)$. Перенумерем точки $A_1, \dots, A_m$ так, чтобы точки, попавшие в круг $S_0$, не неопавшие в круг $S_1$, имели номера от 1 до $p$, точки, попавшие в пересечение кругов $S_0$ и $S_1$,— номера от $p + 1$ до $q$, а точ-

*) См. книгу М. Б. Балка «Геометрические приложения понятия о ценре мяжести» (М., Физматиз, 1959).

7

ки, попавшие в $S_1$, но не попавшие в $S_0$, — номера от $q + 1$ до $r$. Таким образом, в круге $S_0$ лежат точки $A_1, \dots, A_q$, а в круге $S_1$ — точки $A_{p+1}, \dots, A_r$. Ясно, что величины $F(S_0)$ можно выразить через момент инерции $I(O)$ точки $A_1, \dots, A_q$ относительно точки $O$ — центра круга $S_0$, а именно,

$$F(S_0) = (R^2 - |OA_1|^2) + \dots + (R^2 - |OA_q|^2) = qR^2 - I(O).$$

Точка $O_1$ — центр круга $S_1$ — является центром тяжестни точек $A_1, \dots, A_q$, поэтому по теореме Штейнера

$$I(O) = I(O_1) + q |OO_1|^2,$$

то есть

$$F(S_0) = qR^2 - I(O_1) - q |OO_1|^2 = (R^2 - |O_1A_1|^2) + \dots + (R^2 - |O_1A_q|^2) - q |OO_1|^2.$$

Сравним это выражение с

$$F(S_1) = (R^2 - |O_1A_{p+1}|^2) + \dots + (R^2 - |O_1A_r|^2).$$

В выражении $F(S_1)$ отсутствует слагаемые

$$(R^2 - |O_1A_1|^2), \dots, (R^2 - |O_1A_p|^2),$$

но появились слагаемые

$$(R^2 - |O_1A_{q+1}|^2), \dots, (R^2 - |O_1A_r|^2).$$

Позному

$$F(S_1) - F(S_0) = -(R^2 - |O_1A_1|^2) - \dots - (R^2 - |O_1A_p|^2) + (R^2 - |O_1A_{q+1}|^2) + \dots + (R^2 - |O_1A_r|^2) + q |OO_1|^2.$$

Заметим теперь — и это решающее обстоятельство,— что точки $A_1, \dots, A_q$ по построению лежат в некурата $S_1$. Следовательно, величины $R^2 - |O_1A_1|^2, \dots, R^2 - |O_1A_p|^2$ относятельны. Например, точки $A_{q+1}, \dots, A_r$ лежат внутри круга $S_1$; поэтому величины $R^2 - |O_1A_{q+1}|^2, \dots, R^2 - |O_1A_r|^2$ относятельны. Таким образом,

$$F(S_1) - F(S_0) \geq q |OO_1|^2,$$

то есть $F(S_1) > F(S_0)$, если точки $O_1$ и $O$ не совпадают.

Точно так же доказывается, что $F(S_{k+1}) > F(S_k)$, если не совпадают точки $O_{k+1}$ и $O_k$. Используя этот факт, теперь несложно показать, что, начиная с некоторого номера $n$, все круги $S_n, S_{n+1}, \dots$ совпадают. По построению точки $O_{m+1}$ является центром тяжестни точек, попавших в круг $S_m$. Если рассмотреть все подмножества множества точки $A_1, \dots, A_N$ и центры тяжестни точки этих подмножестств, то точки $O_{m+1}$ будет одним из этих центров тяжестни. Поскольку множество центров тяжестни конечно, в последовательности центров $O, O_1, O_2, \dots$ должны встречаться совпадующие, скажем, $O_i$ и $O_j$. Однако мы доказали, что

$$F(S_i) \leq F(S_{i+1}) \leq \dots \leq F(S_j),$$

и так как $S_i = S_j$, $F(S_i) = F(S_j)$, поэтому $F(S_i) = F(S_{i+1}) = \dots = F(S_j)$.

Вспомним теперь, что равенство $F(S_i) = F(S_{i+1})$ возможно ли в том случае, если круги $S_i$ и $S_{i+1}$ совпадают. Остается заметить, что если два последовательных круга совпадают, то с ним совпадают по построению все последующие круги. Таким образом, мы доказали, что движение круга $S_0 \rightarrow S_1 \rightarrow S_2 \rightarrow \dots$ не может быть бесконечным, или, как говоря математически, доказали сходимость алгоритма «Форель». Попутно мы разобрали решение задачи, которая предлагалась на последней Московской математической оптимизации и в задачике «Кванта» (см. задачу М505 в «Кванте», 1978, № 5).

Две новые задачи

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

Задача 4. Пусть $N$ мощек $A_1, \dots, A_N$ разбиены на $l$ (неупустых) групп $G_1, \dots, G_l$. Пусть $O_1, \dots, O_l$ — центры тяжестни каждой из этих групп. Построим новое разбиение мощек $A_1, \dots, A_N$ по следующему правила: каждую точку отнесем к $i$-й группе ($i \leq l$), если близкой к ней