Для воплощения в жизнь второго наблюдения нам потребуются ещё две формулы:

df = количество документов, содержащих слово i

idf. = logj (N / df), где N - общее количество документов в коллекции

Величина idf, называемая обратной документной частотой (inverse document frequency, в русскоязычной литературе термин ещё не устоялся), тем выше, чем меньше в коллекции файлов, содержащих слово i.

Итоговый вес слова i в документе] определяется по формуле:

W, =tf.*idf

Ч Ч

Если вы не забыли, определение веса слов документа - лишь часть нашей задачи. Теперь необходимо решить, каким образом будет производиться вычисление функции подобия для векторов D. и D.. Здесь всё просто, хотя и громоздко:

т *=1

Не забывайте, что любое слово в коллекции можно закодировать числом от единицы до Т.

Поскольку документы представляются в виде векторов, мы можем применить известную в математике формулу скалярного произведения (числитель дроби). Знаменатель нормализует полученный результат, загоняя его в промежуток [0,1].

Модель векторного пространства - алгоритм во многом эвристический, критика в его адрес всегда существовала. Хотя основная цель задачи состоит в реализации систем поиска и рубрикации, разработка собственной функции близости также весьма приветствуется.

6.1.3. Определение авторства Классификация произведений различных авторов

Предположим, некто содержит большую библиотеку электронных текстов. Благодарные читатели со всего света посылают владельцу библиотеки txt-версии понравившихся им книг, пополняя основную коллекцию.

Допус ТИМ, один из читателей прислал весьма интересный рассказ, но вот незадача - забыл указать (или просто не знает) его автора. Скорее всего, в

Здесь Т - размер словаря, то есть общее количество различных слов (поскольку речь идёт о текстовых документах, под словами подразумеваются обычные слова русского языка), встречающихся в документах коллекции. Числа w,., Wjj,w. символизируют веса (или значимость ) отдельных слов в документе D..

Определение весов - это уже другая задача. Например, её классическое решение базируется на следующих наблюдениях.

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

Вес зависит также от наибольшей частоты слова, найденной в процессе анализа документа. Если слово принтер встретилось в тексте десять раз - это много или мало? Зависит от частоты других слов. Например, если самое популярное слово ( винчестер ) использовалось пятнадцать раз, то вес терма принтер в данном тексте достаточно велик. Если же слово винчестер встретилось сорок раз, то текст относится скорее к винчестерам, чем к принтерам, и десятикратное вхождение слова принтер уже не впечатляет.

Используя стандартные обозначения, это наблюдение можно записать с помощью формул:

fj. = частота (количество вхождений) слова в документе]

Ц,-у шах, (У

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

Наблюдение второе. Вес слова снижается, если оно часто встречается во всей коллекции.

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

Запрограммировать метод KNN - дело техники, поэтому займёмся сначала самым важным - функцией расстояния. В её основе лежит простое наблюдение: даже в схожих ситуациях разные люди склонны употреблять разные слова и разные словосочетания. Это, по-видимому, в особенности относится к словосочетаниям. Вероятно, описывая солнце, корову или табуретку, большинство писателей так и напишут: солнце , корова , табуретка . В словосочетаниях простора для фантазии больше. Говоря об одном и том же летнем дне, можно сказать горячее солнце , пекущее солнце , жаркое солнце ... Разные авторы подберут разные эпитеты. Если же в двух различных произведениях наблюдается сравнительно частое использование одних и тех же словосочетаний, можно сделать вывод: гфоизведения принадлежат перу одного и того же писателя.

Практическая реализация функции расстояния навеяна методикой вычисления подобия документов из задачи поисковая система и рубрикатор , но следует ей лишь частично.

Первым делом любой паре слов (wl, w2) каждого документа коллекции сопоставляется вещественное число - вероятность встретить слово w2 непосредственно за словом wl. Например, если в анализируемом документе слово солнце встречается после слова жаркое в каждом пятом случае, то паре (жаркое, солнце) сопоставляется число 1/5.

Далее для двух сравниваемых документов определяется список пар слов, найденных в каждом документе по отдельности. Если в одном документе пара жаркое солнце найдена, а в другом нет, она не будет участвовать в вычислении расстояния.

Соответствующие парам вероятности записываются в два различных вектора (вектор первого документа D1, вектор второго документа D2), после чего расстояние вычисляется с помощью формулы нормализованного скалярного произведения:

Distance(Dj, D) = 1 - (D D,) / IIDJI IIDJI

Теперь приступим к программированию. Здесь в первую очередь потребуется реализация алгоритма KNN. Функция Classify() принимает в качестве параметров новый элемент коллекции, описание существующих кластеров и число N, а возвращает номер кластера, соответствующий классифицируемому элементу Описание кластеров представляет собой вектор списков элементов. К-й элемент вектора является К-м кластером коллекции.

служебная функция для сортировки пар (расстояние, кластер) bool Less(pair<double, int> Ihs, pair<double, int> rhs) { return Ihs.first < rhs.first; }

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

Эта задача входит в компетенцию методов стилометрии, то есть компьютерного анализа стиля писателя. Как и в задаче информационного поиска, главное здесь - изобретение адекватной метрики для множества документов. Имея кластеризованную (распределённую по авторам) коллекцию и метрику, с помощью метода KNN можно найти наиболее подходящий кластер для нового текстового файла.

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

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

разные авторы обычно используют предложения разной длины;

лексиконы писателей различаются (особенно интересно изучить любимые слова - то есть слова, в целом по коллекции встречающиеся гораздо реже, чем у данного конкретного автора);

в дополнение к частоте использования отдельных слов, интересно иззить употребление писателем словосочетаний, состоящих из двух-трёх слов.

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

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

Решение

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

определить номер победившего кластера

return max element(Votes.begin() , Votes.end()) - Votes.begin();

Следующий этап - реализация типа данных документ и функции расстояния:

struct Document {

сопоставляет паре (wl, w2) вероятность появления w2 после wl map<pair<string, string>, double> Prob;

загрузить документ из файла Document(const string filename) {

map<pair<string, string>, int> Freq; частота пары (wl, w2) map<string, int> Count; частота слова wl

ifstream file(filename.c str()); string wl, w2;

file wl;

while(file w2) пока не конец файла

{ обновить Count и Freq

Count[wl]++;

Freq[make pair(wl, w2)]++;

wl = w2;

преобразовать частоту в вероятность:

вероятность встретить слово w2 после wl равна

частоте встречаемости пары (wl, w2),

делённой на частоту встречаемости слова wl

for(tnap<pair<string, string>, int>:: iterator p = Freq.begin {);

p 1= Freq.endO ; p+ + ) Prob[p->first] = p->second / double(Count[p->first.first]);

double Distance (const Documents dl, const DocumentSc d2) {

список словосочетаний, встречающихся в обоих документах set<pair<string, string> > Pairs;

цикл по всем парам первого документа

for(map<pair<string, string>, double>::const iterator p = dl.Prob.beginO;p != dl.Prob.end(); p++) если пара найдена и во втором документе if(d2.Prob.find(p->first) != d2.Prob.end()) Pairs.insert(p->first);

если документы вообще не пересекаются, расстояние между ними максимально if(Pairs.empty О) return 1;

вычислить скалярное произведение векторов (Р) double Р = 0;

for(set<pair<string, string> >:riterator p = Pairs.begin();

p 1= Pairs.endO; p++) P += dl.Prob.find(*p)->second * d2.Prob.find(*p)->second;

вычислить квадрат нормы каждого из векторов double si = О, s2 = 0;

for(set<pair<string, string> >::iterator p = Pairs.begin();

p != Pairs.endO; p++)

si += dl.Prob.find(*p)->second * dl.Prob.find(*p)->second; s2 += d2.Prob.find(*p)->second * d2.Prob.find(*p)->second;

return 1 - P / (sqrt(sl)*sqrt(s2));

template <class Туре>

int Classify(const Туре& Object, const vector<list<Type> >& Clusters, int N) {

список голосующих элементов (расстояние, номер кластера) list<pair<double, int> > VotingList;

для каждого элемента коллекции *р вычислить расстояние до Object и поместить пару (расстояние, кластер элемента) в список VotingList

for(unsigned i = 0; i < Clusters.size(); i++)

for(list<Type>::const iterator p = Clusters[i].begin();

p != Clusters [i] .endO ; p++) VotingList.push back(pair<double, int>(Distance(Object, *p), i));

отсортировать список по возрастанию расстояния VotingList.sort(Less);

vector<int> Votes(Clusters.size());

list<pair<double, int> >::iterator p = VotingList.begin(); подсчитать количество голосов первых N членов (Votes[к] - количество голосов за кластер к) for(int i = 0; i < N; i++)

{ Votes[p->second]++; p++; }