Ключевой и наиболее ресурсоемкий этап работы алгоритма kNN H расчет матрицы ближайших соседей для примеров, подлежащих классификации. Для коллекций документов размером 100 000 и более расчет матрицы близости требует значительных вычислительных ресурсов. Разработка более быстрых алгоритмов является нетривиальной задачей.
В данной работе будут рассмотрены несколько алгоритмов вычисления матрицы близости: очевидный метод расчета «в лоб», методы, описанные в литературе, и разработанный нами эффективный алгоритм. Этот алгоритм позволяет рассчитать матрицу 100 ближайших соседей для 1.54 миллионной коллекции документов за 1 неделю работы кластера из четырех обычных компьютеров (3 GHz CPU, 2 Gb RAM), что примерно на порядок быстрее, чем наилучший из известных методов, опубликованный в работе [5] в 2008 г.
2. Постановка задачи. На вход алгоритма поступают две коллекции текстовых документов, D1 и D2. Результатом работы алгоритма является матрица близости: для каждого документа d из коллекции D1 набор из не более k документов коллекции D2, наиболее близких к d по определенной мере оценки близости документов.
Опишем стандартный [6] способ вычисления меры оценки близости документов.
Первым этапом работы алгоритма является преобразование текстов документов в векторы в пространстве признаков. Все слова, встретившиеся в документе, приводятся к нормальной форме (так называемые «леммы»). Вес слова для этого документа вычисляется по формуле TF*IDF [6, 7], которая учитывает частоту вхождения слова в документ и количество документов коллекции, содержащих данное слово. Мы используем широко распространенный вариант формулы TF*IDF – BM25 INQUERY [7]:
В
(1) tfD(l)
(«term
frequency»)
– учет частотности леммы в документе; freqD(l)
– частотность леммы l в
документе, dlD
– мера длины документа, avg_dl
– средняя длина документа, β = 0.4, idf(l)
(«inverse
document frequency») – фактически форма штрафования
часто
используемых в коллекции слов, |c| – количество документов в
коллекции, df(l) – количество документов, где встретилaсь
лемма l.
Таким образом, текстовый документ преобразуется в вектор признаков в пространстве Rn, где n – количество различных (нормализованных) слов, встретившихся в коллекции документов. Слова, встретившиеся в документе, получают ненулевой вес, вес остальных слов равен нулю.
Задача расчета ближайших соседей для коллекции документов имеет высокую вычислительную сложность. Типичными характеристиками задачи являются:
• размер коллекции документов – от 104 до 108;
• размерность пространства признаков – от 104 до 107;
• количество ненулевых компонент вектора признаков (слов документа); в среднем для каждого документа – от 100 до 10 000;
• количество соседей k – от 10 до 100.
В качестве меры оценки близости документов x ∈ D1 и y ∈ D2 используем косинус между векторами документов в пространстве признаков:
Таким образом, текстовый документ преобразуется в вектор признаков в пространстве Rn, где n – количество различных (нормализованных) слов, встретившихся в коллекции документов. Слова, встретившиеся в документе, получают ненулевой вес, вес остальных слов равен нулю.
Задача расчета ближайших соседей для коллекции документов имеет высокую вычислительную сложность. Типичными характеристиками задачи являются:
• размер коллекции документов – от 104 до 108;
• размерность пространства признаков – от 104 до 107;
• количество ненулевых компонент вектора признаков (слов документа); в среднем для каждого документа – от 100 до 10 000;
• количество соседей k – от 10 до 100.
В качестве меры оценки близости документов x ∈ D1 и y ∈ D2 используем косинус между векторами документов в пространстве признаков:
где
n – размерность
пространства признаков (количество различных слов в коллекции); xi,
yi
– TF*IDF-вес i-го признака
документа x и y соответственно.
Формула (2) может быть записана в более простом виде, если веса слов документа нормализовать:
Формула (2) может быть записана в более простом виде, если веса слов документа нормализовать:
3.
Известные подходы. Рассмотрим
различные варианты вычисления k
ближайших соседей для коллекции документов. Пусть на вход алгоритма
подаются коллекции D1
и D2
обработанных документов,
представленных как векторы признаков. А именно, в виде таблицы значений
(doc_id, word_id, weight), где doc_id – идентификатор
документа,
word_id – идентификатор слова, weight –
нормализованный вес
слова в документе.
Существующие алгоритмы можно разделить на следующие категории:
1) алгоритмы, основанные на полном расчете матрицы ближайших соседей;
2) алгоритмы ускоренного поиска ближайших соседей на основе неравенства треугольника;
3) методы решения близкой задачи H поиска полудубликатов документов.
В п. 3 будут описаны известные алгоритмы. Начнем с анализа приближенных методов и методов, основанных на неравенстве треугольника, и покажем, что они не применимы для поиска близких документов по полным текстам. Затем опишем три алгоритма, основанных на полном расчете: очевидный алгоритм расчета по прямому индексу документов и два алгоритма, опубликованных в литературе. В п. 4 опишем разработанный нами алгоритм. Экспериментальная оценка скорости работы различных алгоритмов представлена в п. 5.
3.1. Близкие задачи: методы поиска полудубликатов. Методы поиска почти одинаковых документов используются для удаления дублей при индексировании web [8, 9] и выявления плагиата [10]. Для эффективного поиска полудубликатов применяются методы индексирования документов на основе выделения специальных факторов, выделяемых из текста, называемых также шинглами [9]. При использовании метода индексирования текстов на основе шинглов документ преобразуется в вектор чисел (шинглов), обладающих следующими полезными свойствами:
1) документу сопоставляется относительно небольшое количество шинглов – порядка 10;
2) малые изменения текста документа приводят к изменениям небольшого числа шинглов в шингл4векторе документа;
3) сильное совпадение шингл4векторов документов означает высокую вероятность совпадения значительных фрагментов текстов документов.
В качестве примера опишем один из методов преобразования документа в вектор шинглов, описанный в работе [8]. Документ преобразуется во множество непрерывных (и пересекающихся) последовательностей из S слов (например, S = 10). Для каждой последовательности S слов вычисляется хэш4сумма. Из полученного набора хэш4сумм выбираются F наибольших значений, которые и образуют шингл-вектор документа.
Для рассматриваемой нами задачи поиска тематически близких документов методы на основе шинглов не подходят, так как такие документы могут не иметь совпадающих фрагментов текстов.
3.2. Близкие задачи: методы на основе неравенства треугольника. Задача поиска тематически близких документов есть частный случай более общей задачи поиска близких объектов в произвольном метрическом пространстве.
Действительно, косинусная мера близости между документами соответствует евклидовой метрике близости между нормализованными векторами документов. Для нормализованных векторов x и y, все координаты которых неотрицательные, евклидово расстояние ρ (x, y) является монотонной функцией от косинусной меры:
Литература
1. Joachims T. Text Categorization with Support Vector Machines: Learning with Many Relevant Features // Proc. of ECML-98. 10th European Conference on Machine Learning. 1998. URL: http://www.cs.cornell.edu/people/tj/publications/joachims98a.ps.gz.
2. Yang Y., Liu X. A re-examination of text categorization methods // Proc. of SIGIR-99. 22nd ACM Intern. Conference on Research and Development in Information Retrieval. / eds: M. A. Hearst, F. Gey, R. Tong. New York, Berkeley: ACM Press, 1999. P. 42–49.
3. Агеев М. С., Добров Б. В., Лукашевич Н. В. Автоматическая рубрикация текстов: методы и проблемы. // Учен. зап. Казанск. гос. ун-та. Сер. Физико-математические науки. 2008. Т. 150, кн. 4. С. 25–40.
4. Агеев М. С., Добров Б. В., Лукашевич Н. В. и др. Классификация запросов и оптимизация факторов для поиска нормативных документов // Рос. семинар по оценке методов информационного поиска: Труды РОМИП’2009: cеминар в рамках Всерос. науч. конференции RCDL’2009. 16 сентября 2009 г. Петрозаводск; Санкт-Петербург: НУ ЦСИ, 2009. С. 151–162.
5. Elsayed T., Lin J., Oard D. W. Pairwise document similarity in large collections with Map-Reduce. // Proc. of the 46th Annual Meeting of the Association for Computational Linguistics on Human Language Technologies: Short papers (Columbus, Ohio, June 16–17, 2008). Human Language Technology Conference. Association for Computational Linguistics. Morristown. New Jark, 2008. P. 265–268.
6. Manning C. D., Raghavan P., Schutze H. Introduction to Information Retrieval. Cambridge, 2008. URL: http://nlp.stanford.edu/IR-book/information-retrieval-book.html.
7. Агеев М. С., Добров Б. В., Лукашевич Н. В., Сидоров А. В. Экспериментальные алгоритмы поиска/классификации и сравнение с Sbasic lineU // Рос. семинар по оценке методов информационного поиска: Труды второго рос. семинара РОМИП’2004 (Пущино, 01.10.2004). СПб: Науч.-исслед. ин-т химии С.-Петерб. ун-та, 2004. С. 62–89.
8. Зеленков Ю., Сегалович И. Сравнительный анализ методов определения нечетких дубликатов для Web-документов // Девятая Всерос. науч. конференция RCDL’2007 SЭлектронные библиотеки: Перспективные Методы и Технологии, Электронные коллекцииU. Переславль-Залесский, 2007. URL: http://rcdl.ru/doc/2007/paper6 5v1.pdf.
9. Ilyinsky S., Kuzmin M., Melkov A., Segalovich I. An efficient method to detect duplicates of Web documents with the use of inverted index // WWW-2002 – Eleventh Intern. World Wide Web Conference. URL: http://www2002.org/CDROM/poster/187/.
10. Butakov S., Scherbinin V. The toolbox for local and global plagiarism detection // Comput. Educ. 2009. Vol. 52, N 4. P. 781–788. URL: http://dx.doi.org/10.1016/j.compedu.2008.12.001.
11. Lifshits Y. Algorithms for Nearest Neighbor Search // Tutorial at RuSSIR’07. Ekaterinburg, September 2007. URL: http://simsearch.yury.name/tutorial.html.
12. Zobel J., Moffat A. Inverted files for text search engines // ACM Comput. Surv. 2006. Vol. 38 N 2 URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.105.8844rep=rep1type=pdf.
13. Сегалович И., Маслов М. Яндекс на РОМИП-2004. Некоторые аспекты полнотекстового поиска и ранжирования в Яндекс // Рос. семинар по оценке методов информационного поиска: Труды второго рос. семинара РОМИП’2004 (Пущино, 01.10.2004). СПб: Науч.-исслед. ин-т химии С.-Петерб. ун-та.
2004. С. 100–109.
14. Как работают новые Яндекс. Новости // Яндекс. 2003. URL: http://company.yandex.ru/public/ articles/smi-mirror.xml.
15. Dean J., Ghemawat S. MapReduce: simplified data processing on large clusters // Proc. of the 6th conference on Symposium on Opearting Systems Design & Implementation. San Francisco, CA. December 06–08, 2004. P. 10-10.
16. Apache Hadoop. URL: http://hadoop.apache.org/. 17. AQUAINT-2 Information-Retrieval Text Research Collection. URL: http://www.ldc.upenn.edu/ Catalog/CatalogEntry.jsp?catalogId=LDC2008T25.
18. Веб коллекция BY.web. 2007. URL: http://romip.ru/ru/collections/by.web-2007.html.
Статья рекомендована к печати проф. В. Ю. Добрыниным.
Статья принята к печати 10 марта 2011 г.
Существующие алгоритмы можно разделить на следующие категории:
1) алгоритмы, основанные на полном расчете матрицы ближайших соседей;
2) алгоритмы ускоренного поиска ближайших соседей на основе неравенства треугольника;
3) методы решения близкой задачи H поиска полудубликатов документов.
В п. 3 будут описаны известные алгоритмы. Начнем с анализа приближенных методов и методов, основанных на неравенстве треугольника, и покажем, что они не применимы для поиска близких документов по полным текстам. Затем опишем три алгоритма, основанных на полном расчете: очевидный алгоритм расчета по прямому индексу документов и два алгоритма, опубликованных в литературе. В п. 4 опишем разработанный нами алгоритм. Экспериментальная оценка скорости работы различных алгоритмов представлена в п. 5.
3.1. Близкие задачи: методы поиска полудубликатов. Методы поиска почти одинаковых документов используются для удаления дублей при индексировании web [8, 9] и выявления плагиата [10]. Для эффективного поиска полудубликатов применяются методы индексирования документов на основе выделения специальных факторов, выделяемых из текста, называемых также шинглами [9]. При использовании метода индексирования текстов на основе шинглов документ преобразуется в вектор чисел (шинглов), обладающих следующими полезными свойствами:
1) документу сопоставляется относительно небольшое количество шинглов – порядка 10;
2) малые изменения текста документа приводят к изменениям небольшого числа шинглов в шингл4векторе документа;
3) сильное совпадение шингл4векторов документов означает высокую вероятность совпадения значительных фрагментов текстов документов.
В качестве примера опишем один из методов преобразования документа в вектор шинглов, описанный в работе [8]. Документ преобразуется во множество непрерывных (и пересекающихся) последовательностей из S слов (например, S = 10). Для каждой последовательности S слов вычисляется хэш4сумма. Из полученного набора хэш4сумм выбираются F наибольших значений, которые и образуют шингл-вектор документа.
Для рассматриваемой нами задачи поиска тематически близких документов методы на основе шинглов не подходят, так как такие документы могут не иметь совпадающих фрагментов текстов.
3.2. Близкие задачи: методы на основе неравенства треугольника. Задача поиска тематически близких документов есть частный случай более общей задачи поиска близких объектов в произвольном метрическом пространстве.
Действительно, косинусная мера близости между документами соответствует евклидовой метрике близости между нормализованными векторами документов. Для нормализованных векторов x и y, все координаты которых неотрицательные, евклидово расстояние ρ (x, y) является монотонной функцией от косинусной меры:
Для
задачи поиска близких точек в
метрическом пространстве разработан широкий класс методов эффективного
поиска, основанных на неравенстве треугольника [11].
Общая
идея этих методов заключается в
следующем. Пусть для данных x ∈ X, ε > 0 и
метрики
ρ (x, y) требуется найти множество объектов, близких к данному:
N(x) = {y ∈ X|ρ (x, y) 6 ε}. Пусть на
некотором шаге алгоритма известно, что расстояние от x до некоторой
точки z довольно
большое, ρ (x, z) > R (рисунок). Тогда для любой точки
y, если
ρ (y, z) 6 R − ε, то из неравенства
треугольника следует, что ρ (x, z) 6 ρ (x, y)
+ρ (y, z) и
ρ (x, y)
> ε, y / ∈ N (x). Если тем или иным
способом сохранить
информацию о расстояниях между некоторыми объектами, то можно не
вычислять ρ (x, y) для тех объектов y, которые находятся близко
к «далеким»
объектам z и таким образом найти N (x) быстрее, чем с помощью полного
вычисления ρ (x, y) для всех y.
Методы, основанные на неравенстве треугольника, широко применяются при индексировании географических данных, в мультимедиа и других областях, где задача обладает хотя бы одним из следующих свойств:
- объекты находятся в пространстве малой размерности (порядка 2–10);
- функция расстояния ρ (x, y) вычисляется долго по сравнению с накладными расходами на использование метрических индексов.
Нам не известны работы, в которых методы, основанные на неравенстве треугольника, успешно использовались бы для поиска похожих документов с косинусной мерой близости. На наш взгляд, эти методы не эффективны для рассматриваемой задачи, потому что для задачи поиска близких документов условие ρ (x, z) > R, ρ (y, z)
R−ε обладает
низкой селективностью и не позволяет существенно сократить вычисления.
Поясним сказанное на примере: пусть требуется найти документы, для которых cos (x, y) > 0.5 (это вполне типичный порог для близких документов по косинусной мере). Из формулы (3) следует, что cos (x, y) > 0.5 ⇔ ρ (x, y)
ε, ε = 1. Так как ρ (x, z)
√2, то R −
ε
√2
− 1 < 0.42, и, следовательно, отсечение по неравенству
треугольника можно выполнить лишь для тех документов y, которые сильно
похожи на образец z: ρ (y, z) < 0.42 (или cos (x, y)
> 0.91).
На практике это практически дубликаты. Таких документов немного
–
доли процента для больших коллекций документов.
Например, мы рассчитали среднее количество соседей, находящихся на расстоянии ρ (y, z) < 0.42, для коллекции из 100 000 документов – подмножества коллекции РО-МИП BY.WEB. Среднее количество соседей составило 121, или 0.12% документов. Таким образом, мы показали, что условие отсечения далеких документов по неравенству треугольника обладает низкой селективностью.
3.3. Алгоритм расчета по прямому индексу документов. Самый простой и очевидный способ расчета ближайших соседей состоит в том, чтобы для каждого документа вычислить расстояния до других документов коллекции, используя таблицу «документ–слово–вес», упорядоченную по паре (doc_id, word_id). Из полученного вектора расстояний выбираются k документов с наибольшими значениями cos (x, y).
Данный алгоритм можно записать в виде псевдокода:
1 Input: index D1, index D2
2 for doc_id1 in D1:
3 List dw1 := List of (word_id, weight) from D1 for doc_id1
4 Dist := Vector of |D2| floats
5 for doc_id2 in D2:
6 Dist[doc_id2] := 0
7 List dw2 := List of (word_id, weight) from D2 for
doc_id2
8 for (word_id1, weight1) in dp1:
9 for (word_id2, weight2) in dp2:
10 Dist[doc_id2] += weight1*weight2
Этот алгоритм легко реализовать на языке SQL в любой реляционной СУБД. Код на языке SQL для нахождения ближайших соседей для одного документа выглядит следующим образом:
SELECT i1.doc_id AS doc_id1,
i2.doc_id AS doc_id2,
SUM(i1.weight*i2.weight) AS cos
FROM doc_word_index i1, doc_word_index i2
WHERE i1.word_id=i2.word_id
AND i1.doc_id=:INPUT_DOC_ID
GROUP BY i1.doc_id, i2.doc_id
ORDER BY cos DESC
Возможна более эффективная по сравнению с СУБД реализация данного алгоритма: во-первых, индекс «документ–слово–вес» можно хранить в сжатом виде, с учетом избыточности повторения doc_id в соседних строках таблицы [6, 12]; во-вторых, при обработке сортированных списков (word_id, weight) для пар документов, необходимо использовать алгоритм слияния сортированных списков [12].
Асимптотическая сложность алгоритма – O (|D|2 Avg_dl ), где |D| – количество документов в коллекции, Avg_dl – среднее количество слов в документе.
Алгоритм применяет прямой просмотр таблицы «документ–слово–вес» и поэтому может быть реализован без использования индексов, хранящихся в памяти (не требуются накладные расходы на операции seek). Поэтому минимальный требуемый объем оперативной памяти – O(max(Avg_dl)) – не зависит от размера коллекции. В то же время кэширование индексов в памяти, естественно, повышает скорость работы алгоритма.
Основными достоинствами данного алгоритма являются:
1) простота реализации;
2) возможность работы с большими индексами документов, которые не помещаются в оперативную память (используется линейный проход по индексу документов);
3) легкость распараллеливания вычислений (можно производить вычисления ближайших соседей независимо для разных документов).
Основной недостаток такого алгоритма - низкая скорость работы.
3.4. Алгоритм расчета с использованием поиска по инвертированному индексу. Более эффективный алгоритм вычисления ближайших соседей можно реализовать при помощи инвертированного индекса документов – отсортированного и сжатого списка троек (word_id, doc_id, weight). Инвертированные списки известны как наиболее эффективная структура данных для выполнения поиска документов по запросу [12].
Первым этапом работы алгоритма является построение инвертированного индекса для коллекции D2. Затем для каждого документа из коллекции D1 производится поиск ближайших документов по коллекции D2. Для этого применяется алгоритм, аналогичный поиску документов по запросу пользователя [6], и в качестве запроса используется полный текст документа. В отличие от обычного поиска документов по запросу для данного алгоритма:
• используются очень длинные запросы, порядка нескольких сотен слов (это характерное количество уникальных слов в документе);
• необходим поиск документов с учетом неточного совпадения (не все слова запроса встречаются в документе);
• элементам запроса присваивается вес, соответствующий нормализованному TF*IDF весу слова в документе.
Данный алгоритм применяется, например, в системе кластеризации новостей Яндекс [13, 14]. К сожалению, указанные публикации не позволяют оценить скорость этого данного алгоритма.
Алгоритм допускает эффективное распараллеливание поиска двумя способами:
- распараллеливание по документам коллекции D2;
- поиск по нескольким индексам (распараллеливание по документам коллекции D1).
3.5. Алгоритм расчета с использованием двух инвертированных индексов и MapReduce. В статье [5] описан метод вычисления полной матрицы близости документов, в котором применяется инвертированный индекс документов и метод распараллеливания MapReduce [15] в варианте Hadoop [16].
В [5] решается задача расчета полной матрицы близости между всеми документами коллекции, однако данный алгоритм легко адаптировать для рассматриваемого несимметричного случая поиска ближайших соседей.
Алгоритм [5] состоит из следующих этапов:
1) построение инвертированного индекса с нормализованными весами слов;
2) усечение индекса выкидыванием наиболее часто встречающихся слов;
3) для всех слов коллекции:
3.1) для всех пар документов (word_id, doc_id1, weight1) и (word_id, doc_id2, weight2) выдать тройку (doc_id1, doc_id2, weight1*weight2) - операция MAP,
3.2) отсортировать тройки (doc_id1, doc_id2, w) по полям (doc_id1, doc_id2),
3.3) вычислить сумму w для каждой пары (doc_id1, doc_id2) – операция REDUCE; в результате получаем искомый результат – список троек (doc_id1, doc_id2, distance)
Алгоритм реализован на языке Java, операции по распараллеливанию вычислений и распределенная сортировка данных и суммирование на шагах 3.2–3.3 выполняются средой выполнения MapReduce–программ Hadoop. Среда выполнения также берет на себя управление памятью.
Отметим, что распределенная сортировка данных и суммирование на шагах 3.2–3.3 требуют интенсивной коммуникации между узлами сети: даже при распараллеливании на два компьютера потребуется передать по сети как минимум половину полной матрицы близости между документами, т. е. O(|D|2)троек (doc_id1, doc_id2, w).
Существенным шагом, позволяющим радикально упростить задачу и ускорить вычисление, является усечение индекса на шаге 2. Авторы [5] использовали стратегию усечения 1% наиболее часто встречающихся слов. Для коллекции 906 000 новостей, применяемых для тестирования, это составляет 9093 слова. Усечение словаря дало возможность сократить количество пар весов, вычисляемых на шаге 4 с 8 · 1012nдо 4 · 109 – в 2000 раз. Соответственно возрастает и скорость работы алгоритма.
В [5] приведены следующие данные о скорости работы алгоритма:
• коллекция документов – новостные сообщения AQUAINT42 на английском языке [17], 906 000 документов общим объемом 2.5 Гб (т. е. около 3 Кб на документ);
• количество различных слов в коллекции (без усечения слов) – 909 326;
• использование кластера из 20 компьютеров, 2.4GHz CPU, 4GB RAM;
• время вычисления матрицы близости для усеченного индекса составило 2 ч, из них 3.5 мин – на построение инвертированного индекса;
• таким образом, общее время работы для усеченного индекса – 2 · 20 = 40 часов машинного времени.
Авторы статьи [5] не произвели оценку влияния усечения индекса на качество результата. В то же время «честный» расчет похожих документов таким способом вряд ли возможен, так как при увеличении количества троек (doc_id1, doc_id2, w) в 2000 раз время работы алгоритма выросло бы пропорционально и стало бы неприемлемо большим.
4. Алгоритм расчета с использованием инвертированного индекса. Предлагаемый нами алгоритм, подобно [14, 5] использует инвертированные индексы для коллекций документов, но при этом применяется более эффективная организация вычисления ближайших соседей одновременно для множества документов:
1) пусть |D1| = M, |D2| = N; в памяти создается матрица расстояний между M×N документами, изначально инициализированная нулями;
2) для слова word_id в память загружаются соответствующие фрагменты инвертированных списков из D1 и D2;
3) далее для каждой пары документов (d1, d2) из этих фрагментов произведение весов добавляется в матрицу расстояний;
4) затем для каждой строки матрицы расстояний вычисляется k элементов с наибольшим весом.
Этот алгоритм можно записать в виде псевдокода:
1 Input: inverted index D1, inverted index D2
2 Dist := Matrix[M*N]
3 for word_id in D1:
4 List dp1 := List of (doc_id, weight) from D1 for word_id
5 List dp2 := List of (doc_id, weight) from D2 for word_id
6 for (doc_id1, weight1) in dp1:
7 for (doc_id2, weight2) in dp2:
8 Dist[doc_id1][doc_id2] += weight1*weight2
Для больших коллекций расчет ближайших соседей необходимо производить, разбив матрицу M×N документов на полосы размером m×N так, чтобы в оперативную память помещалась матрица m×N и соответствующие фрагменты инвертированного индекса для каждого из слов коллекции.
Асимптотическая сложность данного алгоритма – O(|D|2· Avg_wi), где |D| – количество документов в коллекции, Avg_wi – среднее количество документов для одного слова. Асимптотическая сложность этого алгоритма равна общему количеству операций сложения и умножения элементов матриц весов документов, и совпадает с асимптотической сложностью метода, использующего прямой индекс «документ–слово–вес», однако практическая скорость самого алгоритма на несколько порядков выше за счет эффективного использования архитектуры современных процессоров:
• Основной объем вычислений приходится на обработку наиболее частотных слов на простых операциях умножения декартова произведения двух векторов (строки 6–8 алгоритма), что позволяет эффективно работать алгоритму предсказания переходов, реализованному в современных процессорах. В то же время алгоритм расчета по прямому индексу документов выполняет обработку наиболее частотных слов в рамках менее эффективной операции слияния сортированных списков.
• Обрабатываемые данные компактно располагаются в памяти, что дает возможность эффективно использовать кэш современных процессоров.
4.1. Распараллеливание по полосам. Алгоритм расчета с помощью инвертированного индекса легко поддается распараллеливанию на кластерной архитектуре. Наиболее вычислительно сложная часть алгоритма содержит независимые вычислительные блоки, связанные с расчетом ближайших соседей для отдельной полосы m×N документов, поэтому естественным способом распараллеливания является разделение по полосам.
Каждому узлу кластера выделяется задание, состоящее из:
• инвертированного индекса коллекции D2 по N документам;
• прямого индекса документов по коллекции D1;
• интервала документов из коллекции D1, для которых необходимо вычислить k ближайших соседей.
При выполнении задания интервал документов разбивается на полосы шириной не более m, затем для каждой полосы строится инвертированный индекс и производится вычисление соседей.
Общее время выполнения параллельного алгоритма состоит из:
1) времени построения инвертированного индекса документов (на одном компьютере);
2) времени копирования индексов на узлы кластера;
3) времени параллельного расчета ближайших соседей по полосам;
4) времени объединения результатов.
В п. 5 мы покажем, что на практике время выполнения последовательных операций (шаги 1, 2 и 4) для коллекции из 1.5 млн документов составляет 0.4% общего времени работы алгоритма, и, таким образом, на такой коллекции алгоритм допускает эффективное распараллеливание приблизительно до 100 компьютеров.
При увеличении размера коллекции время построения инвертированного индекса и размер индекса растут как O(|D| log |D|) от количества документов, а время расчета ближайших соседей – как O(|D|2· Avg_wi), поэтому процент времени, затрачиваемый на последовательные операции, будет снижаться обратно пропорционально размеру коллекции и соответственно будет улучшаться масштабируемость алгоритма.
Отметим, что этап построения инвертированного индекса допускает эффективное распараллеливание. Алгоритм параллельного построения инвертированного индекса на основе технологии Hadoop MapReduce описан в [5].
4.2. Оценка максимального размера полосы. Оценим максимальный размер полосы m, доступный для вычисления на компьютере, имеющем H Гб оперативной памяти. Предположим, что для матрицы расстояний можно выделить h = 0.8H Гб (остальная память используется для фрагментов индекса и среды исполнения программы).
Пусть ячейка матрицы (накопитель расстояния) имеет размер 4 байта (float).
Тогда
Методы, основанные на неравенстве треугольника, широко применяются при индексировании географических данных, в мультимедиа и других областях, где задача обладает хотя бы одним из следующих свойств:
- объекты находятся в пространстве малой размерности (порядка 2–10);
- функция расстояния ρ (x, y) вычисляется долго по сравнению с накладными расходами на использование метрических индексов.
Нам не известны работы, в которых методы, основанные на неравенстве треугольника, успешно использовались бы для поиска похожих документов с косинусной мерой близости. На наш взгляд, эти методы не эффективны для рассматриваемой задачи, потому что для задачи поиска близких документов условие ρ (x, z) > R, ρ (y, z)
R−ε обладает
низкой селективностью и не позволяет существенно сократить вычисления.Поясним сказанное на примере: пусть требуется найти документы, для которых cos (x, y) > 0.5 (это вполне типичный порог для близких документов по косинусной мере). Из формулы (3) следует, что cos (x, y) > 0.5 ⇔ ρ (x, y)
ε, ε = 1. Так как ρ (x, z)
√2, то R −
ε
√2
− 1 < 0.42, и, следовательно, отсечение по неравенству
треугольника можно выполнить лишь для тех документов y, которые сильно
похожи на образец z: ρ (y, z) < 0.42 (или cos (x, y)
> 0.91).
На практике это практически дубликаты. Таких документов немного
–
доли процента для больших коллекций документов.Например, мы рассчитали среднее количество соседей, находящихся на расстоянии ρ (y, z) < 0.42, для коллекции из 100 000 документов – подмножества коллекции РО-МИП BY.WEB. Среднее количество соседей составило 121, или 0.12% документов. Таким образом, мы показали, что условие отсечения далеких документов по неравенству треугольника обладает низкой селективностью.
3.3. Алгоритм расчета по прямому индексу документов. Самый простой и очевидный способ расчета ближайших соседей состоит в том, чтобы для каждого документа вычислить расстояния до других документов коллекции, используя таблицу «документ–слово–вес», упорядоченную по паре (doc_id, word_id). Из полученного вектора расстояний выбираются k документов с наибольшими значениями cos (x, y).
Данный алгоритм можно записать в виде псевдокода:
1 Input: index D1, index D2
2 for doc_id1 in D1:
3 List dw1 := List of (word_id, weight) from D1 for doc_id1
4 Dist := Vector of |D2| floats
5 for doc_id2 in D2:
6 Dist[doc_id2] := 0
7 List dw2 := List of (word_id, weight) from D2 for
doc_id2
8 for (word_id1, weight1) in dp1:
9 for (word_id2, weight2) in dp2:
10 Dist[doc_id2] += weight1*weight2
Этот алгоритм легко реализовать на языке SQL в любой реляционной СУБД. Код на языке SQL для нахождения ближайших соседей для одного документа выглядит следующим образом:
SELECT i1.doc_id AS doc_id1,
i2.doc_id AS doc_id2,
SUM(i1.weight*i2.weight) AS cos
FROM doc_word_index i1, doc_word_index i2
WHERE i1.word_id=i2.word_id
AND i1.doc_id=:INPUT_DOC_ID
GROUP BY i1.doc_id, i2.doc_id
ORDER BY cos DESC
Возможна более эффективная по сравнению с СУБД реализация данного алгоритма: во-первых, индекс «документ–слово–вес» можно хранить в сжатом виде, с учетом избыточности повторения doc_id в соседних строках таблицы [6, 12]; во-вторых, при обработке сортированных списков (word_id, weight) для пар документов, необходимо использовать алгоритм слияния сортированных списков [12].
Асимптотическая сложность алгоритма – O (|D|2 Avg_dl ), где |D| – количество документов в коллекции, Avg_dl – среднее количество слов в документе.
Алгоритм применяет прямой просмотр таблицы «документ–слово–вес» и поэтому может быть реализован без использования индексов, хранящихся в памяти (не требуются накладные расходы на операции seek). Поэтому минимальный требуемый объем оперативной памяти – O(max(Avg_dl)) – не зависит от размера коллекции. В то же время кэширование индексов в памяти, естественно, повышает скорость работы алгоритма.
Основными достоинствами данного алгоритма являются:
1) простота реализации;
2) возможность работы с большими индексами документов, которые не помещаются в оперативную память (используется линейный проход по индексу документов);
3) легкость распараллеливания вычислений (можно производить вычисления ближайших соседей независимо для разных документов).
Основной недостаток такого алгоритма - низкая скорость работы.
3.4. Алгоритм расчета с использованием поиска по инвертированному индексу. Более эффективный алгоритм вычисления ближайших соседей можно реализовать при помощи инвертированного индекса документов – отсортированного и сжатого списка троек (word_id, doc_id, weight). Инвертированные списки известны как наиболее эффективная структура данных для выполнения поиска документов по запросу [12].
Первым этапом работы алгоритма является построение инвертированного индекса для коллекции D2. Затем для каждого документа из коллекции D1 производится поиск ближайших документов по коллекции D2. Для этого применяется алгоритм, аналогичный поиску документов по запросу пользователя [6], и в качестве запроса используется полный текст документа. В отличие от обычного поиска документов по запросу для данного алгоритма:
• используются очень длинные запросы, порядка нескольких сотен слов (это характерное количество уникальных слов в документе);
• необходим поиск документов с учетом неточного совпадения (не все слова запроса встречаются в документе);
• элементам запроса присваивается вес, соответствующий нормализованному TF*IDF весу слова в документе.
Данный алгоритм применяется, например, в системе кластеризации новостей Яндекс [13, 14]. К сожалению, указанные публикации не позволяют оценить скорость этого данного алгоритма.
Алгоритм допускает эффективное распараллеливание поиска двумя способами:
- распараллеливание по документам коллекции D2;
- поиск по нескольким индексам (распараллеливание по документам коллекции D1).
3.5. Алгоритм расчета с использованием двух инвертированных индексов и MapReduce. В статье [5] описан метод вычисления полной матрицы близости документов, в котором применяется инвертированный индекс документов и метод распараллеливания MapReduce [15] в варианте Hadoop [16].
В [5] решается задача расчета полной матрицы близости между всеми документами коллекции, однако данный алгоритм легко адаптировать для рассматриваемого несимметричного случая поиска ближайших соседей.
Алгоритм [5] состоит из следующих этапов:
1) построение инвертированного индекса с нормализованными весами слов;
2) усечение индекса выкидыванием наиболее часто встречающихся слов;
3) для всех слов коллекции:
3.1) для всех пар документов (word_id, doc_id1, weight1) и (word_id, doc_id2, weight2) выдать тройку (doc_id1, doc_id2, weight1*weight2) - операция MAP,
3.2) отсортировать тройки (doc_id1, doc_id2, w) по полям (doc_id1, doc_id2),
3.3) вычислить сумму w для каждой пары (doc_id1, doc_id2) – операция REDUCE; в результате получаем искомый результат – список троек (doc_id1, doc_id2, distance)
Алгоритм реализован на языке Java, операции по распараллеливанию вычислений и распределенная сортировка данных и суммирование на шагах 3.2–3.3 выполняются средой выполнения MapReduce–программ Hadoop. Среда выполнения также берет на себя управление памятью.
Отметим, что распределенная сортировка данных и суммирование на шагах 3.2–3.3 требуют интенсивной коммуникации между узлами сети: даже при распараллеливании на два компьютера потребуется передать по сети как минимум половину полной матрицы близости между документами, т. е. O(|D|2)троек (doc_id1, doc_id2, w).
Существенным шагом, позволяющим радикально упростить задачу и ускорить вычисление, является усечение индекса на шаге 2. Авторы [5] использовали стратегию усечения 1% наиболее часто встречающихся слов. Для коллекции 906 000 новостей, применяемых для тестирования, это составляет 9093 слова. Усечение словаря дало возможность сократить количество пар весов, вычисляемых на шаге 4 с 8 · 1012nдо 4 · 109 – в 2000 раз. Соответственно возрастает и скорость работы алгоритма.
В [5] приведены следующие данные о скорости работы алгоритма:
• коллекция документов – новостные сообщения AQUAINT42 на английском языке [17], 906 000 документов общим объемом 2.5 Гб (т. е. около 3 Кб на документ);
• количество различных слов в коллекции (без усечения слов) – 909 326;
• использование кластера из 20 компьютеров, 2.4GHz CPU, 4GB RAM;
• время вычисления матрицы близости для усеченного индекса составило 2 ч, из них 3.5 мин – на построение инвертированного индекса;
• таким образом, общее время работы для усеченного индекса – 2 · 20 = 40 часов машинного времени.
Авторы статьи [5] не произвели оценку влияния усечения индекса на качество результата. В то же время «честный» расчет похожих документов таким способом вряд ли возможен, так как при увеличении количества троек (doc_id1, doc_id2, w) в 2000 раз время работы алгоритма выросло бы пропорционально и стало бы неприемлемо большим.
4. Алгоритм расчета с использованием инвертированного индекса. Предлагаемый нами алгоритм, подобно [14, 5] использует инвертированные индексы для коллекций документов, но при этом применяется более эффективная организация вычисления ближайших соседей одновременно для множества документов:
1) пусть |D1| = M, |D2| = N; в памяти создается матрица расстояний между M×N документами, изначально инициализированная нулями;
2) для слова word_id в память загружаются соответствующие фрагменты инвертированных списков из D1 и D2;
3) далее для каждой пары документов (d1, d2) из этих фрагментов произведение весов добавляется в матрицу расстояний;
4) затем для каждой строки матрицы расстояний вычисляется k элементов с наибольшим весом.
Этот алгоритм можно записать в виде псевдокода:
1 Input: inverted index D1, inverted index D2
2 Dist := Matrix[M*N]
3 for word_id in D1:
4 List dp1 := List of (doc_id, weight) from D1 for word_id
5 List dp2 := List of (doc_id, weight) from D2 for word_id
6 for (doc_id1, weight1) in dp1:
7 for (doc_id2, weight2) in dp2:
8 Dist[doc_id1][doc_id2] += weight1*weight2
Для больших коллекций расчет ближайших соседей необходимо производить, разбив матрицу M×N документов на полосы размером m×N так, чтобы в оперативную память помещалась матрица m×N и соответствующие фрагменты инвертированного индекса для каждого из слов коллекции.
Асимптотическая сложность данного алгоритма – O(|D|2· Avg_wi), где |D| – количество документов в коллекции, Avg_wi – среднее количество документов для одного слова. Асимптотическая сложность этого алгоритма равна общему количеству операций сложения и умножения элементов матриц весов документов, и совпадает с асимптотической сложностью метода, использующего прямой индекс «документ–слово–вес», однако практическая скорость самого алгоритма на несколько порядков выше за счет эффективного использования архитектуры современных процессоров:
• Основной объем вычислений приходится на обработку наиболее частотных слов на простых операциях умножения декартова произведения двух векторов (строки 6–8 алгоритма), что позволяет эффективно работать алгоритму предсказания переходов, реализованному в современных процессорах. В то же время алгоритм расчета по прямому индексу документов выполняет обработку наиболее частотных слов в рамках менее эффективной операции слияния сортированных списков.
• Обрабатываемые данные компактно располагаются в памяти, что дает возможность эффективно использовать кэш современных процессоров.
4.1. Распараллеливание по полосам. Алгоритм расчета с помощью инвертированного индекса легко поддается распараллеливанию на кластерной архитектуре. Наиболее вычислительно сложная часть алгоритма содержит независимые вычислительные блоки, связанные с расчетом ближайших соседей для отдельной полосы m×N документов, поэтому естественным способом распараллеливания является разделение по полосам.
Каждому узлу кластера выделяется задание, состоящее из:
• инвертированного индекса коллекции D2 по N документам;
• прямого индекса документов по коллекции D1;
• интервала документов из коллекции D1, для которых необходимо вычислить k ближайших соседей.
При выполнении задания интервал документов разбивается на полосы шириной не более m, затем для каждой полосы строится инвертированный индекс и производится вычисление соседей.
Общее время выполнения параллельного алгоритма состоит из:
1) времени построения инвертированного индекса документов (на одном компьютере);
2) времени копирования индексов на узлы кластера;
3) времени параллельного расчета ближайших соседей по полосам;
4) времени объединения результатов.
В п. 5 мы покажем, что на практике время выполнения последовательных операций (шаги 1, 2 и 4) для коллекции из 1.5 млн документов составляет 0.4% общего времени работы алгоритма, и, таким образом, на такой коллекции алгоритм допускает эффективное распараллеливание приблизительно до 100 компьютеров.
При увеличении размера коллекции время построения инвертированного индекса и размер индекса растут как O(|D| log |D|) от количества документов, а время расчета ближайших соседей – как O(|D|2· Avg_wi), поэтому процент времени, затрачиваемый на последовательные операции, будет снижаться обратно пропорционально размеру коллекции и соответственно будет улучшаться масштабируемость алгоритма.
Отметим, что этап построения инвертированного индекса допускает эффективное распараллеливание. Алгоритм параллельного построения инвертированного индекса на основе технологии Hadoop MapReduce описан в [5].
4.2. Оценка максимального размера полосы. Оценим максимальный размер полосы m, доступный для вычисления на компьютере, имеющем H Гб оперативной памяти. Предположим, что для матрицы расстояний можно выделить h = 0.8H Гб (остальная память используется для фрагментов индекса и среды исполнения программы).
Пусть ячейка матрицы (накопитель расстояния) имеет размер 4 байта (float).
Тогда
Размер
инвертированного индекса
зависит от суммарного объема документов коллекции. Использование
алгоритмов сжатия инвертированного индекса [12] позволяет добиться
сжатия индекса до 10–40% от исходного размера текстовых
файлов.
Предположим, размер индекса составляет 1 кб на документ. Общий объем
данных, которые необходимо прочитать из индекса, равен размеру индекса,
умноженному на количество полос (в предположении, что индекс не
помещается в память, и его необходимо читать
при каждом проходе).
Пусть h = 1.6 Гб. Оценка размера полосы m (по формуле (4)) и размера инвертированного индекса для коллекций различного размера приведена в табл. 1.
при каждом проходе).
Пусть h = 1.6 Гб. Оценка размера полосы m (по формуле (4)) и размера инвертированного индекса для коллекций различного размера приведена в табл. 1.
Таким
образом, для коллекций размера
до 1 000 000 документов, с одной стороны, размер полосы m достаточно
велик, что позволяет за один проход по индексу решать задачу для
большого количества документов, а с другой – размер индекса
достаточно мал (весь или почти весь индекс можно поместить в
оперативной памяти), и общий объем чтения индекса является приемлемым.
Для коллекций размером 10 000 000 документов и более квадратичный характер асимптотической сложности алгоритма делает задачу трудно решаемой на обычных компьютерах. Данный метод плохо применим из-за огромного объема данных, которые необходимо прочитать при большом количестве итераций.
В предельном случае очень большой коллекции в оперативную память помещается лишь полоса документов ширины 1 (матрица 1 × N), и в этом случае алгоритм эквивалентен алгоритму расчета с использованием поиска по инвертированному индексу.
5. Экспериментальная оценка эффективности алгоритмов расчета ближайших соседей. Были реализованы следующие алгоритмы поиска похожих документов:
1) базовый алгоритм на основе SQL, с использованием СУБД Oracle 9i∗);
2) алгоритм расчета с использованием инвертированного индекса, с применением распараллеливания по полосам (будем называть его INVMUL);
3) метод усечения инвертированного списка документов, описанный в [5].
Для тестирования скорости работы алгоритма применялась коллекция документов РОМИП BY.WEB [18], представляющая собой 1.5 млн документов, собранных с русскоязычных сайтов белорусского Интернета (домены *.by), и подмножества данной коллекции (выбранные в порядке следования документов в дистрибутиве коллекции) BY.WEB_10k и BY.WEB_100k, состоящие из 10 000 и 100 000 документов соответственно.
Для коллекций размером 10 000 000 документов и более квадратичный характер асимптотической сложности алгоритма делает задачу трудно решаемой на обычных компьютерах. Данный метод плохо применим из-за огромного объема данных, которые необходимо прочитать при большом количестве итераций.
В предельном случае очень большой коллекции в оперативную память помещается лишь полоса документов ширины 1 (матрица 1 × N), и в этом случае алгоритм эквивалентен алгоритму расчета с использованием поиска по инвертированному индексу.
5. Экспериментальная оценка эффективности алгоритмов расчета ближайших соседей. Были реализованы следующие алгоритмы поиска похожих документов:
1) базовый алгоритм на основе SQL, с использованием СУБД Oracle 9i∗);
2) алгоритм расчета с использованием инвертированного индекса, с применением распараллеливания по полосам (будем называть его INVMUL);
3) метод усечения инвертированного списка документов, описанный в [5].
Для тестирования скорости работы алгоритма применялась коллекция документов РОМИП BY.WEB [18], представляющая собой 1.5 млн документов, собранных с русскоязычных сайтов белорусского Интернета (домены *.by), и подмножества данной коллекции (выбранные в порядке следования документов в дистрибутиве коллекции) BY.WEB_10k и BY.WEB_100k, состоящие из 10 000 и 100 000 документов соответственно.
В
табл. 2 собраны характеристики
используемой нами коллекции по сравнению с коллекцией AQUAINT42,
тестированной в статье [5]. Для коллекции BY.WEB приведены размеры
текстовых файлов, полученных из исходных HTML очисткой тегов и другой
неотображаемой информации. Из таблицы видно, что количество документов
коллекции BY.WEB в 1.7 раз больше, чем в коллекции AQUAINT42, и
документы BY.WEB больше, чем документы AQUAINT42. Учитывая
асимптотическую зависимость времени вычисления ближайших соседей O(|D|2·
Avg_wi),
можно оценить сравнительную сложность поиска похожих документов по
коллекции BY.WEB как примерно в 3 раза большую, чем AQUAINT42.
Для вычислений использовали четыре компьютера 3 GHz CPU, 2 Gb RAM. Для каждого документа производилось вычисление 100 наиболее близких документов. Время работы различных алгоритмов представлено в табл. 3.
В столбце «Послед. операции, %» приводится оценка доли времени, затраченного на операции, выполняемые в последовательном режиме для алгоритма распараллеливания по полосам. Время последовательных операций состоит из фактического времени построения инвертированного индекса плюс оценки времени на копирование индекса на разные компьютеры в предположении, что скорость копирования по сети составляет 2 Мб/с.
Для вычислений использовали четыре компьютера 3 GHz CPU, 2 Gb RAM. Для каждого документа производилось вычисление 100 наиболее близких документов. Время работы различных алгоритмов представлено в табл. 3.
В столбце «Послед. операции, %» приводится оценка доли времени, затраченного на операции, выполняемые в последовательном режиме для алгоритма распараллеливания по полосам. Время последовательных операций состоит из фактического времени построения инвертированного индекса плюс оценки времени на копирование индекса на разные компьютеры в предположении, что скорость копирования по сети составляет 2 Мб/с.
Можно
сопоставить скорость работы
предложенного нами алгоритма INVMUL с использованием стратегии
отсечения 1% наиболее частых слов и алгоритма [5], основанного на
перемножении инвертированных индексов с помощью Hadoop MapReduce.
Получим 10 компьютеро-часов для INVMUL на BY.WEB против 40
компьютеро-часов Hadoop MapReduce на AQUAINT42. Учитывая сравнительную
оценку сложности коллекции AQUAINT42 как приблизительно в 3 раза
меньшую, чем BY.WEB, можно сделать вывод, что разработанный нами
алгоритм примерно в 12 раз эффективнее алгоритма [5].
При сопоставлении скорости работы алгоритма INVMUL с простым решением на основе SQL видно, что она примерно в 37 раз выше даже на очень маленькой коллекции документов. Попытки применить SQL для коллекций большего размера показали,что соотношение эффективности возрастает при увеличении размера коллекции. Для коллекций из нескольких сот тысяч документов SQL не применим.
5.1. Оценка влияния усечения индекса на результаты поиска похожих документов. Стратегия усечения наиболее часто используемых слов из индекса, предложенная в статье [5], весьма сомнительна, с точки зрения влияния на качество получаемого результата. Рассмотрим результаты отсечения на коллекции BY.WEB.
Отсечение 1% наиболее частотных слов составляет 33 000 слов, в которые попадает большинство общезначимых слов языка. В индексе остаются лишь слова, имеющие частотность не более 550 документов из 1.5 млн, т. е. встречающиеся реже, чем в 0.04% документов. Поиск близких документов по таким признакам не имеет практического смысла. Даже при использовании отсечения по порогу 0.1%, получаем отсечение 3300 наиболее частотных слов. В индексе остаются лишь слова, имеющие частотность не более 13 329 документов, встречающиеся реже, чем в 1% документов. Отсекаются, например, такие тематически значимые слова как МИНСК, БЕЛАРУСЬ, РОССИЯ,
МОСКВА, РУБЛЬ, ТЕЛЕФОН, ПРАВИТЕЛЬСТВО, ИНТЕРНЕТ/СПРАВОЧНИК, ФЕН, ПЛЯЖ, ЗОЛОТО, КОНТРАКТ, ПОЕЗД, АВТОШКОЛА, ТРЕНЕР, СЫРЬЕ и др.
Поэтому, по нашему мнению, данная стратегия не применима для использования результатов поиска похожих документов на практике.
6. Заключение. Были рассмотрены различные алгоритмы для вычисления матрицы наиболее близких соседей в больших коллекциях документов, при использовании стандартного векторного представления документов с TF*IDF4весами слов, и получены следующие основные результаты:
1) предложен алгоритм полного попарного расчета матрицы ближайших соседей, применимый на практике для коллекций размером порядка 1 млн документов;
2) реализованный алгоритм опробован на коллекции BY.WEB, состоящей из 1.5 млн документов, время работы составило 7 суток на четырех обычных компьютерах, что примерно в 12 раз эффективнее, чем алгоритм Hadoop4MapReduce [5].
Несмотря на достигнутый прогресс, практически важная задача расчета матрицы близости для коллекций существенно большего размера – от 10–100 млн. документов и более – требует разработки новых методов решения.
При сопоставлении скорости работы алгоритма INVMUL с простым решением на основе SQL видно, что она примерно в 37 раз выше даже на очень маленькой коллекции документов. Попытки применить SQL для коллекций большего размера показали,что соотношение эффективности возрастает при увеличении размера коллекции. Для коллекций из нескольких сот тысяч документов SQL не применим.
5.1. Оценка влияния усечения индекса на результаты поиска похожих документов. Стратегия усечения наиболее часто используемых слов из индекса, предложенная в статье [5], весьма сомнительна, с точки зрения влияния на качество получаемого результата. Рассмотрим результаты отсечения на коллекции BY.WEB.
Отсечение 1% наиболее частотных слов составляет 33 000 слов, в которые попадает большинство общезначимых слов языка. В индексе остаются лишь слова, имеющие частотность не более 550 документов из 1.5 млн, т. е. встречающиеся реже, чем в 0.04% документов. Поиск близких документов по таким признакам не имеет практического смысла. Даже при использовании отсечения по порогу 0.1%, получаем отсечение 3300 наиболее частотных слов. В индексе остаются лишь слова, имеющие частотность не более 13 329 документов, встречающиеся реже, чем в 1% документов. Отсекаются, например, такие тематически значимые слова как МИНСК, БЕЛАРУСЬ, РОССИЯ,
МОСКВА, РУБЛЬ, ТЕЛЕФОН, ПРАВИТЕЛЬСТВО, ИНТЕРНЕТ/СПРАВОЧНИК, ФЕН, ПЛЯЖ, ЗОЛОТО, КОНТРАКТ, ПОЕЗД, АВТОШКОЛА, ТРЕНЕР, СЫРЬЕ и др.
Поэтому, по нашему мнению, данная стратегия не применима для использования результатов поиска похожих документов на практике.
6. Заключение. Были рассмотрены различные алгоритмы для вычисления матрицы наиболее близких соседей в больших коллекциях документов, при использовании стандартного векторного представления документов с TF*IDF4весами слов, и получены следующие основные результаты:
1) предложен алгоритм полного попарного расчета матрицы ближайших соседей, применимый на практике для коллекций размером порядка 1 млн документов;
2) реализованный алгоритм опробован на коллекции BY.WEB, состоящей из 1.5 млн документов, время работы составило 7 суток на четырех обычных компьютерах, что примерно в 12 раз эффективнее, чем алгоритм Hadoop4MapReduce [5].
Несмотря на достигнутый прогресс, практически важная задача расчета матрицы близости для коллекций существенно большего размера – от 10–100 млн. документов и более – требует разработки новых методов решения.
1. Joachims T. Text Categorization with Support Vector Machines: Learning with Many Relevant Features // Proc. of ECML-98. 10th European Conference on Machine Learning. 1998. URL: http://www.cs.cornell.edu/people/tj/publications/joachims98a.ps.gz.
2. Yang Y., Liu X. A re-examination of text categorization methods // Proc. of SIGIR-99. 22nd ACM Intern. Conference on Research and Development in Information Retrieval. / eds: M. A. Hearst, F. Gey, R. Tong. New York, Berkeley: ACM Press, 1999. P. 42–49.
3. Агеев М. С., Добров Б. В., Лукашевич Н. В. Автоматическая рубрикация текстов: методы и проблемы. // Учен. зап. Казанск. гос. ун-та. Сер. Физико-математические науки. 2008. Т. 150, кн. 4. С. 25–40.
4. Агеев М. С., Добров Б. В., Лукашевич Н. В. и др. Классификация запросов и оптимизация факторов для поиска нормативных документов // Рос. семинар по оценке методов информационного поиска: Труды РОМИП’2009: cеминар в рамках Всерос. науч. конференции RCDL’2009. 16 сентября 2009 г. Петрозаводск; Санкт-Петербург: НУ ЦСИ, 2009. С. 151–162.
5. Elsayed T., Lin J., Oard D. W. Pairwise document similarity in large collections with Map-Reduce. // Proc. of the 46th Annual Meeting of the Association for Computational Linguistics on Human Language Technologies: Short papers (Columbus, Ohio, June 16–17, 2008). Human Language Technology Conference. Association for Computational Linguistics. Morristown. New Jark, 2008. P. 265–268.
6. Manning C. D., Raghavan P., Schutze H. Introduction to Information Retrieval. Cambridge, 2008. URL: http://nlp.stanford.edu/IR-book/information-retrieval-book.html.
7. Агеев М. С., Добров Б. В., Лукашевич Н. В., Сидоров А. В. Экспериментальные алгоритмы поиска/классификации и сравнение с Sbasic lineU // Рос. семинар по оценке методов информационного поиска: Труды второго рос. семинара РОМИП’2004 (Пущино, 01.10.2004). СПб: Науч.-исслед. ин-т химии С.-Петерб. ун-та, 2004. С. 62–89.
8. Зеленков Ю., Сегалович И. Сравнительный анализ методов определения нечетких дубликатов для Web-документов // Девятая Всерос. науч. конференция RCDL’2007 SЭлектронные библиотеки: Перспективные Методы и Технологии, Электронные коллекцииU. Переславль-Залесский, 2007. URL: http://rcdl.ru/doc/2007/paper6 5v1.pdf.
9. Ilyinsky S., Kuzmin M., Melkov A., Segalovich I. An efficient method to detect duplicates of Web documents with the use of inverted index // WWW-2002 – Eleventh Intern. World Wide Web Conference. URL: http://www2002.org/CDROM/poster/187/.
10. Butakov S., Scherbinin V. The toolbox for local and global plagiarism detection // Comput. Educ. 2009. Vol. 52, N 4. P. 781–788. URL: http://dx.doi.org/10.1016/j.compedu.2008.12.001.
11. Lifshits Y. Algorithms for Nearest Neighbor Search // Tutorial at RuSSIR’07. Ekaterinburg, September 2007. URL: http://simsearch.yury.name/tutorial.html.
12. Zobel J., Moffat A. Inverted files for text search engines // ACM Comput. Surv. 2006. Vol. 38 N 2 URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.105.8844rep=rep1type=pdf.
13. Сегалович И., Маслов М. Яндекс на РОМИП-2004. Некоторые аспекты полнотекстового поиска и ранжирования в Яндекс // Рос. семинар по оценке методов информационного поиска: Труды второго рос. семинара РОМИП’2004 (Пущино, 01.10.2004). СПб: Науч.-исслед. ин-т химии С.-Петерб. ун-та.
2004. С. 100–109.
14. Как работают новые Яндекс. Новости // Яндекс. 2003. URL: http://company.yandex.ru/public/ articles/smi-mirror.xml.
15. Dean J., Ghemawat S. MapReduce: simplified data processing on large clusters // Proc. of the 6th conference on Symposium on Opearting Systems Design & Implementation. San Francisco, CA. December 06–08, 2004. P. 10-10.
16. Apache Hadoop. URL: http://hadoop.apache.org/. 17. AQUAINT-2 Information-Retrieval Text Research Collection. URL: http://www.ldc.upenn.edu/ Catalog/CatalogEntry.jsp?catalogId=LDC2008T25.
18. Веб коллекция BY.web. 2007. URL: http://romip.ru/ru/collections/by.web-2007.html.
Статья рекомендована к печати проф. В. Ю. Добрыниным.
Статья принята к печати 10 марта 2011 г.