Текст статьиБлехер П. М., Кельберт М. Я. Алгоритмы классификации // Квант. — 1979. — № 6. — С. 2—8.
В этой статье мы расскажем об одном из разделов не так давно возникшей
науки — теории распознавания образов. А именно: мы поговорим о методах классификации. Классификация — это разбиение
некоторой совокупности объектов на группы объектов, близких в каком-то
смысле. Можно классифицировать, например, фабрики данной отрасли,
наблюдавшиеся в каком-то районе землетрясения, сентябрьскую погоду за много
лет, вымерших ящеров и т. д. Важно только, чтобы классифицируемые
объекты характеризовались определённым набором чисел и признаков. Для простоты мы pacсмотрим случай, когда каждый объект описывается только
набором чисел.
Как классифицировать школьников?
Пусть мы хотим разделить всех школьников девятых классов данной школы по тому, как они используют своё внешкольное время. Мы опросим каждого
школьника и запишем, какую часть этого времени он тратит на уроки и какую —
на развлечения. Оставшееся время (на еду, сон, транспорт и т. д.)
нас сейчас не интересует. В результате каждый школьник будет
характеризоваться двумя числами: временем на уроки и временем на развлечения. Поэтому он может быть изображён точкой на координатной
плоскости. Таким образом, мы приходим к чисто математическому вопросу:
как разбить данное множество точек плоскости на группы близких
точек?
К этому же вопросу приводят и многие серьёзные прикладные задачи, только
в них число координат гораздо больше (порядка нескольких десятков).
Например, в текстильной промышленности работает огромное количество
предприятий. Среди них есть и специализированные фабрики с небольшим
ассортиментом продукции, и комбинаты, выпускающие разнообразные изделия.
Есть фабрики-гиганты, есть фабрики средних размеров, есть и небольшие
местные производства. Чтобы сравнивать деятельность отдельных предприятий и планировать их работу, необходимо классифицировать все эти предприятия — разбить их на группы однотипных предприятий. Предприятия
различаются по своим экономическим показателям. Выберем среди них несколько
самых важных (например, стоимость валовой продукции, стоимость
производственных фондов и фонд заработной платы) и будем проводить
классификацию по ним. Число выбранных показателей обозначим через $n$.
Сопоставим каждому предприятию набор чисел $(x_1;\ldots;x_n)$, где $x_1$
— значение его первого показателя, $x_2$ — значение его второго показателя
и т. д.
Пара чисел $(x_1;x_2)$ задаёт точку на плоскости, тройка чисел
$(x_1;x_2;x_3)$ — точку в пространстве, а последовательность $n$
чисел $(x_1;x_2;\ldots;x_n)$ по определению считается точкой
$n$-мерного пространства.
Таким образом, на этот раз мы приходим к задаче классификации точек в $n$-мерном пространстве.
Без машин трудно
Для решения задач классификации разработаны различные алгоритмы,
позволяющие использовать вычислительные машины. Необходимость применения
вычислительных машин вызвана двумя причинами. Во-первых, как правило,
объектов очень много, и обработка всех данных вручную просто невозможна.
Во-вторых, классифицируемые объекты чаще всего многомерны.
Если, как в примере со школьниками, координат всего две и число объектов
невелико, то человек может. справиться с задачей классификации не хуже, чем вычислительная машина. А именно: он посмотрит на картинку, где изображены
точки, представляющие объекты, и выделит отвечающие сгущению
точек. Эксперименты показывают, что все люди делают это примерно одинаково.
Это связано с тем, что они (люди) непроизвольно стремятся к тому, чтобы
точки в одной группе были близки друг к другу, а различные группы были
удалены на достаточное расстояние. Если же число параметров равно трём или больше, то соображения наглядности уже практически бесполезны и задача
классификации становится труднодоступной для человека.
Психологами проводился следующий эксперимент.
Испытуемым выдавались наборы карточек с тремя числами, соответствующими
координатам точек в пространстве. Требовалось разбить точки на две естественные группы. На самом деле существовала плоскость, идущая под углом
к координатным осям, которая разбивала все точки на две группы так, что расстояние от любой точки до этой плоскости было достаточно велико по сравнению с расстояниями между точками внутри каждой группы. Большинство
людей разбивало точки по значению одной из координат, что приводило к неестественным разбиениям; правильного разбиения не удалось построить почти
никому.
Поэтому для точек в многомерном пространстве были разработаны
алгоритмы классификации. Одним из критериев правильности работы
этих алгоритмов служит требование, чтобы при классификации точек на плоскости они давали естественные разбиения — те же, какие находят люди.
Дерево минимальной длины
Мы сейчас опишем алгоритм построения связной системы отрезков,
соединяющей данные точки, с минимальной суммой длин (система отрезков
называется связной, если на любой данной точки по отрезкам этой
системы можно добраться до любой другой данной точки). Для наглядности мы рассмотрим построение на плоскости. В многомерном пространстве алгоритм
такой же, только нельзя нарисовать картинку.
Итак, пусть на плоскости даны $N$ точек $A_1$, $\ldots$, $A_N$. Для простоты мы будем считать, что все попарные расстояния между точками
различны. Выпишем все пары точек $(A_1,A_2)$, $(A_1,A_3)$, $\ldots$,
$(A_{N-1},A_N)$ и упорядочим их так, чтобы вначале шла пара с минимальным
расстоянием между точками, за ней пара со вторым по величине значением
расстояния и т. д. Соединим теперь первую пару точек, затем вторую
пару и т. д. Если при проведении очередного отрезка появляется
цикл (т. е. из системы уже проведённых отрезков можно выбрать
несколько отрезков, образующих замкнутую ломаную), то этот отрезок мы пропустим и перейдём к следующему и т. д. — до тех пор, пока не переберём все отрезки. Полученная система отрезков по построению не содержит
циклов. (Связную систему отрезков без циклов называют деревом.)
Задача 1. Докажите, что построенная система отрезков имеет
минимальную длину среди всех связных систем отрезков, соединяющих данные
точки.
Задача 2. Докажите, что ту же систему отрезков можно получить
следующим, как говорят математики, двойственным построением:
соединим все пары точек отрезками и упорядочим эти отрезки в порядке
убывания их длины; отбросим самый длинный отрезок, затем второй по величине отрезок и т. д.; если при отбрасывании очередного отрезка
оставшиеся отрезки не образуют связного множества, то пропустим этот отрезок
и перейдём к следующему и т. д. — до тех пор, пока не переберём
все отрезки.
Задача 3*. Пусть среди попарных расстояний между точками $A_1$,
$\ldots$, $A_N$ есть совпадающие. Упорядочим произвольным образом отрезки
одинаковой длины и проведём процедуру, описанную в тексте или в задаче 2. Докажите, что построенная система отрезков имеет минимальную
длину независимо от того, как были упорядочены равные отрезки. Разумеется, в этом случае система отрезков минимальной длины может быть неединственной.
Описанный нами алгоритм построения дерева минимальной длины сравнительно
прост, но требует большого перебора и, следовательно, долгой работы
вычислительной машины. Существуют более быстрые (но и более сложные!)
алгоритмы.
Разбиение на группы
После того как дерево $\Gamma$ минимальной длины построено, разбиение
множества точек $A_1$, $\ldots$, $A_N$ на группы осуществляется
отбрасыванием некоторых отрезков, входящих в это дерево. Естественно
отбрасывать достаточно длинные отрезки, но так, чтобы точки, попавшие в одну
группу, были расположены как можно теснее. Это наглядное соображение можно
формализовать, если ввести следующие величины. Пусть мы хотим разбить
множество точек $A_1$, $\ldots$, $A_N$ на $k+1$ групп. Выберем произвольные
$k$ отрезков дерева $\Gamma$ и отбросим их (рис. 1). Мы получим $k+1$
связных групп точек: $\Gamma_1$, $\ldots$, $\Gamma_{k+1}$. Для каждой группы
$\Gamma_i$ разделим сумму длин отрезков дерева $\Gamma$, соединяющих точки,
входящие в неё, на число отрезков. Мы получили среднюю длину отрезков в каждой группе $\Gamma_i$. Если какая-то группа состоит из одной точки, то по определению эта средняя длина равна нулю. Обозначим вычисленные средние
длины через $l_1$, $l_2$, $\ldots$, $l_k$, $l_{k+1}$. Пусть, кроме того,
длины отброшенных отрезков — $b_1$, $b_2$, $\ldots$, $b_k$. Образуем величину
$$F=l_1+l_2+\ldots+l_{k+1}-b_1-\ldots-b_k.$$
Рис. 1
Ясно, что чем меньше величина $F$, тем теснее расположены точки каждой
группы и тем дальше друг от друга находятся разные группы. Поэтому
естественно предложить следующий алгоритм: из дерева минимальной длины всеми
возможными способами отбрасываем $k$ отрезков и вычисляем величину $F$;
среди всех полученных разбиений выбираем то, для которого величина $F$
минимальна; если «минимальных» разбиений несколько, берём любое из них.
В реально используемых алгоритмах величина $F$ определяется, как правило,
более сложным образом.
Вычислительная практика показала, что алгоритмы описанного типа приводят
к достаточно разумным разбиениям. Главный недостаток этих алгоритмов
заключается в том, что требуется производить слишком большой перебор. При увеличении числа точек задача становится недоступной даже для современных
вычислительных машин.
Чтобы справиться с этой трудностью, используют следующую идею. Точки,
расстояние между которыми меньше некоторой величины $a$, стараются отнести к одной группе. Все построение проводят в два этапа. На первом этапе множество
точек $A_1$, $\ldots$, $A_N$ разбивают на более мелкие группы $G_1$,
$\ldots$, $G_m$ так, чтобы для каждой группы $G_i$ существовал круг $S_i$
радиуса $R=\dfrac a2$, содержащий все точки группы $G_i$ и только их. Как это сделать, мы обсудим ниже. На втором этапе рассматривают только центры
$O_1$, $\ldots$, $O_m$ кругов $S_1$, $\ldots$, $S_m$ и строят дерево
минимальной длины уже для множества $O_1$, $\ldots$, $O_m$. Минимизируя
соответствующую этому дереву величину $F$, строят разбиение на группы
множества точек $O_1$, $\ldots$, $O_m$ так, как это было описано выше. Тем самым мы получаем и разбиение множества точек $A_1$, $\ldots$, $A_N$. А именно, две точки $A_i$, $A_j$ относятся к одной группе, если они лежат в одной мелкой группе $G_i$ или если центры кругов соответствующих им мелких
групп попали при разбиении точек $O_1$, $\ldots$, $O_m$ в одну группу. Смысл
этой двухступенчатой процедуры состоит в уменьшении числа исходных точек:
число $m$ оказывается много меньше $N$, и такую процедуру уже можно
реализовать на вычислительной машине.
Задача о движущемся круге
Нам осталось обсудить, как разбить множество точек $A_1$, $\ldots$, $A_N$
на мелкие группы. Для решения этой задачи используется алгоритм «Форель» (он
несколько напоминает один из способов ловли форели). Опишем этот алгоритм
для точек на плоскости, хотя точно так же он работает и в многомерных
пространствах.
Рис. 2
Итак, пусть на плоскости даны $N$ точек $A_1$, $\ldots$, $A_N$. Поместим
в эти точки шарики единичной массы и нарисуем какой-нибудь круг $S_0$
радиуса $R$, в котором лежит хотя бы один из шариков. Пусть $O_1$ — центр
тяжести шариков, попавших в круг $S_0$, и $S_1$ — круг радиуса $R$ с центром
в точке $O_1$. Пусть $O_2$ — центр тяжести шариков, попавших в круг $S_1$, и $S_2$ — круг радиуса $R$ с центром в точке $O_2$ и т. д. Например,
на рисунке 2 изображены восемь точек $A_1$, $\ldots$,$A_8$. В начальный
круг $S_0$ попадает одна точка $A_3$, которая и будет центром круга $S_1$. В круг $S_1$ попадают точки $A_2$, $A_3$, $A_4$, и центр круга $S_2$ совпадает
с их центром тяжести. Круг $S_3$ содержит точки $A_2$, $A_3$, $A_4$, $A_5$,
$A_6$, $A_8$, и его центр совпадает с их центром тяжести, поэтому все последующие круги с ним совпадают. Далее мы докажем, что так происходит
всегда, т. е. для любых точек$A_1$, $\ldots$, $A_N$ и
произвольного выбора начального круга$S_0$, содержащего хотя бы одну точку$A_i$, все круги, начиная с некоторого шага,
совпадают. Другими словами, движение круга по маршруту
$S_0\to S_1\to S_2\to\ldots$ не может происходить бесконечно. Точки,
попавшие в последний круг, мы и отнесём к первой группе. К оставшимся точкам
применяется та же процедура, т. е. «выпускается» новый круг, конечное
положение которого определяет вторую группу. Этот процесс продолжается до тех пор, пока все точки не будут отнесены к какой-то группе.
Почему круг останавливается?
Оставшаяся часть статьи посвящена доказательству того, что круг
действительно «останавливается». Рассматривая рисунок 2, мы замечаем,
что круги $S_0$, $S_1$, $S_2$, $\ldots$ захватывают всё большее число точек
и их конечное положение соответствует сгущению точек. Естественно
предположить, что при любых расположениях точек $A_1$, $\ldots$, $A_N$ и круга $S_0$ число точек, попавших в круги $S_0$, $S_1$, $S_2$, $\ldots$, по крайней мере, не убывает. Рисунок 3 показывает, что это неверно; однако в некотором смысле сгущение точек в кругах $S_0$,
$S_1$, $S_2$, $\ldots$ действительно возрастает, только кроме числа
точек, попавших в круг, нужно учитывать, насколько близко к центру круга они лежат.
Рис. 3
А именно, пусть в какой-то круг $S$ с центром $O$ попали точки $A_{i_1}$,
$\ldots$, $A_{i_k}$; определим величину
$$
F(S)=(R^2-|OA_{i_1}|^2)+\ldots+(R^2-|OA_{i_k}|^2).
$$
Чем ближе точка к центру круга $S$, тем больший вклад она вносит в величину
$F(S)$. Докажем, что последовательность величин $F(S_0)$, $F(S_1)$,
$F(S_2)$, $\ldots$ возрастает до тех пор, пока круг не остановится.
Для доказательства нам понадобится понятие момента инерции
системы материальных точек $A_1$, $\ldots$, $A_m$ относительно некоторой
точки $A$ и теорема Штейнера, которая очень полезна при решении
многих задач не только из геометрии, но и из механики.
Моментом инерции системы материальных точек $A_1$, $\ldots$,
$A_m$ относительно точки $A$ называется величина
$$
I(A)={|AA_1|}^2+\ldots+{|AA_m|}^2.
$$
Теорема Штейнера позволяет вычислить $I(A)$, если известен момент инерции
$I(C)$ этой системы точек относительно их центра тяжести $C$. Эта теорема
утверждает, что $$
I(A)=I(C)+m|CA|^2.
$$
Докажем теорему Штейнера. Введём прямоугольную систему координат,
поместив её начало в центр тяжести точек $A_1$, $\ldots$, $A_m$ — точку $C$.
Обозначим координаты точек $A_1$, $\ldots$, $A_m$ через $(x_1;y_1)$,
$\ldots$, $(x_m;y_m)$. Тогда
$$
\begin{gather*}
I(A)=[(x_1-x)^2+(y_1-y)^2]+\ldots+[(x_m-x)^2+(y_m-y)^2]=\\
=(x_1^2+y_1^2)+\ldots+(x_m^2+y_m^2)+m(x^2+y^2)-{}\qquad\qquad\\
\qquad\qquad{}-2x(x_1+\ldots+x_m)-2y(y_1+\ldots+y_m)=I(C)+m|CA|^2,
\end{gather*}
$$
поскольку $2x(x_1+\ldots+x_m)=2y(y_1+\ldots+y_m)=0$. Теорема Штейнера
доказана.
Докажем, что если круг $S_1$ не совпадает с кругом$S_0$,
то$F(S_1)\gt F(S_0)$. Перенумеруем точки $A_1$, $\ldots$, $A_m$
так, чтобы точки, попавшие в круг $S_0$, но не попавшие в круг $S_1$, имели
номера от 1 до $p$, точки, попавшие в пересечение кругов $S_0$ и $S_1$, —
номера от $p+1$ до $q$, а точки, попавшие в $S_1$, но не попавшие в $S_0$, —
номера от $q+1$ до $r$. Таким образом, в круге $S_0$ лежат точки $A_1$,
$\ldots$, $A_q$, а в круге $S_1$ — точки $A_{p+1}$, $\ldots$, $A_r$. Ясно,
что величину $F(S_0)$ можно выразить через момент инерции $I(O)$ точек
$A_1$, $\ldots$, $A_q$ относительно точки $O$ — центра круга $S_0$, а именно,
$$
F(S_0)=(R^2-{|OA_1|}^2)+\ldots+(R^2-{|OA_q|}^2)=qR^2-I(O).
$$
Точка $O_1$ — центр круга $S_1$ — является центром тяжести точек $A_1$,
$\ldots$, $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)+\ldots+(R^2-|O_1A_q|^2)-q|OO_1|^2.
$$
Сравним это выражение с $$
F(S_1)=(R^2-|O_1A_{p+1}|^2)+\ldots+(R^2-|O_1A_r|^2).
$$
В выражении $F(S_1)$ отсутствуют слагаемые $(R^2-|O_1A_1|^2)$, $\ldots$,
$(R^2-|O_1A_p|^2)$, но появились слагаемые $(R^2-|O_1A_{q+1}|^2)$, $\ldots$,
$(R^2-|O_1A_r|^2)$. Поэтому
$$
\begin{gather*}
F(S_1)-F(S_0)=-(R^2-|O_1A_1|^2)-\ldots-(R^2-|O_1A_p|^2)+{}\qquad\qquad\\
\qquad\qquad{}+(R^2-|O_1A_{q+1}|^2)+\ldots+(R^2-|O_1A_r|^2)+q|OO_1|^2.
\end{gather*}
$$
Заметим теперь — и это решающее обстоятельство, — что точки $A_1$, $\ldots$,
$A_p$ по построению лежат вне круга $S_1$. Следовательно, величины
$R^2-|O_1A_1|^2$, $\ldots$, $R^2-|O_1A_p|^2$ отрицательны. Напротив, точки
$A_{q+1}$, $\ldots$, $A_r$ лежат внутри круга $S_1$; поэтому
величины $R^2-|O_1A_{q+1}|^2$, $\ldots$, $R^2-|O_1A_r|^2$ неотрицательны.
Таким образом,
$$
F(S_1)-F(S_0)\ge q|OO_1|^2,
$$
т. е. $F(S_1)\gt F(S_0)$, если точки $O_1$ и $O$ не совпадают.
Точно так же доказывается, что $F(S_{k+1})\gt F(S_k)$, если не совпадают
точки $O_{k+1}$ и $O_k$. Используя этот факт, теперь несложно показать, что,
начиная с некоторого номера $n$, все круги $S_n$, $S_{n+1}$, $\ldots$
совпадают. По построению точка $O_{m+1}$ является центром тяжести точек,
попавших в круг $S_m$. Если рассмотреть все подмножества множества точек
$A_1$, $\ldots$, $A_N$ и центры тяжести точек этих подмножеств, то точка
$O_{m+1}$ будет одним из этих центров тяжести. Поскольку множество центров
тяжести конечно, в последовательности центров $O$, $O_1$, $O_2$, $\ldots$
должны встретиться совпадающие, скажем, $O_i$ и $O_j$. Однако мы доказали,
что $$
F(S_i)\le F(S_{i+1})\le\ldots\le F(S_j),$$
и так как $S_i=S_j$, $F(S_i)=F(S_j)$, поэтому
$F(S_i)=F(S_{i+1})=\ldots=F(S_j)$.
Вспомним теперь, что равенство $F(S_i)=F(S_{i+1})$ возможно лишь в том случае, если круги $S_i$ и $S_{i+1}$ совпадают. Остаётся заметить, что если
два последовательных круга совпадают, то с ними совпадают по построению все последующие круги. Таким образом, мы доказали, что движение круга
$S_0\to S_1\to S_2\to\ldots$ не может быть бесконечным, или, как говорят
математики, доказали сходимость алгоритма «Форель». Попутно мы разобрали решение задачи, которая предлагалась на последней Московской
математической олимпиаде и в Задачнике «Кванта» (см. задачу
М505 в «Кванте», 1978, №5).
Две новые задачи
В заключение сформулируем ещё две задачи. Процедуры, которые описываются
в этих задачах, также применяются для классификации точек в многомерных
пространствах. Как и раньше, ограничимся случаем плоскости.
Задача 4. Пусть$N$ точек$A_1$, $\ldots$,
$A_N$ разбиты на$l$ (непустых) групп$G_1$,
$\ldots$, $G_l$. Пусть$O_1$, $\ldots$, $O_l$ — центры тяжести
каждой из этих групп. Построим новое разбиение точек$A_1$, $\ldots$,
$A_N$ по следующему правилу: каждую точку отнесём к $i$-й группе($i\le l$), если ближайшим к ней центром тяжести является точка$O_i$ (если таких центров тяжести несколько, то выбирается тот из них,
который имеет наименьший номер). Пусть после отбрасывания пустых
групп (приведите пример, когда среди групп $G_1$, $\ldots$, $G_l$
появляются пустые!) осталось $p$ групп($p\le l$).
Перенумеруя их произвольным образом, получим новое разбиение$G_1^1$, $\ldots$, $G_p^1$.
Найдя центры тяжести$O_1^1$, $\ldots$, $O_p^1$ точек этих
групп и повторив ту же процедуру, построим разбиение$G_1^2$, $\ldots$,
$G_q^2$ ($q\le p$) и т. д. Докажите, что, начиная с некоторого
шага, разбиения совпадают.
Для формулировки следующей задачи удобно ввести обозначение. Пусть на плоскости заданы точка $A$ и произвольное подмножество $G$ множества точек
$A_1$, $\ldots$, $A_N$. Положим
$$
I(A,G)=|AA_i|^2+\ldots+|AA_j|^2
$$
(сумма берётся по точкам из $G$).
Задача 5. Пусть, как и в задаче 4, задано начальное
разбиение множества точек$A_1$, $\ldots$, $A_N$ на$l$
непустых групп$G_1$, $\ldots$, $G_l$. Опишем правило
построения нового разбиения$G_1^1$, $\ldots$, $G_p^1$ ($p\le l$)
точек$A_1$, $\ldots$, $A_n$ несколько отличающееся от правила
задачи 4. При этом новое разбиение будет отличаться от начального
только тем, что одна из точек попадает в новую группу. А именно, отнесём
точку$A_1$ к той группе$G_i$, для которой величина
$I(A_1,G_i)$ минимальна (если таких групп несколько, то отнесём
точку $A_1$ к той из них, которая имеет наименьший номер). Если при этом точка $A_1$ была единственной в своей группе и в результате её переноса
группа стала пустой, то отбросим эту группу, а остальные группы перенумеруем
произвольным образом. Полученное разбиение обозначим$G_1^1$, $\ldots$,
$G_p^1$ ($p=l$ или$p=l-1$). Повторим ту же процедуру для точек$A_2$, $\ldots$, $A_N$ и затем — снова для $A_1,$ для $A_2$
и т. д. Докажите, что, начиная с некоторого шага, все разбиения
совпадают.
Рис. 4
Преимущество алгоритмов, описанных в задачах 4 и 5, по сравнению с алгоритмом «Форель» состоит в том, что эти алгоритмы быстро
сходятся (т. е. построение окончательного разбиения требует меньшего
времени работы вычислительной машины). Однако при неудачном выборе
начального разбиения эти алгоритмы могут привести к не очень естественному
конечному разбиению на группы. Один из таких примеров приведён на рисунке 4.
