§2. Эвристические методы

Научное исследование — это искусство, а правила его, если они слишком жёстки, приносят больше вреда, чем пользы.

— Дж. Томсон, «Дух науки»

Подавляющая часть классификаций на практике проводится именно эвристическими методами. Причины:

• они относительно просты, и смысл их ясен;
• в работу алгоритма можно вмешаться, меняя один-два параметра с понятным смыслом;
• трудоёмкость у них невысокая.

A1. Связные компоненты

Все объекты разбиваются на классы типа ленты (слабого сгущения, C3 из §1), где задаваемый параметр $\tau \in (\min d_{ij}, \max d_{ij})$. В этой постановке задача классификации эквивалентна нахождению связных компонент графа: вершины $i$ и $j$ соединены ребром, если $d_{ij} \le \tau$. Алгоритм выделения связных компонент — поиск в глубину — изложен в §9.

Для выбора $\tau$ полезно построить гистограмму межобъектных расстояний: высота прямоугольника над промежутком $\Delta_l$ пропорциональна количеству $d_{ij}$, попавших в $\Delta_l$. При хорошей структурированности данных гистограмма, как правило, имеет два выделяющихся максимума:

• при $d_{ij} \approx d_{int}$ — типичное внутриклассовое расстояние;
• при $d_{ij} \approx d_{out}$ — типичное межклассовое расстояние.

Часто удачным выбором $\tau$ оказывается значение $(d_{int} + d_{out})/2$.

Смысл по-пацански: договорились, что «свои» — это те, до кого можно дотянуться рукой длиной $\tau$, хотя бы через знакомых. Короткая рука — каждый сам за себя; длинная — весь район одна компания. Гистограмма подсказывает длину руки.

Подвигай $\tau$ на «облаках с центром» и на «лентах». Окно удачных $\tau$ узкое:

• чуть короче — и от облаков откалываются одиночки, а ленты рвутся на куски;
• чуть длиннее — и соседние классы склеиваются через пару случайно оказавшихся между ними точек. Это цепочечный эффект, о нём ещё будет речь в §3.

Поэтому гистограмма так важна: без неё $\tau$ приходится угадывать.

A2. Кратчайший незамкнутый путь

Его также называют минимальным покрывающим деревом или каркасом (КНП). Строится так:

1. соединяются ребром две ближайшие точки;
2. затем среди оставшихся отыскивается точка, ближайшая к любой из уже соединённых, и присоединяется к ним;
3. и т. д. до исчерпания всех точек.

Р. Прим в 1957 г. доказал, что построенный таким способом граф имеет минимальную общую длину рёбер среди всевозможных соединений, связывающих все вершины.

В найденном КНП затем отбрасывают $k - 1$ самых длинных дуг и получают $k$ классов. Число $k$ задаёт исследователь; на практике обычно $2 \le k \le 5$. Метод позволяет выделять классы произвольной формы.

Длины рёбер КНП — это ровно уровни объединения в методе «ближнего соседа» из §3: каркас и дендрограмма P1 несут одну и ту же информацию.

Отступление: точка Штейнера

Если разрешается добавлять в граф новые вершины (точки Штейнера), то можно добиться меньшей, чем у КНП, длины пути. Уже для трёх точек $A$, $B$ и $C$ на плоскости, у которых наибольший из углов $\triangle ABC$ меньше $120°$, существует точка $O$ внутри треугольника, для которой минимальна сумма $|OA| + |OB| + |OC|$.

Доказательство. Пусть $O$ — некоторая точка внутри $\triangle ABC$. При повороте на $60°$ вокруг вершины $A$ точки $O$, $B$ и $C$ перейдут в точки $O'$, $B'$ и $C'$ соответственно. Так как $\triangle AOO'$ равносторонний, то $|AO| = |OO'|$. Отрезок $OC$ переходит в отрезок $O'C'$, поэтому $|OC| = |O'C'|$. Значит, сумма $|OA| + |OB| + |OC| = |OO'| + |OB| + |O'C'|$ равна длине ломаной $BOO'C'$. Она минимальна, когда ломаная является отрезком. Поскольку $\angle AOO' = 60°$, для этого необходимо, чтобы $\angle BOA = 120°$. Иначе говоря, сторона $AB$ должна быть видна из оптимальной точки под углом $120°$. Из симметрии то же самое должно быть верно и для двух других сторон $\triangle ABC$. $\blacksquare$

Как построить такую точку циркулем и линейкой — вопрос 2, где она для выпуклого четырёхугольника — вопрос 3. Для произвольного расположения вершин и любого числа точек Штейнера эффективные алгоритмы построения кратчайшего соединения неизвестны.

A3. Метод k-средних

Предназначен для выделения классов типа C4 («класс с центром»). Название, ставшее популярным, введено Дж. Мак-Кином. Два варианта.

(a) Алгоритм Г. Болла и Д. Холла (1965).

1. Случайно выбираются $k$ объектов — эталонов.
2. Каждый объект присоединяется к ближайшему эталону — образуется $k$ классов.
3. В качестве новых эталонов принимаются центры масс классов (каждому объекту приписана масса 1).
4. После пересчёта объекты снова распределяются по ближайшим эталонам и т. д.

Критерий окончания — стабилизация центров масс всех классов.

Вместо случайно выбираемых эталонов лучше использовать $k$ наиболее удалённых объектов. Сначала отыскиваются два самых удалённых друг от друга объекта, затем $l$-й эталон ($l = 3, \dots, k$) определяется как наиболее удалённый в среднем от уже имеющихся.

(b) Алгоритм Дж. Мак-Кина (1967). Отличается тем, что при просмотре списка объектов пересчёт центра масс класса происходит сразу после присоединения к нему очередного объекта. Алгоритм Мак-Кина связан с функционалом качества $F2$ из §5.

Смысл по-пацански: выбрали $k$ «старших», каждый прибился к ближайшему, старший переехал в середину своей компании, все снова перебежали к ближайшему — и так, пока никто не переезжает. Болл и Холл пересаживают всех разом, Мак-Кин — по одному.

Пощёлкай «Эталоны: случайные» и «Новая выборка». Случайные эталоны нередко ставят двух «старших» в одно облако, и алгоритм застревает в плохом разбиении. Самые удалённые объекты спасают почти всегда. Двигая «Шаг алгоритма», видно, как центры сползают к серединам облаков за несколько итераций. На лентах и кольце k-средних беспомощен: это не классы с центром.

A4. Алгоритм «Форель»

Первоначальное название — ФОРЭЛ, «ФОРмальный ЭЛемент». Предложен В. Н. Елкиной и Н. Г. Загоруйко в 1966 г.

1. Случайный объект объявляется центром класса; все объекты на расстоянии не больше $R$ от него входят в первый класс.
2. В классе определяется центр масс, который объявляется новым центром класса, и т. д. до стабилизации центра.
3. Затем все объекты, попавшие в первый класс, изымаются, и процедура повторяется с новым случайным центром.

Алгоритмы A4 и A2 можно скомбинировать:

• при небольшом $R$ алгоритм A4 находит $k' > k$ классов;
• их центры соединяют КНП, из которого удаляют $k - 1$ самых длинных рёбер, и получают $k$ классов.

При этом образуются классы более сложной формы, чем $m$-мерные шары. Здесь важна идея двухэтапности: сначала выделить заведомо компактные маленькие группы, затем произвести их объединение. Так можно успешно классифицировать довольно большие массивы информации — сотни объектов.

A5. Метод потенциальных ям

Предположим, что каждый объект $\boldsymbol x_i = (x_{i1}, \dots, x_{im})$ создаёт вокруг себя поле притяжения с некоторой весовой функцией, например гладким квартическим ядром

где $r_i = |\boldsymbol x - \boldsymbol x_i|$, а параметр $R > 0$ задаёт эффективный размер области притяжения. Все вместе объекты создают потенциальное поле $U(\boldsymbol x) = -\sum W_i(\boldsymbol x)$. Классам соответствуют потенциальные ямы: объект $\boldsymbol x_i$ относится к яме, в которую он «скатывается» при свободном движении.

Практически приходится, стартовав с $\boldsymbol x_i$, запускать некоторый алгоритм (локальной) минимизации. Один из простейших — циклический перебор $2m$ точек, соседних с текущей по осям, с шагом $\pm h$ ($h$ — точность поиска точки минимума):

• если значение $U$ в какой-то из них меньше, чем в текущей, происходит перемещение туда (противоположную по этой оси точку можно не проверять);
• для ускорения полезно запоминать знак успешного перемещения по каждой оси и в следующем цикле пробовать сдвигаться сначала в том же направлении;
• критерий окончания — отсутствие перемещений за время цикла.

Обозначим через $\boldsymbol y_i$ конечную точку пути из $\boldsymbol x_i$. Объекты $\boldsymbol x_i$ и $\boldsymbol x_j$ отнесём к одному классу, если $\sum_{l=1}^m|y_{il} - y_{jl}| \le 2kh$, то есть если $\boldsymbol y_i$ и $\boldsymbol y_j$ близки в метрике города D1. (Буква $k$ в книге не расшифрована — это небольшое целое число шагов; в виджете взято $k = m$.) Число перемещений при поиске локального минимума — длина пути — характеризует удалённость $\boldsymbol x_i$ от «центра» класса, дна ямы.

Из-за необходимости численной минимизации для каждого $\boldsymbol x_i$ метод рекомендуется применять для классификации небольшого числа (нескольких десятков) объектов.

Смысл по-пацански: каждый объект — ямка в резиновом листе. Ямки рядом сливаются в одну большую воронку. Пустил шарик с каждого объекта — куда скатился, там его и класс.

На паре «большое облако + малое плотное» потенциальные ямы при $R$ около 2 обычно находят оба класса, хотя k-средних тут часто «отгрызает» от большого облака кусок в пользу малого. Попробуй и «Форель»: при маленьком $R$ она дробит всё на мелкие шарики — ровно тот первый этап, после которого их склеивают через КНП.

Проверь себя