Visualizing Top Tweeps with t-SNE, in Javascript

Недавно я изучал различные способы вложения немаркированных многомерных данных в двумерное пространство для визуализации. Для этой задачи было предложено множество методов. Этот обзорный доклад 2009 года содержит хорошие ссылки на многие из них (PCA, Kernel PCA, Isomap, LLE, автоэнкодеры и др.). Если у вас есть Matlab, в Dimensionality Reduction Toolbox реализовано множество этих методов. В Scikit Learn также есть краткий раздел по обучению на многообразиях с соответствующей реализацией.

Среди этих алгоритмов t-SNE выделяется приятной, интуитивной формулировкой, простым градиентом и хорошими свойствами. Вот видео Google Tech Talks, где Laurens van der Maaten (автор метода) объясняет его суть. Я решил реализовать t-SNE с нуля, потому что это лучший известный мне способ чему-то научиться, — и на каком же языке это делать, как не на Javascript! :)

Короче говоря, я реализовал t-SNE на JS, выложил библиотеку как tsnejs на Github и создал небольшую демонстрацию, которая использует эту библиотеку для визуализации топовых аккаунтов Twitter по тематике их твитов. В этом посте я решил, что будет интересно задокументировать такой маленький однодневный проект от начала до конца. Заодно это даёт мне возможность описать некоторые инструменты из моего арсенала, которые могут пригодиться другим.

Финальная демонстрация

Для начала взгляните на готовую демонстрацию. Для её создания я нашёл 500 самых популярных аккаунтов в Twitter, скачал по 200 их твитов и затем измерил различия в тематике их публикаций. Эти различия затем были переданы в t-SNE для построения двумерной визуализации, где близко расположенные люди пишут о похожих вещах. Забавно!

Получение списка топовых твиттерян

Сначала нам нужно определить 500 самых популярных твиттерян. Я загуглил «top twitter accounts» и нашёл http://twitaholic.com/, где они перечислены. Однако аккаунты встроены в веб-страницу, и нам нужно извлечь их в структурированном формате. Для этого я обожаю недавний стартап из YC — Kimono; я постоянно использую его для извлечения структурированных данных с сайтов. Он позволяет кликнуть по нужным элементам (в данном случае — Twitter-хэндлам) и извлечь их в JSON. Проще простого!

Сбор твитов

Теперь у нас есть список из 500 топовых твиттерян, и мы хотим получить их твиты, чтобы понять, о чём они пишут. Моя любимая библиотека для этой задачи — Tweepy. Документация у неё довольно ужасная, но если покопаться в исходном коде, всё оказывается относительно просто. Вот пример вызова для получения 200 твитов конкретного пользователя:

tweets = tweepy.Cursor(api.user_timeline, screen_name=user).items(200)

Мы итерируем это по всем пользователям, извлекаем текст твитов и сохраняем всё в файлы — по одному на аккаунт. В процессе мне пришлось справиться с двумя неприятностями:

Twitter накладывает жёсткие лимиты на частоту API-вызовов, поэтому сбор данных занял несколько часов, обёрнутый в блоки try-catch и вызовы time.sleep. Возвращаемый текст в Unicode, что создаёт проблемы при попытке записи в файл.

Одно из решений второй проблемы — использовать библиотеку codecs:

import codecs codecs.open(filename, 'w', 'utf-8').write(tweet_texts)

Ах да, давайте также скачаем и сохраним аватарки профилей Twitter — они пригодятся нам в визуализации. Пример для одного пользователя:

import urllib # да, я знаю, что это устарело userobj = api.get_user(screen_name = user) urllib.urlretrieve(imgname, userobj.profile_image_url) # сохраняем изображение на диск

Должен упомянуть, что я пишу много быстрого чернового кода на Python в IPython Notebooks, которые я горячо рекомендую. Если вы пишете весь свой Python в текстовых редакторах — вы серьёзно многое упускаете.

Количественная оценка различий между твиттерянами

Теперь у нас есть 500 твиттерян и их 200 последних твитов, объединённых в 500 файлов. Теперь мы хотим найти тех, кто пишет о похожих вещах. Scikit learn отлично подходит для быстрых NLP-задач вроде этой. В частности, мы загружаем все файлы и создаём массив из 500 элементов, где каждый элемент — 200 объединённых твитов. Затем мы используем класс TfidfVectorizer для извлечения всех слов и биграмм из текстовых данных и преобразования языка каждого пользователя в один tfidf-вектор. Этот вектор — своего рода отпечаток языка, который использует каждый человек. Вот как это можно просто настроить:

from sklearn.feature_extraction.text import CountVectorizer,TfidfVectorizer vectorizer = TfidfVectorizer(min_df=2, stop_words = 'english',\ strip_accents = 'unicode', lowercase=True, ngram_range=(1,2),\ norm='l2', smooth_idf=True, sublinear_tf=False, use_idf=True) X = vectorizer.fit_transform(user_language_array) D = -(X * X.T).todense() # Матрица расстояний: скалярное произведение tfidf-векторов

В коде выше user_language_array — это массив из 500 элементов с объединёнными твитами. Класс TfidfVectorizer просматривает все твиты и фиксирует все слова (униграммы) и словесные биграммы (то есть последовательности из двух слов). Он строит словарь из всех униграмм/биграмм и по сути подсчитывает, как часто каждый человек использует каждую из них. Вот пример преобразования текста твита в униграммы/биграммы:

Tfidf-векторы возвращаются сложенными в строки матрицы X размером 500 x 87 342. Каждое из 87 342 измерений соответствует некоторой униграмме или биграмме. Например, 10 000-е измерение может соответствовать частоте использования униграммы «YOLO». Векторы нормализованы по L2, поэтому скалярное произведение между ними связано с углом между любыми двумя векторами. Это можно интерпретировать как сходство языка. Наконец, мы сохраняем матрицу и имена пользователей в JSON-файл — и мы готовы загрузить всё в Javascript!

Визуализация

Теперь создаём .html-файл и подключаем jQuery (как всегда) и d3js, который я люблю использовать для любых графиков. Загружаем JSON с расстояниями и именами пользователей через jQuery, а с помощью d3js инициализируем SVG-элемент, который будет содержать всех пользователей. Для начала мы размещаем пользователей в случайных позициях, но вскоре расположим их так, чтобы похожие пользователи оказались рядом — с помощью t-SNE. Изучите код на странице демо, чтобы увидеть части с jQuery и d3js (Ctrl+U). В коде мы видим несколько вещей, которые я люблю использовать:

Мне нравится использовать Google Fonts для получения шрифтов красивее стандартных. Здесь, например, я подключаю Roboto и затем использую его в CSS. Далее мы видим подключение кода syntaxhighlighter, который динамически подсвечивает код на странице. Затем идёт JS-код отслеживания Google, который позволяет мне отслеживать статистику сайта в Google Analytics. На этом сайте я не использовал Bootstrap, потому что он очень маленький и простой, но обычно использую — это сразу делает сайт нормально работающим на мобильных устройствах.

t-SNE

Наконец добираемся до сути! Нам нужно расположить пользователей на нашем графике d3js так, чтобы похожие пользователи оказались рядом. Функция стоимости t-SNE была описана в статье 2008 года van der Maaten и Hinton. Как и во многих других методах, мы задаём две метрики расстояния — в исходном и во вложенном пространствах — и минимизируем их различие. В t-SNE, в частности, расстояние в исходном пространстве основано на распределении Гаусса, а во вложенном — на тяжелохвостом распределении Стьюдента. Формулировка через KL-дивергенцию обладает приятным свойством асимметричности в штрафовании расстояний между двумя пространствами:

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

Таким образом, алгоритм в первую очередь заботится о сохранении локальной структуры многомерных данных. К удобству, авторы размещают ссылки на множество реализаций t-SNE на своём сайте, что позволяет нам также посмотреть код для справки (если вы похожи на меня, читать код бывает гораздо легче, чем текстовые описания). Мы готовы писать версию на Javascript!

Финальный код можно увидеть в файле tsne.js на Github. Обратите внимание, как мы оборачиваем весь JS-код в замыкание, чтобы не засорять глобальное пространство имён. Это очень распространённый приём в Javascript, который по сути используется для реализации классов. Обратите также внимание на большой объём скучного служебного кода в начале, потому что Javascript не совсем предназначен для математики :) Основная функция, где происходит вся магия, — это costGrad(), которая вычисляет функцию стоимости и градиент целевой функции. Корректность реализации этой функции проверяется численной проверкой градиента в debugGrad(). Как только аналитический градиент совпадает с численным — можно запускать! Мы настраиваем фрагмент Javascript для многократного вызова функции step() (вызов setInterval()) и отображаем решение по мере его вычисления.

Уф! Финальный результат, ещё раз: демонстрация t-SNE.

Надеюсь, некоторые из упомянутых ссылок оказались полезными. Если вы используете tsnejs для вложения своих данных — дайте мне знать!

Бонус: визуализация векторных представлений слов с помощью t-SNE

Я создал ещё одну демонстрацию — на этот раз для визуализации векторных представлений слов. Перейдите сюда, чтобы посмотреть её. Векторные представления слов обучены по методу, описанному в статье ACL 2012.

Целевая функция (без учителя) устроена так, что слова, которые взаимозаменяемы (то есть встречаются в очень похожем окружающем контексте), оказываются близки во вложении. Это хорошо видно в визуализации!