Yuri_K: Для сравнения документов мы используем собственные разработки, в основе которых лежат семантические и лингвистические инструменты. Общий смысл сводиться к тому, чтобы не привязываться к конкретным словам которые содержаться в документе, а попытаться работать на уровне смысла информации. Для этого мы преобразуем документ в особый семантический индекс, который получается уникальным для каждого документа, и что самое главное - позволяет нам проводить сравнение самых разных документов - ну например многостраничного сайта и документа MS Word.
Ну и вторая фишка это лингвистические базы. В семантическом индексе информация содержится в особой абстрагированной форме. Это значит, что если 2-а документа написаны про одно и тоже, но разными авторами разными словами и в разных стилях (например научном и литературном) то наш компаратор все равно покажет высокую степень проксимити (похожести), т.к. конкретные речевые конструкции для него имеют мало значения.
Вы используете тезаурус для построения семантического индекса? И где можно почитать по подробнее об инструменте?
Yuri_K: Сложные и навароченные тулы для сематического (по смыслу) сравнения документов с возможностью задавать степень proximity (похожести) интересуют?
А на основе каких алгоритмов, построен инструмент?
dfo: интересный метод, немного неконкретное описание. Вы не описали его в какой-нибудь статье?
каковы тестовые результаты? проверяли на больших наборах текстов?
"больший вес имеют слова из "редких" букв" - это Ваша идея, или где-то уже описана?
dfo: интересно, разрабатывал ли кто-нибудь это предположение..
вроде как может сгодиться для построения кластеров (дубликатов, или, например, стилистических, тематических..)
Не пойдет. Ципф-Мандельброт может сгодиться только как теоретическая основа. Вряд ли с его помощью можно отловить различных авторов. Да даже практически наверняка нельзя.
Есть еще куча всего. Но лучше все же воспользоваться шинглами - просто и эффективно. Только вот с выбором порога сходства замучаетесь. Но с другой стороны так во всех методах.
!Иван FXS: Без статистики не обойтись, а без лингвистики - не построить объект для статистической обработки.
.
Ну от чего же без лингвистики не построить обект? Если конечно не считать приведение к нормальной форме - лингвистикой, то можно обойтись и без нее. Работать с частотами одно-, двух-, трехсловных конънктов.
Но у меня ощущение, что лингвистический подход (в частности использование тезауруса для автоматического индесирования) - должен дать гораздо более лучшие результаты, чем использование исключительно статистических методов.
eshum: Причем N должно быть константным в пределах всей коллекции документов.
Совсем не факт. В таком случае количество сохраненных шинглов будет прямо пропорционально количеству всех шинглов (равному n-9 для 10-словного шингла, где n-число слов в тексте) для всего текста. Оно вам надо?
В таком случае либо Вы будите хранить избыточное количество шинглов для больших по объему текстов, либо недостаточное количество для малых.
Из этой ситуации можно выкрутиться используя ранжирование текстов и сохраняя для текстов одного ранга шинглы кратные одному числу. Но для того, чтобы можно было сравнивать документы разных рангов, нужно чтобы эти числа тоже были кратны (например 10, 20 и 40) для документов разбитых на три ранга в зависимости от объема.
Как писал eshum Кажется понял. Т.е. Вы предпологаете что документы разной длины всегда различны если они не находятся в пределах одного ранга.
Да нет же. Страницы на границе рангов вполне могут быть "почти похожими". Я уж и не знаю как объяснить.
Хотя...
может быт, это и не такая плохая идея. Для повышения скорости можно сравнивать только документы объем которых различается не более чем в заранее заданное число раз. Так как если документы отличаются, например, больше чем в два раза то они не могут быть "почти похожими". Хотя, стоит оговорится, если необходимо помимо почти-дубликатов определять и включенность, то этот метод не прокатит.
А так, при поиске документа 3-го ранга среди ранее сохраненных шинглах документов 1-х рангов прийдется либо пересчитывать шинглы "на лету" для всех документов 1-го ранга, либо хранить все шинглы и при поиске брать только кратные искомому.
...либо хранить все шинглы и при поиске брать только кратные искомому. Но это только для документов разных рангов! Для документов же одних рангов, будем брать все шинглы имеющие кратность соответствующую данному рангу. Например
Как писал eshum А если прийдется сравнивать наоборот, 3-й ранг (шинглы кратны 40) с 1-м рангом (шинглы кратны 10), ведь 40 не кратно 10?
Сравнить 3-й с 1-м рангом при кратности шинглов 10 нельзя по принципиальным причинам (иначе Вам необходимо хранить для 3-го ранга шинглы кратные 10, что самом по себе убивает весь смысл в разделении на ранги).
3-й ранг сравнивается с 1-м точно так же как и 1-й с 3-м. Какая разница? Просто для сравнения из шинглов 1го ранга кратных 10 берутся только шинглы кратные 40-ка.
Для сравнения документов мы используем собственные разработки, в основе которых лежат семантические и лингвистические инструменты. Общий смысл сводиться к тому, чтобы не привязываться к конкретным словам которые содержаться в документе, а попытаться работать на уровне смысла информации. Для этого мы преобразуем документ в особый семантический индекс, который получается уникальным для каждого документа, и что самое главное - позволяет нам проводить сравнение самых разных документов - ну например многостраничного сайта и документа MS Word.
Ну и вторая фишка это лингвистические базы. В семантическом индексе информация содержится в особой абстрагированной форме. Это значит, что если 2-а документа написаны про одно и тоже, но разными авторами разными словами и в разных стилях (например научном и литературном) то наш компаратор все равно покажет высокую степень проксимити (похожести), т.к. конкретные речевые конструкции для него имеют мало значения.
Вы используете тезаурус для построения семантического индекса? И где можно почитать по подробнее об инструменте?
Сложные и навароченные тулы для сематического (по смыслу) сравнения документов с возможностью задавать степень proximity (похожести) интересуют?
А на основе каких алгоритмов, построен инструмент?
интересный метод, немного неконкретное описание. Вы не описали его в какой-нибудь статье?
каковы тестовые результаты? проверяли на больших наборах текстов?
"больший вес имеют слова из "редких" букв" - это Ваша идея, или где-то уже описана?
Смотрите здесь: http://www.livejournal.com/community/ru_ir/7911.html
Как раз в статье я его описал (раз Яндекс почему то этого не сделал), но в интернете ее нет.
интересно, разрабатывал ли кто-нибудь это предположение..
вроде как может сгодиться для построения кластеров (дубликатов, или, например, стилистических, тематических..)
Не пойдет. Ципф-Мандельброт может сгодиться только как теоретическая основа. Вряд ли с его помощью можно отловить различных авторов. Да даже практически наверняка нельзя.
Шинглы достаточно просты а реализации. Можно также посмотреть SVM (Метод Опорных Векторов) http://svmlight.joachims.org/ (где то встречал статью, где описывается его применение к определению дубликатов, но думаю это не самый легкий вариант), а так же метод k-ближайших соседей (k-Nearest Neighbors, k-NN) (здесь например можно на русском посмотреть http://www.spc-consulting.ru/DMS/Machine%20Learning/MachineLearning/Overviews/KNearestNeighborsIntroductoryOverview%20.htm). Этот метод хорош тем, что при добавлении нового документа его не надо заново обучать на все выборке.
Есть еще куча всего. Но лучше все же воспользоваться шинглами - просто и эффективно. Только вот с выбором порога сходства замучаетесь. Но с другой стороны так во всех методах.
Как можно решить какие алгоритмы хороши, какие нет, если их не проверять в реальных условиях?
Следует отличать ИДЕИ алгоритмов и РЕАЛЬНЫЕ алгоритмы.
Многое зависит от ЦЕЛИ, для которой создается поисковая машина.
Трудно ожидать, что на форуме возможно собрать все хорошее, что опубликовано в:
trec.nist.gov
sigir.org
www10.org, www2002.org
и т.д.
2bvd
Спасибо за ссылки. Отличные материалы.
Без статистики не обойтись, а без лингвистики - не построить объект для статистической обработки.
.
Ну от чего же без лингвистики не построить обект? Если конечно не считать приведение к нормальной форме - лингвистикой, то можно обойтись и без нее. Работать с частотами одно-, двух-, трехсловных конънктов.
Но у меня ощущение, что лингвистический подход (в частности использование тезауруса для автоматического индесирования) - должен дать гораздо более лучшие результаты, чем использование исключительно статистических методов.
Причем N должно быть константным в пределах всей коллекции документов.
Совсем не факт. В таком случае количество сохраненных шинглов будет прямо пропорционально количеству всех шинглов (равному n-9 для 10-словного шингла, где n-число слов в тексте) для всего текста. Оно вам надо?
В таком случае либо Вы будите хранить избыточное количество шинглов для больших по объему текстов, либо недостаточное количество для малых.
Из этой ситуации можно выкрутиться используя ранжирование текстов и сохраняя для текстов одного ранга шинглы кратные одному числу. Но для того, чтобы можно было сравнивать документы разных рангов, нужно чтобы эти числа тоже были кратны (например 10, 20 и 40) для документов разбитых на три ранга в зависимости от объема.
Надеюсь изложил свою мысль не слишком сумбурно.
Кажется понял. Т.е. Вы предпологаете что документы разной длины всегда различны если они не находятся в пределах одного ранга.
Да нет же. Страницы на границе рангов вполне могут быть "почти похожими". Я уж и не знаю как объяснить.
Хотя...
может быт, это и не такая плохая идея. Для повышения скорости можно сравнивать только документы объем которых различается не более чем в заранее заданное число раз. Так как если документы отличаются, например, больше чем в два раза то они не могут быть "почти похожими". Хотя, стоит оговорится, если необходимо помимо почти-дубликатов определять и включенность, то этот метод не прокатит.
А так, при поиске документа 3-го ранга среди ранее сохраненных шинглах документов 1-х рангов прийдется либо пересчитывать шинглы "на лету" для всех документов 1-го ранга, либо хранить все шинглы и при поиске брать только кратные искомому.
...либо хранить все шинглы и при поиске брать только кратные искомому. Но это только для документов разных рангов! Для документов же одних рангов, будем брать все шинглы имеющие кратность соответствующую данному рангу. Например
док1 (ранг1):
19734298510
44578957880
36719111850
94235456700
док2 (ранг2):
54887592520
52856783240
Сравниваем только:
из док1 - 44578957880, 94235456700
из док2 - 54887592520, 52856783240
А если прийдется сравнивать наоборот, 3-й ранг (шинглы кратны 40) с 1-м рангом (шинглы кратны 10), ведь 40 не кратно 10?
Сравнить 3-й с 1-м рангом при кратности шинглов 10 нельзя по принципиальным причинам (иначе Вам необходимо хранить для 3-го ранга шинглы кратные 10, что самом по себе убивает весь смысл в разделении на ранги).
3-й ранг сравнивается с 1-м точно так же как и 1-й с 3-м. Какая разница? Просто для сравнения из шинглов 1го ранга кратных 10 берутся только шинглы кратные 40-ка.