Кластеризация новостей

Question

Как Google News и Techmeme объединяют похожие новости? Есть ли какой-нибудь хорошо известный алгоритм, который используется для достижения этой цели?

Ценю вашу помощь.

Спасибо заранее.

Answer 1

Одним из довольно распространенных способов кластеризации текста на основе содержимого является использование Принципа анализа компонентов для векторов слов (вектор из n измерений, где каждое возможное слово представляет одно измерение и величину в каждом направлении, каждый вектор - это число вхождений слова в этой конкретной статье), за которым следует простая кластеризация, например K-Means.

Answer 2

Алгоритмическая основа - агломерационная кластеризация или что-то подобное. Но есть множество эвристик на вершине этого. Например, векторное пространство обязательно состоит из слов и фраз (n-граммы слова). Ограничение поиска в строгий период времени также очень важно. И определение имен, и взвешивание заголовка и заголовков абзаца также являются ключевыми частями.

На тангенциально связанной ноте. Если вы заинтересованы в нахождении почти дублированных статей, существует ряд более простых для реализации подходов, например, описанный здесь

Answer 3

Есть несколько разных способов сделать это. Стандарт состоит в том, чтобы выполнить анализ «мешка слов» (взвешенный TF-IDF), а затем выполнить косинусное сходство и k-средних.

У меня был успех с этой бумагой: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=4289851

Самое замечательное в этом: 1) Это пошаговое, что отлично подходит для новостей. При использовании стандартных k-средних вам нужен весь набор данных. С новостями у вас обычно появляются статьи, поступающие со временем. Инкрементные алгоритмы решают это. 2) Это основано на фразе. Так что он опирается на фразы, а не просто слова.

В последнее время появились методики, в которых вместо слов используется семантическое значение (например, путем извлечения концепций Википедии или DBPedia из каждой статьи и использования этого вместо просто слов).