Setting lower bounds on Jensen–Shannon divergence and its application to nearest neighbor document search

Дивергенция Дженсена–Шеннона используется для определения ближайших соседей в коллекции документов для конкретного документа запроса. Это эффективный механизм, однако исчерпывающий поиск может оказаться трудоемким процессом. В этой статье покажем, определив нижнюю оценку дивергенции Дженсена–Шeннона, что возможно сократить объем вычислений на 60% для исчерпывающего поиска и на 98% для приближенного поиска на основе выполнения поиска ближайшего соседа в одной реальной коллекции документов. В этих экспериментах был применен корпус документов, который содержит 1 854 654 статьи, опубликованные в New York Times с 01.01.1987 по 19.06.2007 (The New York Times Annotated Corpus). В качестве запросов были выбраны 100 случайных документов из данного корпуса документов. Оценивается влияние на производительность на основе сокращения количества вызовов логарифмической функции. Приближенный поиск ближайшего соседа основан на кластеризации документов с помощью алгоритма контекстной кластеризации. Выполняется приближенный поиск ближайшего соседа путем нахождения некоторого набора аттракторов кластеров, которые наиболее близки запросу, и далее ограничивается поиск документов в кластерах, соответствующих выбранным аттракторам.