Data Mining *

кадр из фильма Миссия Невыполнима II

Эта история началась пару месяцев назад, в первый день рождения моего сына. На мой телефон пришло СМС-сообщение с поздравлением и пожеланиями от неизвестного номера. Думаю, если бы это был мой день рождения мне бы хватило наглости отправить в ответ, не совсем культурное, по моему мнению, «Спасибо, а Вы кто?». Однако день рождения не мой, а узнать кто передаёт поздравления было интересно.

Первый успех

Было решено попробовать следующий вариант:

• Добавить неизвестный номер в адресную книгу телефона;
• Зайти по очереди в приложения, привязанные к номеру (Viber, WhatsApp);
• Открыть новый чат с вновь созданным контактом и по фотографии определить отправителя.

Мне повезло и в моём случае в списке контактов Viber рядом с вновь созданным контактом появилась миниатюра фотографии, по которой я, не открывая её целиком, распознал отправителя и удовлетворенный проведенным «расследованием» написал смс с благодарностью за поздравления.

Сразу же за секундным промежутком эйфории от удачного поиска в голове появилась идея перебором по списку номеров мобильных операторов составить базу [номер_телефона => фото]. А еще через секунду идея пропустить эти фотографии через систему распознавания лиц и связать с другими открытыми данными, например, фотографиями из социальных сетей.

За сайтом «Российские общественные инициативы» я наблюдаю давно, примерно с 29 мая 2013 года. Как и другие наблюдатели, я замечал аномалии в ходе голосований за различные инициативы. Но это мало кого беспокоило, пока аномалии приводили по нашим оценкам к росту числа голосов. Видимо, никто не считал чем-то плохим, если очередная инициатива наберет 100 000 голосов раньше срока. Всё изменилось, когда аномалии стали замедлять голосование.



Это началось 24 ноября в 13:35 по московскому времени. Счетчик голосов за принятие инициативы 9376 уменьшился на 2. Потом еще на 1 и еще на 2. Вечером уменьшение значения счетчика стало происходить всё чаще и чаще. Кто-то заметил это и сообщил автору инициативы. С этого момента начался тщательный мониторинг хода голосования.

Я расскажу про некоторые странности голосования, которые мы (наблюдатели) заметили за последнюю неделю. Также я попытаюсь сделать предположения о причинах некоторых из них. Выводов довольно мало, т.к. не всегда есть возможность получить нужные данные о ходе голосования.

Два года назад многих удивила новость о том, что американская торговая сеть Target узнала о беременности девушки раньше, чем её отец. «Она ещё в школу ходит, а вы посылаете ей купоны на детскую одежду и памперсы?», — кричал тогда рассерженный отец. Ничего удивительного: простой дата-майнинг истории покупок с привязкой к дисконтной или банковской карте.

Оказывается, многие маркетинговые компании сейчас активно пытаются найти именно беременных женщин, потому что те находятся в преддверии большого количества предсказуемых покупок. Поэтому ритейлеры и производители детских товаров много платят за такую информацию. В эпоху таргетированной рекламы один только факт беременности примерно в 200 раз повышает стоимость профиля потребителя.

35-летнему математику Крису Маккинли (Chris McKinlay) из Калифорнийского университета в Лос-Анджелесе потребовалось всего 88 дней, чтобы осуществить дата-майнинг анкет на сайте знакомств и подобрать девушку, которая идеально подходит по характеру. Помог ему в этом доступ к суперкомпьютерам Калифорнийского университета, пишет Wired.

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

Дело в том, что я занимаюсь технологиями data mining и text mining последние лет пятнадцать. И поэтому все недавние скандалы, связанные с делом Сноудена и PRISM, XKeyScore, Muscular, СОРМ, чтением почты Гуглом, передачей конфиденциальных и гео данных с мобильников, и множество прочих оставили меня абсолютно равнодушным.

По очень простой причине – я уже знаю, что Большой Брат давно существует.



Если точнее, я абсолютно в этом уверен – так же, как не могу знать, что Солнце завтра взойдет, но весьма и весьма в этом убежден. И все новые доказательства существования Большого Брата полезны, но уже не обязательны.
А объяснение уверенности очень простое: при наличии необходимых ресурсов я сам мог бы его построить.

Как бы ни гремели скандалы про PRISM, про персональные данные и их утечки, социальные сети так и манят поведать о себе всё: какие котята нравятся, с кем ты дружишь и почему с утра такой не выспавшийся.
Целая энциклопедия о поведении большинства интернет-активной публики лежит совсем рядом, и мне всегда хотелось её пощупать. С одной стороны, эти данные лежат вроде бы в открытом доступе, но просто взять и проанализировать их не так легко — всё слишком неструктурировано и разрозненно. К тому же, насколько я знаю, пригодных для машинного анализа наборов данных о соцсетях практически не существует. А для России — так и подавно.
Выбора не оставалось, и пришлось, зловеще хохоча по ночам, писать простеньких пауков для соцсетей ВКонтакте, Одноклассники, МойМир и русского сегмента Фейсбук, которые за несколько месяцев неспешно собрали более или менее статистически-корректный семпл данных. Собиралась только та информация, которую люди сами о себе рассказали. А рассказали они много.

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

На Yet another Conference 2013 мы представили разработчикам нашу новую библиотеку Yandex SpeechKit. Это публичный API для распознавания речи, который могут использовать разработчики под Android и iOS. Скачать SpeechKit, а также ознакомиться с документацией, можно здесь.

Yandex SpeechKit позволяет напрямую обращаться к тому бэкэнду, который успешно применяется в мобильных приложениях Яндекса. Мы достаточно долго развивали эту систему и сейчас правильно распознаем 94% слов в Навигаторе и Мобильных Картах, а также 84% слов в Мобильном Браузере. При этом на распознавание уходит чуть больше секунды. Это уже весьма достойное качество, и мы активно работаем над его улучшением.



Можно утверждать, что уже в скором времени голосовые интерфейсы практически не будут отличаться по надежности от классических способов ввода. Подробный рассказ о том, как нам удалось добиться таких результатов, и как устроена наша система, под катом.

Недавно я наткнулся на такую удивительную штуку как число Данбара.
История такова. 20 с лишним лет назад, когда выражение «британские учёные» ещё не было мемом, антрополог Робин Данбар, изучая данные по человекообразным обезьянам, обнаружил, что численность их стаи подчиняется определённому закону. Есть максимальное количество членов стаи. Если стая разрастается и её численность превышает порог, она разделяется на две. Причём для разных видов этот предельный размер получается разным.

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

Я немного проапгрейдил график, чтобы выводилось не только абсолютные цифры, но и относительные. Добавилось 2 типа – относительный и прирост. Первый показывает изменения графика относительно начала выбранного отрезка времени, а второй – прирост голосов в виде столбчатой диаграммы (данные группируются в зависимости от масштаба графика).

Изменение места жительства пользователей Facebook

Математик и программист Стивен Вольфрам известен как автор программы Mathematica и научного поисковика Wolfram Alpha. Несмотря на большой объём текущей работы, Стивена всегда интересовал вопрос: можно ли математическими методами проанализировать траекторию жизни человека.

Рассматривая всевозможные списки Forbes, цены на квартиры в Москве или просто ценник нового Galaxy S4, легко впасть в уныние – кто-то же это все покупает. Причем в легкую, не парясь, не то что я. Проблема в том, что это все навязанная картина мира (не пугайтесь, пафоса в моем топике будет немного).

Существует такое понятие как «золотой миллиард». Это одна седьмая часть населения планеты, потребляющая большую часть ресурсов и обеспеченная базовыми удобствами. То есть еще раз, 6 миллиардов людей на планете живут хуже. Значительно хуже. Для того, чтобы понять, каков порог вхождения в этот «миллиард» можно воспользоваться сайтом статистики Global Rich List. Выбираем валюту, вводим либо годовой доход, либо накопленное состояние, и позиционируем себя на мировом финансовом поле.

Самую престижную награду в области журналистики в этом году получила газета Sun Sentinel из Южной Флориды за серию статей «Превыше закона: копы на высокой скорости».

Для расследования журналисты запросили из полицейских участков записи о прохождении патрульными машинами пропускных пунктов SunPass на платных дорогах. В каждой записи SunPass стоит отметка с точным временем прохождения пункта. Полиция предоставила информацию, не заподозрив подвоха.

Пятнадцать месяцев назад анонимный источник передал в распоряжение Международного консорциума журналистов-расследователей (ICIJ) 2 500 000 файлов общим объёмом в 260 гигабайт, содержащих данные о финансовых транзакциях 130 000 организаций и частных лиц из 170 стран мира, которые использовали офшорные зоны для уклонения от налогов.

ICIJ объединяет журналистов крупных мировых изданий, ведущих расследования злоупотреблений представителей власти и крупного бизнеса. Исследование 30 лет истории офшорных транзакций, которое 86 журналистов из 46 стран вели больше года — самый крупный проект консорциума за всю его историю. По данным организации Tax Justice Network, сильные мира сего прячут в офшорных «райских уголках» планеты от 21 до 32 триллионов долларов.

Вокруг adult киноиндустрии существует много мифов и заблуждений. Например, многие склонны думать, что типичная актриса — блондинка с пышными формами. На самом деле это далеко не так. Джон Миллворд (Jon Millward) осуществил дата-майнинг кинематографической базы Internet Adult Film Database и проанализировал информацию о 125 тыс. фильмах, которые содержат информацию более чем о 115 тыс. актёрах. Для статистического анализа были сделана выборка 10 000 человек.

Представители компаний IBM и WellPoint провели совместную конференцию, на которой объявили о начале коммерческой эксплуатации медицинской системы IBM Watson. Шесть экземпляров IBM Watson уже «трудоустроены» в больницы США в качестве врачей-диагностов.

Вчера на американских биржах произошла маленькая, но очень интересная аномалия, о которой оперативно сообщила аналитическая компания Nanex Research.

31 января 2013 года примерно за 400 миллисекунд до официальной публикации недельногого отчёта по запасам природного газа резко увеличилась торговая активность по фьючерсам на природный газ и паям индексных фондов, таких как UGZ, UNG и BOIL.

Отчёт опубликован в 10:30:00. На графике вверху показана активность на торгах индексным фондом UGZ в промежутке с 10:29:59 до 10:30:02, с официальными метками времени транзакций от разных бирж.

Предисловие: мой предыдущий пост на эту тему попал в утиль — на хабре, увы, больше нет раздела «ссылки», а даже частичный копипаст в виде затравки с ссылкой на оригинальный текст, запрещен правилами. Тем не менее, я считаю случившееся событие очень важным, поэтому рискую еще раз вынести это текст на обсуждение. Чтобы остаться в рамках правил, постараюсь пересказать основной текст своими словами.

Итак, с середины с декабря прошлого года в Google начал работать известный изобретатель и футуролог Рей Курцвейл. Как пишет в свой статье Олег Парамонов (а это и есть основной текст, на который я хотел сослаться), событие это из ряда вон выходящее и, я не побоюсь этого слова, революционное.



Давайте сначала разберемся зачем гуглу вообще исскуственный интеллект. На фоне новостей про Android, гидроэлектростанции и прочее-прочее-прочее, легко забыть, что Google, это прежде всего поиск. Собственно, именно он приносит львиную часть доходов. Но что такое поиск завтрашнего дня?

Цитата 1:
«Ещё в 2000 году Ларри Пейдж, один из основателей Google, объявил, что идеальной версией поисковика будет искусственный интеллект.
Цитата 2 (из документа Google для внутреннего пользования 2006 года):
»Чтобы стать лучшими в поиске, мы должны создать исследовательский центр мирового класса, занимающийся искусственным интеллектом".»

Разработчики суперкомпьютера IBM Watson сделали большую ошибку, когда закачали в его память словарь уличного жаргона с сайта Urban Dictionary. IBM Watson обучен распознавать смысл предложений/вопросов и отвечать на них, используя усвоенные массивы неструктурированных данных (data mining). Благодаря этому компьютер выиграл у чемпионов телевикторины «Своя игра» (Jeopardy) в 2011 году, после чего начал изучать медицинские справочники с целью диагностировать болезни по симптоматике, как доктор Хаус.

Разработчики думали, что информация о дополнительных смыслах слов улучшит искусственный интеллект, поможет ему лучше понимать людей. Они ошиблись. Уличный жаргон оказался исключительно вреден суперкомпьютеру. Однажды он даже ответил на вопрос неприличным словом “Bullshit”.

Каждый год 31 декабря David Eppstein публикует обзор препринтов за прошедший год, посвященных структурам данных и алгоритмам, опубликованным на arxiv.org. По ссылкам можно познакомиться с материалами за 2010 и 2011 (мой перевод) годы.

Раздел cs.DS развивается хорошими темпами: в этом году появилось 935 препринтов по алгоритмам и структурам данных, в то время как за 2011 их было 798. Раздел пока не дотягивает до сотни в месяц, хотя в июле (98 препринтов) этот порог был очень близок.

Это мой личный список из десятка препринтов, которые кажутся мне особенно интересными. Как обычно, я не вношу в него мои собственные работы и некоторые другие, о которых я писал раньше. Кроме того, здесь нет результатов (например, более быстрый алгоритм нахождения максимального потока), не появлявшихся на arxiv.org.

Вот они, в хронологическом порядке:

Информация о пробках появилась на Яндексе в 2006 году. Начинали мы с необходимого — научились строить схему загруженности городских улиц и учитывать текущую ситуацию при прокладывании маршрутов. Автомобилисты, ориентируясь перед выездом на эту информацию, уже могли сэкономить время в пути:


Затем, чтобы помогать водителям непосредственно во время движения, мы добавили в мобильные Яндекс.Карты (и, как следствие, в Яндекс.Навигатор) автоматическое перестроение маршрута. Приложения научились адаптировать маршрут при каждом заметном изменении ситуации в городе.

Собрав на десктопе и в мобильном информацию про «сейчас», мы перешли к решению вопроса «а как будет потом?»:


Первым шагом стала статистическая карта пробок — на ней можно посмотреть, как в среднем стоит и едет город в конкретный час конкретного дня недели. Мы предполагали, что у карты «обычных» пробок может быть полезный побочный эффект — возможность по ним спрогнозировать заторы на ближайшее время. Но практика показала, что усреднённая картина помогает примерно спланировать только, например, завтрашнюю поездку в аэропорт — но не помогает выезжающим сейчас избежать новых пробок. По нашим измерениям, даже в конце часового маршрута картина пробок на момент выезда обычно ближе к фактической, чем усреднение:



Неделю назад на Яндекс.Картах появилась возможность посмотреть изменения пробок в ближайший час — следующий наш шаг в решении вопроса про будущее. Для тех, кто в этом году не смог приехать на Yet another Conference, мы сегодня расскажем, что у нашего прогноза внутри, и как оно там оказалось.