С++ мастер-класс. 85 нетривиальных проектов, решений и задач 4 Мария Озерова

Следом располагаются пары вида (идентификатор родителя, идентцфи-катор ребёнка):

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

5.8. СКРИНСЕЙВЕР - ДЕЛАЕМ ПРОСТУЮ, НО ЭФФЕКТНУЮ АНИМАЦИЮ

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

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

Слово скринсейвер не стоит воспринимать буквально. Цель не в том, чтобы запрограммировать заставку по всем правилам Windows (хотя это приветствуется); достаточно созвать приложение, выводящее на экран описанный анимироваЕшый узор.

ГЛАВА 6. ОБУЧАЮЩИЕСЯ ПРОГРАММЫ

Не всегда компьютерная программа способна храмотно распорядиться входными данными без предварительной подготовки. Если требуется отсортировать по возрастанию набор чисел, никакой подготовки не нужно; если же стоит задача определить, на что больше похож переданный объект - на круг или на прямоугольник, программе необходимо объяснить, чем круг отличается от прямоугольника. Иногда эти сведения можно явно задать в коде, но порою гораздо удобнее научить программу самостоятельно принимать решения, заранее натренировав её на типичных множествах кругов и прямоугольников. Аналогично, программа может сама научиться играть в крестики-нолики, проведя с человеком серию партий.

В данной главе мы познакомимся с алгоритмами, помимо чисто процедурных средств использующими память о каком-либо предшествующем опыте. Изучив общую задачу классификации и кластеризации, мы рассмотрим, как обучение применяется, например, при выявлении авторства текста (п. 6.1.3) и распознавании языка документа (п. 6.1.4). Вторая часть главы посвящена самообучающимся алгоритмам, самостоятельно делающим выводы из собственных успехов и неудач.

6.1. КЛАССИФИКАЦИЯ И КЛАСТЕРИЗАЦИЯ 6.1.1. Классификация и кластеризация

Алгоритмы KNN и C-Means

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

Глава 6. Обучающиеся программы

Пр1Ятной особенностью алгоритмов сортировки и поиска является их обоб-щейность. Алгоритму сортировки всё равно, что сортировать: целые числа, апельсины или плюшевых медведей. Требуется липп> передать ему отношение порядка для элементов сортируемой коллекции, то есть написать функцию, определяющую, какой из двух данных объектов является большим, а какой - меньшим.

То же самое можно сказать об универсальных методах классификации и кластеризации: достаточно ввести во множестве классифицируемых объектов метрику - и алгоритмы к вашим услугам.

Осталось пояснить, что такое метрика. С точки зрения математики, это функция f(x, у), сопоставляющая двум объектам множества некоторое число и обладаюп?ая четырьмя свойствами:

f(x.y)>0;

f(x,y) = f(y,x);

если f(x, у) = О, то X совпадает с у и наоборот;

f(x, z) + f(z, у) > f(x, у), где Z - любой объект классифицируемого множества.

На практике термин метрика обычно можно считать синонимом слова расстояние . Если вы будете думать о метрике именно в таком ключе, то изобретаемые вами функции автоматически будут удовлетворять всем требуемым условиям.

Рассмотрим, например, расстояние между двумя точками (А и В) на плоскости. Здесь и выдумывать ничего не надо, достаточно лишь воспользоваться известной формулой Евклида: ДА, В) = (A,-BJHA,-Bf

Как можно убедиться, она отвечает всем четырём требованиям, предъявляемым к метрике:

расстояние между двумя точками всегда неотрицательно;

расстояние от А до В равно расстоянию от В до А;

если расстояние между точками равно нулю, то точки совпадают и наоборот;

путь от А до В по прямой не длиннее пути, проходящего через

промежуточную точку Z. Определить расстояние между точками на плоскости или в пространстве нетрудно. Гораздо сложнее изобрести адекватную метрику, вычисляющую

О 60 100 150 200 250 300

Рис 6.1. Кластеризованное множество двумерных точек

Для кластеризации произвольной коллекции mcqicho использовать, например, несложный алгоритм C-Means:

г/ -л-

сформировать М кластеров ч; г ., i:-

приписать каждый элемент коллекции случайному кластеру . ЦИКЛ , ,

найти центроид {центральный эле1:4[ент) каждого кластера

приписать каждый объект кластеру с наиболее близкиМ к объекту центроидом ? h;;;?.

ПОКА происходят изменения ,

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

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

Наверное, самым простым алгоритмом классификации является метод KNN (К nearest neighbors). В качестве параметра алгоритма задаётся число К. Для нового объекта определяются К ближайших элементов рассортированной по кластерам коллекции. Далее производится голосование : каждый элемент голосует за свой кластер. В итоге новый объект приписывается к победившему кластеру.

Для разминки можно запрограммировать алгоритмы KNN и C-Means для точек на плоскости.

На первом шаге программа должна считывать из входного файла cmeans.txt координаты точек коллекции, принимать с клавиатуры число формируемых кластеров М и по алгоритму C-Means раскидывать точки по М кластерам. Полученные кластеры следует визуализировать, как на рис. 6.1.

Во входном файле knn.txt находятся координаты новых точек. Второй шаг программы состоит в классификации этих точек по методу KNN (значение К вводится с клавиатуры).

Обратите внимание, что первая часть коллекции (передаваемая на вход алгоритму C-Means) должна адекватно описывать всю коллекцию (то есть содержать репрезентативную выборку точек). В противном случае результаты работы метода KNN вас разочаруют. Предположим, первая часть коллекции содержит лишь точки с координатами, лежащими в промежутке от нуля до четырёх. Задав М - 2, мы получим какие-то два кластера. Далее, допустим, вторая часть коллекции (классифицируемая методом KNN) сплошь содержит элементы, сосредоточенные вокруг точки (20,20) (рис.6.2).

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

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

Допустим, исходное множество состоит из телескопов, Чебурашек и велосипедов. Допустим также, что изобретённая нами метрика гарантирует: любой телескоп будет ближе к другому телескопу, чем к любому Чебурашке или велосипеду. Аналогично, Чебурашки ближе к чебуршшсам, а велосипеды - к велосипедам.

Таким образом, если попросить программу распределить объекты по трём кластерам, все телескопы окажутся в первом ящике , Чебурашки во втором, а велосипеды в третьем. Интересны (хотя и лишены особого смысла) ситуации с двумя или четырьмя кластерами. В первом сл)гчае алгоритму придётся поместитькакие-то разнородные объекты в один и тот же кластер, а во втором, наоборот, однородные объекты окажутся помещёнными в разные ящички (впрочем, не исключён и случай пустого четвёртого кластера).

В качестве примера можно привести результат кластеризации множества двумерных точек (рис. 6.1). Количество кластеров равно четырём.