Data Mining *

Всем привет. Продолжая тему того, что Andrew Ng не успел рассказать в курсе по машинному обучению, приведу пример своей реализации алгоритма k-средних. У меня стояла задача реализовать алгоритм кластеризации, но мне необходимо было учитывать степень корреляции между величинами. Я решил использовать в качестве метрики расстояние Махаланобиса, замечу, что размер данных для кластеризации не так велик, и не было необходимости делать кэширование кластеров на диск. За реализацией прошу под кат.

Всем привет. На этой неделе в курсе по машинному обучению профессор Andrew Ng рассказал слушателям про метод главных компонент, с помощью которого можно уменьшить размерность пространства признаков ваших данных. Но к сожалению он не рассказал про метод вычисления собственных векторов и собственных чисел матрицы, просто сказал, что это сложно и посоветовал использовать матлаб/октавовскую функцию [U S V] = svd(a).

Для моего проекта мне понадобилась реализация этого метода на c#, чем я сегодня и занимался. Сам метод главных компонент очень элегантный и красивый, а если не понимать математику которая лежит за всем этим, то это можно это все назвать шаманством. Проблема вычисления собственных векторов матрицы в том, что не существует быстрого способа вычисления их точных значений, так что приходится выкручиваться. Я хочу рассказать об одном из таких способов выкрутиться, а так же приведу код на c# выполняющий эту процедуру. Прошу под кат.

Музыканты-любители с сайта hooktheory.com решили найти закономерности в современной поп-музыке. Они провели статистический анализ аккордов 1300 песен и опубликовали результаты: какие созвучия чаще всего встречаются в музыке и как они взаимодействуют между собой.

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

При открытии своего интернет магазина владелец обычно поступает следующим образом:
— У меня есть выход на поставщика трусов, техники … (тут каждый вставляет свое), почему бы мне не открыть интернет магазин, это ведь круто, я слышал в Интернете можно МНОГО заработать, дело перспективное и прибыльное.
Таким образом, возникают тысячи сайтов, продающих одни и те же товары, захламляя собой интернет пространство все больше и больше.

Оказывается, трусы продает еще 1001 магазин. Вместо денег, как правило, предприниматель получает головную боль в виде seo, шмео и несоизмеримой стоимости контекстной рекламы.
Интернет магазин загибается, не успев появиться.

Предлагаю пойти другим путем.

Цель (она же Теория):
Поиск незанятых ниш для торговли.
Идеальная ситуация Спрос – есть, Предложений – нет, Дешевая контекстная реклама.

Представьте двух героев: коммерсанта Александра и сисадмина Василия. Вася, как олицетворение среднестатистического клиента, каждый вечер заходит в магазин Саши (представителя розничной сети) и покупает пиво. Саша заказывает для него 7 бутылок пива в неделю. Иногда Вася остаётся работать с ночевкой и не выходит из серверной, а иногда – после работы берёт по две бутылки пива для себя и главбуха.


^{График спроса на пиво в зависимости от жизненных приключений Васи}

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

Как и многие люди технического склада ума, я с крайним недоверием отношусь к астрологии, гороскопам и прочим псевдонаукам. Моё мировозрение пошатнулось когда я от скуки решил изучить влияение времени года в которое рождается человек, на его психические особенности. Оценка психических особенностей производилась по результатам соционического теста из приложения VK, которое насчитывает более 500000 пользователей. Надёжность и валидность теста небольшая, да и вся соционическая модель имеет ряд проблем. Но нам важно другое: понять есть ли хоть какие-то отличия между людьми родившимися в разное время. Объём выборки в полмиллиона человек позволяет надеяться на положительный результат. В ходе исследования ожидалось получить линейную зависимость между продолжительностью светлого времени суток в день рождения человека и его психотипом, но получилось

26 апреля стартовал конкурс рекомендательных систем Million Song Dataset Challenge. Завершение — через три месяца, 9 августа. В ходе конкурса нужно построить систему, которая по 100% истории прослушивания музыки для 1М пользователей и 50% истории для 100К пользователей сможет максимально точно достроить недостающие 50%. При этом доступны не только данные по прослушиванию, но и обширная база метаданных и даных по контенту от The EchoNest, MusicXMatch и Last.fm. При желании можно пользоваться любыми другими данными (у многих других музыкальных сервисов есть API, через который можно выудить ценную информацию).

Организаторы — CAL UCSD, LabROSA CU, IMIRSEL и UIUC.

Как такового приза у конкурса нет, но компания Zvooq решила сделать его чуть более интересным для российских участников. Лучшая команда из России (вне зависимости от абсолютного места) получит $5000 и возможность бесплатно отправить одного участника на ISMIR 2012.

Условия получения этого бонуса — все участники команды должны проживать в РФ, должно быть опубликовано описание используемого подхода (например, на Хабре или arxiv.org), команда должна заявить о себе на challenge@zvooq.com.

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

Если вы не знаете, какой тарифный план из трёх предложенных стоит запустить по всей стране, надо воспользоваться клиентской аналитикой, которая возьмёт каждого отдельного человека из базы, оценит эмоциональные и практические мотивы перехода – и позволит понять, сколько людей будут пользоваться этим тарифом.

Именно так выглядит Data Mining в клиентской аналитике. И именно так это уже работает на практике в сотнях крупных компаний по всему миру и в нашей стране.

UPD 4.04. Новость оказалась первоапрельской шуткой ChessBase, которая из-за ошибки CMS была опубликована на сайте 2 апреля. Поверила даже Википедия, изменив статью про королевский гамбит.

Запустив шахматную программу Rybka на рабочей станции IBM POWER 7 с 2800 ядрами, автор программы сумел решить королевский гамбит — один из самых сложных и острых дебютов шахматной партии, который активно использовали Борис Спасский и Бобби Фишер. Компьютерная программа рассчитала исход всех вариантов развития шахматной партии и пришла к неожиданным результатам.



Оказывается, в случае принятия чёрными жертвы на f4 у белых остаётся только один ход, который ведёт к ничьей (в случае идеальной игры с обеих сторон) — слон на e2. Во всех остальных случаях белые получают мат.

Здравствуйте.

В контексте анализа данных из твиттера возникла задача обработки хештегов. Нужно было взять хештег и разбить его на отдельные слова (#habratopic => habra topic). Задача казалась примитивной, но, получается, я ее недооценил. Пришлось перебрать несколько алгоритмов пока не было найдено то, что надо.

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

Здравствуйте.
Если вы занимаетесь DataMining, анализом текстов на выявление мнений или вам просто интересны статистические модели для оценки эмоциональной окраски предложений — эта статья может оказаться интересной.
Далее, чтобы не тратить время потенциального читателя впустую на груду теории и рассуждений, сразу краткие результаты.
Реализованный подход работает приблизительно с 55% точностью в трех классах: негативный, нейтральный, позитивный. Как говорит Википедия, 70% точность приблизительно равна точности человеческих суждений в среднем (в силу субъективности трактований каждого).
Следует отметить, что существует немало утилит с точностью выше полученной мной, но описанный подход, можно достаточно просто усовершенствовать (будет описано ниже) и получить в итоге 65-70%. Если после всего вышеизложенного у вас осталось желание читать — добро пожаловать под кат.

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

Потом перезваниваете с телефона сестры и получаете ласковое «А какого цвета у вас Интернет?», и начинаете понимать, в чём дело.

Да, это реально возможно на практике. Давайте для примера возьмём некий типовой call-центр и покопаемся в его уже собранных данных, а потом подключим немного математики.

Разработчик программного пакета Mathematica и научной поисковой системы Wolfram Alpha Стивен Вольфрам выложил результаты анализа цифровых данных, которые скопились у него за годы. В числе прочего — визуализация 300 тыс. отправленных электронных писем с 1989 года, 100 миллионов нажатий клавиш с 2002 года, телефонные звонки, встречи, время редактирования файлов разного типа с 1980 года и т.д. В результате проявились некоторые интересные корреляции между различными аспектами жизни, а также структурные изменения, которые произошли в течение десятилетий.

Подобный личностный анализ может сделать каждый с помощью новых функций поисковика Wolfram Alpha Pro.

Среди многочисленных проектов компании Google есть один очень важный проект, которым компания занимается уже более пяти лет, и в то же время он на удивление мало освещается в прессе. Речь идёт о стандарте GTFS (изначально Google Transit Feed Specification, но с 2009 года расшифровку сменили на General Transit Feed Specification) — общий протокол для расписания общественного транспорта, который компания Google предложила в 2006 году.



Сейчас Google получает информацию от 475 транспортных компаний США и Европы, но пока что расписание на Google Maps полноценно работает только в четырёх американских городах (Бостон, Портленд, Сан-Диего, Сан-Франциско) и двух европейских (Мадрид, Турин). Жители этих городов могут в привычном интерфейсе Google Maps смотреть, через сколько минут на остановку придёт нужный автобус, троллейбус или трамвай — c июня 2011 года для этих городов работает функция Live Transit Updates, то есть обновление в реальном времени информации о реальном местонахождении транспорта.

Несколько дней назад американцы объявили о выводе войск из Ирака. Они ушли не с пустыми руками, а увезли биометрические данные трёх миллионов иракских жителей (примерно 10% населения). В течение нескольких лет американские пехотинцы носили с собой портативные оптические сканеры, которые позволяют быстро в полевых условиях сделать снимок радужной оболочки глаза и снять отпечатки пальцев у любого прохожего.

Ценная база данных является собственностью американской армии и будет храниться в США.

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

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

 

Миланский университет и Facebook окончили исследование о теории шести рукопожатиях. За основу брался социальный граф Facebook. Были исследованы все аккаунты Facebook. В итоге получилось, что двух любых людей отделяют не 6, а 4,74 уровня связи.
И в США, кстати, количество звеньев меньше — 4,37 (по статистике более половины американцев старше 13 лет пользуются Facebook).
«Даже если взять самого территориально удаленного пользователя Facebook в сибирской тундре или перуанских джунглей, друг вашего друга, вероятно, знает друга их друга» — так отмечают исследователи.
Три года назад Microsoft провела аналогичное исследование на 242 миллионах пользователей MSN, написавших хоть одно сообщение за месяц. Их результат тогда был равен 6,6.
А вот исследование аудитории ВКонтакте, которое сделал shuttie, показывает, что этот результат в более локализованной сети — меньше, 5.65 пользователей.

Однажды в студеную зимнюю пору я столкнулся с упоминанием того, что кто-то в Facebook пытается подтвердить теорию шести рукопожатий. Для тех кто не в курсе, эта теория заключается в том, что все жители земли в среднем знакомы друг с другом через цепочку из пяти друзей (т.е. шести рукопожатий). Подробнее об истории этой теории можно прочитать в википедии, там же можно узнать о том, что Майкрософт несколько лет назад пыталась подтвердить эту теорию на основе данных о контакт-листах мессенджера MSN — в результате у них получилось 6,6 рукопожатий, что вполне вписывается в теорию.

Очень мне захотелось эту теорию подтвердить самому, используя данные, которые есть под рукой — ВКонтакте. Для претворения моей странной идеи в жизнь надо было решить целый комплекс проблем:

1. На каких данных это все расчитывать.
2. Где эти данные взять.
3. Как эти данные сохранять.
4. Каким алгоритмом воспользоваться для расчетов.

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

Классификация

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