Зеркало сделал, для тех, у кого основной сервер не грузится:
http://astrolabe.best-host.ru
Приобрел под этот проект домен второго уровня:
http://aslb.ru
Да, некоторые уже жаловались, что им fatal.ru не виден. Ну что ж поделаешь, бесплатный хостинг есть бесплатный хостинг. Я все хорошо вижу.
Ну вот, наконец готово.
http://astroljabija.webhost.ru
Там пока зарегистрировано только два моих сайта и только один человек.
К тому же, это моя первая работа на Перле, поэтому ужасно боюсь, что допустил какой-нибудь ляп с безопасностью и надежностью.
Но по крайней мере, из этого сайта можно понять как это должно работать.
Интерфейс, естественно, может быть разный, главное - алгоритм, а тот же алгоритм может быть встроен в интернет-пейджеры типа ICQ, использован для адресного показа баннеров и даже для обработки статистики звонков в мобильниках.
Слишком многое еще неизвестно. Известно только, что на обработку одного посещения процессорного времени тратится немногим больше, чем на обычный счетчик - примерно 10^-3 c. Но неизвестно самое главное - сколько посещений потребуется, чтобы адекватно определить тематику ресурса? Допустим - 100. А дальше все зависит от того, сколько у нас будет пользователей и насколько активно они будут пользоваться нашими сервисами.
Можно встроить мой алгоритм в интернет-пейджер типа ICQ или Odigo. В Одиго уже есть поиск людей по интересам, а у меня будет более продвинутый плюс поиск ресурсов по интересам. Пусть наш пейджер не будет столь же популярен как аська и другие старые пейджеры, но допустим у него наберется хотя бы миллион пользователей. А общее число пользователей интернета исчисляется сотнями миллионов.
Если по-прежнему держаться той гипотезы, что нужно 100 посещений наших пользователей, и наши пользователи составляют 1/100 всех пользователей Интернета, значит, чтобы ресурс адекватно включился в нашу сеть, нужно, чтобы его посетило 10000 чел.
Вопрос был про иерархическую структуру - я на него и ответил. Подразумевалось, что кластеры уже есть, но они пока равноправны и проблема только в том, как построить из них дерево. А как сделать сами кластеры - тут, конечно, мой опыт ничем не поможет.
Был у меня один знакомый, который как раз кластеризацией занимался, но сейчас уехал куда-то за границу, кажется в Англию, и на письма не отвечает. Одно время он в livejournal часто пописывал, может там его можно отловить, но адрес потерялся после того, как мне пришлось закарантинить свой почтовый ящик, зараженный нелечимым вирусом. Будет время - открою его со всеми необходимыми предосторожностями и посмотрю.
По каким признакам вычисляется релевантность урла к теме у меня - это невозможно объяснить, не описывая весь алгоритм обработки посещений. А у Тринка, как я понял, есть свой алгоритм.
Почему тем всего 500: мои темы - это не ключевые слова. В реальной работе системы они, по идее, должны появляться при регистрации нового ресурса, когда владелец захочет указать его тематику. Кстати, он может этого и не делать, тогда система сама привяжет ресурс к существующим темам. А пока я сделал так - взял несколько десятков тем, которые лично меня интересовали, просмотрел рэмблеровские топ100, изменил названия нескольких рубрик и придумал по несколько подрубрик к каждой рубрике. Формат данных у меня позволяет обрабатывать до 2^31 тем. А если будет медленно, то использую те идеи по ускорению, о которых писал, или займусь распараллеливанием на несколько процессоров, тогда мой шеф будет в восторге, он как раз параллельными вычислениями интересуется.
Почему на семь уровней? Потому что при тех значениях посещаемости, которые сейчас установлены (совершенно от фонаря, кстати) это - максимальное число, при котором получается приличное число тем в каждом уровне.
Уф, я тут сообразил все... И не надо ждать два дня. Просто у меня от долгого дебаггинга мозги заклинило, и вопрос показался сложней, чем на самом деле.
Значит так, иерархия тем у меня строится следующим образом:
Сначала я все темы сортирую по посещаемости (в твоем случае - по частоте). Потом разбиваю темы по посещаемости на N уровней. Важно подобрать N так, чтобы в каждом уровне была хотя бы одна тема.
Потом делаю цикл по уровням, но не с самого верхнего - нулевого, а со следующего - первого.
Внутри цикла по уровням делаю цикл по темам текущего уровня.
Внутри цикла по темам текущего уровня - цикл по темам старшего уровня.
Для каждой темы старшего уровня вычисляю релевантность к текущей теме текущего уровня.
Делается это так: в цикле по всем урлам перемножаются релевантности урла к теме текущего уровня и к теме старшего уровня, произведния суммируются и сохраняются до конца цикла по темам старшего уровня.
Затем находится тема старшего уровня с наибольшей релевантностью и считается родительской. (Можно, также, найти вторую, третью, энную тему по релевантности, чтобы родительских тем было несколько.)
Все.
Может показаться, что это очень долго, но у меня база из 35 тыс. урлов, и все обрабатывается где-то за 1.5 часа на моем PII, 400MHz.
Чтобы не подвешивать на это время сервер, я делают так: копирую всю базу на другой компьютер и регенерирую дерево тем на нем, а результат, т. е. иерархическую структуру, записываю в специальный файл. Потом этот файл гружу на сервер и там уже из него записываю структуру в БД. В итоге сервер доступен все время, даже во время загрузки новой структуры, т. к. структура состоящая из наполовину незатертой старой и наполовину загруженной новой тоже вполне работоспособна.
Легко сообразить, что время обработки растет пропорционально первой степени количества урлов и квадрату количества тем в одном уровне.
Сейчас у меня урлов, как я уже сказал, 35000, а тем - около 500, которые я разбиваю на 7 уровней, в самом большом из которых тем - около 200.
Возможно трудности возникнут не только из-за увеличения базы, но и из-за более медленного вычисления релевантности темы к урлу, у меня-то она вычисляется очень быстро в силу особенностей алгоритма.
На этот случай есть идеи по совершенствованию:
1.
Можно для каждого урла хранить релевантность к текущей теме текущего уровня до окончания цикла по темам старшего уровня. Я этого не делаю только потому, что и так считается достаточно быстро, а память для меня более критична, чем время.
2.
Можно пользоваться не всем массивом урлов, а случайной выборкой, и только если максимальная релевантность окажется ниже некоторого предела (у особенно редких тем) - загружать другую случайную выборку.
3.
Можно не регенерировать все дерево тем сразу, а менять родителей у любого числа тем, хоть у одной только. Объем требуемой памяти (все необходимые данные по урлам у меня на время регенерации загружаются в память) это не уменьшит, но время сократит. А то, что номера уровней у части тем старшего уровня изменятся, никого не колышет, т. к. номера уровней нужны только для регенерации тем, а все остальные сервисы пользуются ссылками на родительские темы.
Стоп, одну принципиальную проблему углядел: в случае с контекстным поиском непонятно, как загрузить в память все данные, необходимые для вычисления релевантности урла к каждой теме... У меня-то это легко, потому что данных этих немного - 128 байт на урл всего. Будем думать.
Вот так, в общем. Понимаю, что алгоритм не без недостатков, но повторюсь, это далеко не главная часть моей работы, основное у меня - анализ посещений, а алгоритм построения дерева тем я придумал почти наспех, первый, какой пришел в голову.
Ну та же, что и у тебя. Точнее - это одна из двух, вторая - поиск людей по интересам, ну там знакомства, друзья, единомышленники. Ведь анализ посещений - штука обоюдоострая, он и посетителей анализирует так же, как и посещаемые ресурсы.
Нет, я в Москве.
KIAM (из моего е-мэйловского адреса) - это Keldysh Institute of Applied Mathematics - Институт прикладной математики им. М.В.Келдыша.
Как это все работает - долго объяснять. Получается или нет - трудно сказать, система ведь самообучающаяся, по-настоящему ее можно проверить только на группе тестировщиков, когда она будет запущена.
Насчет построения тематической иерархии я тебе попытаюсь помочь - это второстепенная часть моего алгоритма и от основной она слабо зависит, но надо все-таки немного подумать, как ее адаптировать к твоей задаче. Подожди до завтра или послезавтра.
