Сомнения в методах кластеризации для твитов

Question

Я довольно новичок в кластеризации и смежных вопросах, поэтому, пожалуйста, простите мои вопросы.

Я пытаюсь войти в эту область, выполнив некоторые тесты, и в качестве первого эксперимента я хотел бы создать кластеры на твитах на основе сходства контента. Основная идея эксперимента заключалась в хранении твитов в базе данных и периодическом вычислении кластеризации (т. Е. С использованием задания cron). Обратите внимание: база данных будет получать новые твиты время от времени.

Будучи невежественны в этой области, моя идея (возможно, наивный) было бы сделать что-то вроде этого:

1. For each new tweet in the db, extract N-grams (N=3 for example) into a set 
2. Perform Jaccard similarity and compare with each of the existing clusters. If result > threshold then it would be assigned to that cluster 
3. Once finished I'd get M clusters containing similar tweets 

Теперь я вижу некоторые проблемы с этим основным подходом. Давайте отложим вычислительную стоимость, как бы было сделано сравнение между твитом и кластером? Предполагая, что у меня есть твит Tn и кластер C1, содержащий T1, T4, T10, с которым я должен сравнивать его? Учитывая, что мы говорим о сходстве, вполне возможно, что порог sim (Tn, T1)>, но sim (Tn, T4) <. Чувство моего чувства говорит мне, что для кластера нужно использовать что-то вроде среднего, чтобы избежать этой проблемы.

Также может случиться, что sim (Tn, C1) и sim (Tn, C2) являются как пороговыми, а сходство с C1 будет выше. В этом случае Tn следует перейти к C1. Это может быть сделано грубой силой, а также назначить твит для кластера с максимальным сходством.

И, наконец, это вычислительная проблема. Я немного читал о minhash, и, похоже, это ответ на эту проблему, хотя мне нужно сделать еще несколько исследований.

В любом случае, мой главный вопрос: мог ли кто-нибудь с опытом работы в этом районе рекомендовать мне, к какому подходу я должен стремиться? Я прочитал некоторые упоминания об LSA и других методах, но попытка справиться со всем становится немного подавляющей, поэтому я буду признателен за руководство.

Из того, что я читаю, инструмент для этого будет иерархической кластеризацией, поскольку это позволит перегруппировать кластеры всякий раз, когда появятся новые данные. Это верно?

Обратите внимание, что я не ищу сложный случай. Моя идея использования будет иметь возможность группировать подобные твиты в группы без какой-либо предыдущей информации. Например, твиты из Foursquare («Я проверяю ...», которые похожи друг на друга, были бы одним случаем, или «Мой рейтинг klout ...»). Также обратите внимание, что я хотел бы, чтобы это было независимым от языка, поэтому я не заинтересован в том, чтобы иметь дело с конкретными языковыми проблемами.

Answer 1

Похоже, что вы пытаетесь решить две разные проблемы в одной, то есть в синтаксической и семантической кластеризации. Это совершенно разные проблемы, особенно если вы находитесь в сфере краткосрочного анализа (и, конечно, Twitter - король короткого текста).

«Синтаксическая» кластеризация означает объединение твитов, которые, скорее всего, происходят из одного источника. Ваш пример Foursquare идеально подходит, но он также распространен для ретвитов, людей, которые используют онлайн-статьи в газетах или сообщения в блогах, и многие другие случаи. Для этого типа проблемы использование N-граммовой модели почти обязательно, как вы сказали (мой опыт показывает, что N = 2 хорош для твитов, так как вы можете найти значительные твиты, которые имеют как минимум 3-4 функции). Нормализация также является важным фактором здесь, устранение тега RT, упоминания, хэштеги могут помочь.

«Семантическая» кластеризация означает объединение твитов, разделяющих одну и ту же тему. Это гораздо более сложная проблема, и она вряд ли будет работать, если вы попытаетесь объединить произвольную выборку твитов из-за того, что они, как правило, несут слишком мало информации. Однако эти методы могут работать, если вы ограничите свой домен определенным подмножеством твитов (т. Е. Сопоставлением ключевого слова или хэштегом). LSA может быть полезен здесь, в то время как это бесполезно для синтаксических кластеров.

Основываясь на вашем наблюдении, я думаю, что вы хотите использовать синтаксическую кластеризацию. Ваша самая большая проблема, однако, заключается в том, что вам нужна сетевая кластеризация, а не статическая кластеризация. Классические алгоритмы кластеризации, которые будут хорошо работать в статическом случае (например, иерархическая кластеризация или объединение), не подходят для онлайн-кластеризации, если только вы не повторяете кластеризацию с нуля каждый раз, когда новый твит будет добавлен в вашу базу данных. «Усреднение» кластеров для добавления новых элементов не является отличным решением в соответствии с моим опытом, потому что вам нужно сохранить всю информацию каждого члена кластера, чтобы обновлять «среднее» каждый раз, когда попадают новые данные. Кроме того, алгоритмы, такие как иерархические кластеризация и объединение находят работу хорошо, потому что они могут присоединиться к существующим кластерам, если между ними обнаружена связь сходства, и они не просто назначают новый элемент «ближайшему» кластеру, что вы предложили сделать в своем после.

Алгоритмы, подобные MinHash (или SimHash), действительно больше подходят для онлайн-кластеризации, поскольку они поддерживают идею «запроса» для похожих документов. MinHash - это, по сути, способ получить пары документов, которые превышают определенный порог сходства (в частности, MinHash можно считать оценкой сходства с Jaccard), не полагаясь на квадратичный алгоритм, как попарное сравнение (это, по сути, O(nlog(n)) во время). Это, однако, квадратично в пространстве, поэтому реализация MinHash только для памяти полезна только для небольших коллекций (скажем, 10000 твитов). В вашем случае, однако, может быть полезно сохранить «эскизы» (т. Е. Набор хэшей, которые вы получаете путем мини-хэширования твита) ваших твитов в базе данных, чтобы сформировать «индекс», и запросить новые против этот индекс. Затем вы можете сформировать граф подобия, добавив ребра между вершинами (твитами), которые соответствовали запросу подобия. Связанными компонентами вашего графика будут ваши кластеры.

Answer 2

Это очень напоминает canopy pre-clustering для меня.

По существу, каждый кластер представлен первым объектом, который запустил кластер. Объекты в пределахвнешний радиус присоединиться к кластеру. Объекты, которые не являются в пределахвнутренний радиус по меньшей мере одного кластера запускает новый кластер. Таким образом, вы получаете перекрывающееся (непересекающееся!) Квантование вашего набора данных. Поскольку это может значительно уменьшить размер данных, его можно использовать для ускорения различных алгоритмов.

Однако не ожидал полезных результатов от кластеризации твитов. Tweet данные - это просто шум. Большинство твитов имеют всего несколько слов, слишком мало, чтобы определить хорошее сходство.С другой стороны, у вас есть различные ретвиты, близкие к дубликатам, но тривиальные для обнаружения.

So что было бы хорошим набором твитов? Может ли это подобное n-граммовое сходство захватить это?