-Т!-1-1-г

Рис 6.2. Неудачная классификация методом KNN

По логике вещей, эти точки должны быть сгруппированы в свой собственный кластер, но поздно! Кластеры сформированы, и всё, что может сделать KNN - это поместить новые элементы в уже существующие ящики , даже если полученная классификация будет соверщенно неадекватной.

Решение

Здесь мы рассмотрим только решение задачи кластеризации методом C-Means. Алгоритм KNN используется в задачах 6.3 и 6.4, и приводить же один и тот же фрагмент кода в двух местах книги мне кажется излипшим.

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

Пусть элементы произвольного типа Туре находятся в некотором контейнере. Считается, что в программе определена функция расстояния

double Distance(const Туре& Ihs, cbnst Туре& rhs)

возвращающая расстояние между любыми двумя объектами типа Туре. Наша задача - написать фзгнкцию Cluster (), по заданным итераторам начала и конца диапазона объектов и количеству кластеров М формирующую требуемые кластеры:

template <class Iterator>

vector<list<typename Iterator::value type> > Cluster(const Iterator begin,

const Iterator end, int M)

Возвращаемое значение представляет собой вектор, каждый элемент которого является отдельным кластером - списком объектов типа

Iterator;:value type.

Для начала нам потребуется несложная служебная функция Centroid (), возвращающая центроид набора объектов, задаваемого итераторами begin и end:

template <class Iterator>

Iterator::value type Centroid(const Iterator begin, const Iterator end) {

double MinDist = numeric limits<double>::max(); Iterator::value type Element;

пробежаться no всем элементам диапазона

for(Iterator current = begin; current != end; current++)

вычислить сумму расстояний между текущим элементом и всеми остальными double Dist = 0;

for(Iterator с = begin; с != end; С++) Dist += Distance(*current, *c);

найти элемент, для которого эта сумма минимальна if(Dist < MinDist)

{ MinDist = Dist; Element = *current; }

return Element;

Функция Cluster о реализует алгоритм, приведенный в постановке задачи на псевдокоде:

template <class Iterator>

vector<list<typename Iterator: :value type> > Cluster (const Iterator begin.,

const Iterator end, int M)

создать M кластеров

vector<list<Iterator::value type> > Clusters(M);

приписать каждый объект к случайному кластеру for(Iterator с = begin; с != end; С++) Clusters[random(М)].push back(*c);

vector<Iterator::value type> Centroids(M);

С++ мастер-класс. 85 нетривиальных npoeiaob. решений и задач

bool modified;

найти центроиды

for(int i = 0; i < M; i++)

Centroids[i] Centroid(Clusterslil .begin(), Clusters[il .end());

modified = false;

vector<list<Iterator::value type> > NewClusters(M) ;

for(int OldCl = 0; OldCl < M; 01dCl++)

fordterator с = Clusters[01 dCl] .begin();

с != Clusters[OldCl].endO; С++)

double MinDist = numeric limits<double>::max(); int ClusterNo;

найти кластер ближайшего к элементу центроида for(int centroid = 0; centroid < М; centroid++) {

double Dist = Distance(*c, Centroids[centroid]);

if(Dist < MinDist)

{ MinDist = Dist; ClusterNo = centroid; }

если центроид принадлежит друголгу кластеру if(ClusterNo != OldCl)

modified = true; NewClusters[ClusterNo].push back(*c);

Clusters = NewClusters;

пока происходят изменения

while(modified); return Clusters;

Чтобы применить функцию Cluster () к двумерным точкам, осталось описать структуру точка на плоскости и запрограммировать простые функции Distance О. и main О:

struct Point {

int X, у;

расстояние между точками на плоскости

double Distance(const Pointt pi, const Point& p2)

return sqrt((pl.x - p2.x)*(pl.x - p2.x) + (pl.y - p2.y)*(pl.y - p2.y));

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

int main(int argc, char* argv[]) {

randomize();

int N, M; cin N; cin M;

количество точек

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

считать список точек

list<Point> 1р;

for(int i = 0; i < N; i++)

Point p; cin p.x; cin p.y; Ip.push back(p);

выполнить кластеризацию

vector<list<Point> > Clusters = Cluster dp. begin(), Ip.endO, M);

распечатать результаты (номер кластера, х, у) for(int i = 0; i < М; i++)

for(list<Point>::iterator p = Clusters[il.beginO;

p 1- Clusters[i] .endO ; p++) cout i p->x p->y endl;

return 0;

Результат разбиения тестовой коллекции точек на два (слева) и на четыре (справа) кластера показан на рис. 6.3.

100 120

ГЦ 4

Рис. 6.1. Кластеризация коллекции точек на плоскости

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

Классификация и кластеризация текстовых документов

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

Поисковая система - это программа наподобие Яндекса: пользователь задаёт в строке ввода запрос , а компьютер возвращает сортированный по релевантности список найденных документов, некоторым образом соответствующих запросу.

Рубрикатор - это служба, называемая в терминах Яндекса каталогом . Документы коллекции некоторым образом группируются в иерархическую структуру, предоставляемую для просмотра пользователю. Например, верхние уровни каталога могут называться Работа , Учёба , Дом , Бизнес и так далее. Зайдя в раздел Дом , человек попадает в подразделы вроде Квартира , Кулинария или Семья .

Подобные системы, используемые м1огими из нас ежедневно, имеют самое непосредственное отношение к рассмотренным выше темам.

Представьте, что на множестве документов определена метрика f(A, В), то есть функция, сопоставляющая паре документов расстояние между ними. Если считать пользовательский запрос Q одним из документов коллекции (его маленький размер ничего не меняет), то задача поиска превращается в простую распечатку списка файлов коллекции, наиболее близких к запросу в соответствии с метрикой:

L - пустой список

для КАЖДОГО документа коллекции D

ЕСЛИ f{D, Q) < ПОРОГОВОЕ ЗНАЧЕНИЕ РЕЛЕВАНТКОеЩ . добавить D в список h , i, v

/*0!рсо?тщ)двйть L по убыванию релевантности , >

распечатать Ь

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

Подсказка

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

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

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

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

Но сначала одно маленькое замечание. При работе с пространством документов обычно рассматривают не метрику f(A, В), а функцию близости sJm(A, В).

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

Таким образом, функция sim(A, В) возвращает число в промежутке [0,1], трактуемое как степень соответствия. При желании можно определить метрику через близость:

f(A,B)-l-sim(A,B)

Конечно, функция f(A, В) также будет ограничена сверху единицей, но это не противоречит определению метрики.

Вернёмся теперь к модели векторного пространства. Идея заключается в представлении каждого документа (D, Dj,D ) системы (включая запрос пользователя) в виде набора (вектора) из Т чисел: