Тематическая кластеризация документов

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

Уф, я тут сообразил все... И не надо ждать два дня. Просто у меня от долгого дебаггинга мозги заклинило, и вопрос показался сложней, чем на самом деле.

Значит так, иерархия тем у меня строится следующим образом:

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

Потом делаю цикл по уровням, но не с самого верхнего - нулевого, а со следующего - первого.

Внутри цикла по уровням делаю цикл по темам текущего уровня.

Внутри цикла по темам текущего уровня - цикл по темам старшего уровня.

Для каждой темы старшего уровня вычисляю релевантность к текущей теме текущего уровня.

Делается это так: в цикле по всем урлам перемножаются релевантности урла к теме текущего уровня и к теме старшего уровня, произведния суммируются и сохраняются до конца цикла по темам старшего уровня.

Затем находится тема старшего уровня с наибольшей релевантностью и считается родительской. (Можно, также, найти вторую, третью, энную тему по релевантности, чтобы родительских тем было несколько.)

Все.

Может показаться, что это очень долго, но у меня база из 35 тыс. урлов, и все обрабатывается где-то за 1.5 часа на моем PII, 400MHz.

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

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

Сейчас у меня урлов, как я уже сказал, 35000, а тем - около 500, которые я разбиваю на 7 уровней, в самом большом из которых тем - около 200.

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

На этот случай есть идеи по совершенствованию:

1.

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

2.

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

3.

Можно не регенерировать все дерево тем сразу, а менять родителей у любого числа тем, хоть у одной только. Объем требуемой памяти (все необходимые данные по урлам у меня на время регенерации загружаются в память) это не уменьшит, но время сократит. А то, что номера уровней у части тем старшего уровня изменятся, никого не колышет, т. к. номера уровней нужны только для регенерации тем, а все остальные сервисы пользуются ссылками на родительские темы.

Стоп, одну принципиальную проблему углядел: в случае с контекстным поиском непонятно, как загрузить в память все данные, необходимые для вычисления релевантности урла к каждой теме... У меня-то это легко, потому что данных этих немного - 128 байт на урл всего. Будем думать.

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

Осталось выяснить самое малое - по каким признакам считается релевантность урла теме, почему тем всего(!) 500 и взято 7 уровней?

По каким признакам вычисляется релевантность урла к теме у меня - это невозможно объяснить, не описывая весь алгоритм обработки посещений. А у Тринка, как я понял, есть свой алгоритм.

Почему тем всего 500: мои темы - это не ключевые слова. В реальной работе системы они, по идее, должны появляться при регистрации нового ресурса, когда владелец захочет указать его тематику. Кстати, он может этого и не делать, тогда система сама привяжет ресурс к существующим темам. А пока я сделал так - взял несколько десятков тем, которые лично меня интересовали, просмотрел рэмблеровские топ100, изменил названия нескольких рубрик и придумал по несколько подрубрик к каждой рубрике. Формат данных у меня позволяет обрабатывать до 2^31 тем. А если будет медленно, то использую те идеи по ускорению, о которых писал, или займусь распараллеливанием на несколько процессоров, тогда мой шеф будет в восторге, он как раз параллельными вычислениями интересуется.

Почему на семь уровней? Потому что при тех значениях посещаемости, которые сейчас установлены (совершенно от фонаря, кстати) это - максимальное число, при котором получается приличное число тем в каждом уровне.

Я сейчас решаю немного не такую задачу

У меня скорее не рубрикация а кластеризация

То есть на перед для какого то набора документов не задается не списка тем ни уровней

Система должна сама построить его

Пробовал разные классические алгоритмы но результатом был не доволен

После этого ввел массу мелких изменений которые влияли как на качество так и на требования к вычислительным ресурсам и в принципе сейчас имею достаточно неплохие результаты

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

А на счет изложения Северина то Вячеслав прав -- самые наукоемкие моменты это реализация подсчета релевантности и структуры данных которыми задается дерево тем

Для справки - Яндекс Ньюз ничего особо не кластеризует - там идет обычный экспорт в XML заранее рубрицированных источником новостей. Так что задача сводится к тому, чтобы выбрать из заголовка (и возможно резюме) новости наиболее важные ключевые слова и создать специальный запрос, который будет выдавать все "похожие" новости.

Ничего особо героического в этом нет и не совсем понятно, зачем так надувать щеки от осознания собственной крутизны :)

А можно ли где-то глянуть на полученные результаты?

Мне кажется вы неправы на счет яндекс ньюз

Щеки они действительно раздувают в словах синонимах к слову "выдающееся"

Но если внимательно изучить результаты запроса то окажется что в один кластер ложатся новости из совершенно разных источников и они относятся к теме которая возникла только сегодня

Поэтому я исключаю возможность ручного формирования тем

Это был бы просто непосильный труд

Хотя все может быть.

А свои результаты могу разве что выслать на мыло

В вебе у меня ничего не висит

Vyacheslav Tikhonov,

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

Вроде никто и не говорил, что это делается вручную. В XML, который они получают, уже указана рубрика новости, причем указана сайтом-источником, то есть никакой рубрикации новостей Яндекс сам не проводит. А темы, как я уже сказал, собираются в кластер элементарно.

Пример - берем новость

Шеварднадзе получил письмо от Буша .

Подобрать все новости по этой же теме несложно - извлекаем ключевые слова, например, существительные - Шеварнадзе, письмо, Буш.

Теперь автоматически формируем запрос.

Документы в выдаче слишком отличаются от кластера , который показывает по этой теме Яндекс? :)

На счет ручного труда -- согласен.

Просто я в самом начале непонял откуда беруться темы.

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

Но попробуйте применить его для одной из больших тем с несколькими десятками новостей и вы получите плохой результат.

Возможно в ваших словах и есть рациональное зерно но сказать так у них все работает или нет можно только после серьезных экспериментов на которые конечно же ни у кого нету времени. А так остается слишком много "но"

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

На мой взгляд так поступили и ребята из яндекса.