Author Archives: Firepush

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

Как-то раз меня спросили на работе: “А есть ли у нас некие шаблоны поведения, которым следуют игроки при прохождении определенного этапа игры? И если есть – сколько таких шаблонов и какие они?”

Вопрос интересный и на первый взгляд простой. Но, как это обычно бывает, пришлось повозиться.

Первое решение, которое приходит в голову – кластеризация на основе алгоритмов расстояния между словами (расстояние Левенштейна, Хэмминга и т.д.). Но самое неприятное – это то, что готовые библиотеки применяют алгоритмы только к “словам”. Но не к последовательности элементов в массиве. (Очень странно, что очевидное решение этой проблемы не пришло мне в голову сразу, но об этом – в конце статьи). Расстояние Хэмминга – очень прост в реализации, но слишком чувствителен. Левенштайн мне переписать было не под силу.

Так что я решил попробовать написать свой велосипед)

Итак, определимся, чем для нас является шаблон поведения в игре:

Шаблон поведения – это последовательность из уникальных событий.

В контексте игры последовательность может выглядеть так:

установка – завершение таска №1 квеста №1 – завершение №2 квеста №1  – завершение №1 – получение левела №1  –  трата рубинов №1  и т.д.

Почему уникальных? Для простоты алгоритма, признаюсь. Но для большинства событий это условие и так выполнятся: “квест №1”, например, можно завершить только один раз. А для таких, как “трата рубинов”, к названию будем приписывать порядковый номер события данного типа: трата рубинов №1, трата рубинов №2  и т.д.

Подготовка данных для анализа потребовала некоторых усилий. В конечном итоге в R мы получаем Named List, где имя элемента листа – это ID соответствующего игрока, а значение – вектор строк с уникальными элементами последовательности.

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

Как можно охарактеризовать “расстояние” между двумя этими последовательностями? Первое, что приходит на ум – сравнить индексы позиций соответствующих элементов и посчитать среднюю “разницу”. Чем она больше, тем “дальше” они друг от друга.

Функция для подсчета данного коэффициента в R:

 

Мы получаем таблицу такого вида:

elem rangx rangy diff
1 A 1 1 0.0000000
2 C 3 2 0.3333333
3 B 2 3 0.3333333
4 D 4 4 0.0000000
5 E 5 5 0.0000000
6 F 6 6 0.0000000

inner_join – позволяет нам игнорировать элементы, которые не встретились в обеих последовательностях. rangx и rangy – индексы соответствующих элементов в первом и втором векторе. diff считается для каждой пары этих индексов, как абсолютная разность индексов, деленная на половину длины наибольшей последовательности. В конечном итоге получаем diffres, как среднее значение всех diff-ов,  в нашем случае – 0.1111.

Если сделать две перестановки, то расстояние уже будет равно 0.2222:

 

Ну а если сравнить a с “совсем” противоположным d, то получим 1:

Таким образом, самые близкие последовательности будут иметь расстояние близкое к нулю, а самые далекие –  к единице.

Как ни странно, даже с этим простым алгоритмом уже можно делать кластеризацию!

Но давайте поразмыслим еще. Мы ведь совсем не учитываем “липкость” элементов. Давайте сравним три такие последовательности:

В b – элементы попарно переставлены. А в с – первую тройку элементов поменяли местами с последней тройкой. Теперь сравним расстояния:

Но резонно ли говорить, что c гораздо дальше от a, чем b? Ведь в с есть такие же подпоследовательности, как и в a, тогда как в b  – ни одной?

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

Упрощенно он рассчитывается так: из двух рассматриваемых последовательностей берется та, что с меньшей длиной. Смотрим первый элемент этой последовательности, смотрим какой элемент за ним следует и проверяем повторяется ли эта подпоследовательность у соседа. Если да, идем дальше – попутно запоминая длину рассматриваемого “лоскутка”.  Если лоскуток “обрывается” – запоминаем длину этого лоскутка и начинаем считать длину для нового. При этом в алгоритме есть понятие нулевой длины, когда лоскуток – из одного элемента.

Поделив среднюю длину “лоскутков”, на длину более длинной последовательности и применив некоторые магические арифметические преобразования, получим другой коэффициент расстояния.

Как и ожидалось, этот коэффициент считает по-другому. И по-своему правильно :)

Сама функция выглядит так (простите за отстойный код):

Добавляем шумы и строим графики

Давайте проверим на графиках, как работают обе функции определения расстояния в зависимости от силы шума, добавляемой к одной и той же последовательности. Пусть дана последовательность a <- LETTERS (26 букв алфавита).

Создадим функцию shuffle, которая принимает на вход два аргумента: кол-во перестановок и саму последовательность:

Чем больше x, тем сильнее последовательность на выходе будет не похожа на исходную.

Создадим вектор “иксов” с нарастанием, которые будем скармливать этой функции:

Теперь нагенеририруем последовательности с нарастающей шумностью и сохраним в листе gro:

Ну и наконец посчитаем двумя способами расстояния между a и каждой из последовательности листа gro

 

iumG2NA

8pEqUWy

Что же, вполне неплохо. Чтобы учитывать и тот и другой фактор, будем считать среднее геометрическое двух коэффициентов:

geomMean

Приступаем к кластеризации

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

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

Генерация шума:

Соберем в кучу и перемешаем:

А теперь посчитаем матрицу расстояний. Внимание! Эта операция ресурсоемкая. Поэтому для больших объемов данных лучше делать выборки.

Примерно за 80 секунд получаем такую матрицу (первые 5 строк и столбцов):

KaJkikZ

Каждый элемент означает дистанцию между последовательностями с индексом соответствующей строки  и столбца. На основе этой матрицы расстояний и строится кластерный анализ. Я использовал R-библиотеку “cluster”.

Итак:

LWR0teq

 

 

rangdiff

 

 

 

meanlen

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

Мысль о том, что каждый элемент можно сопоставить отдельному символу (что по сути и было сделано) и “склеить” в слово до меня дошла уже после проделанной работы. Применив код ниже (который отработал в разы быстрее):

 

Получим вот такую замечательную картинку:

lev

Очевидно, что применение этого алгоритма намного эффективнее. Как в плане точности, так и в скорости. При этом элементы последовательности могут повторяться. Недостаток этого подхода – кол-во символов ограничено, тогда как уникальных элементов в наборе может быть очень много. Я пытался использовать список разных символов из юникода, но R у меня отказывается их обрабатывать.  

Так а что там с игрой? Кластеризация не позволила выделить какие-то обособленные группы:

seq

Что же, плохой опыт тоже опыт)

 

Методика оценки эффективности рекламы сервиса

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

Знания, которыми я поделюсь в этой статье, получены опытным путем и, можно сказать, выстраданы. Вероятно, если бы я знал все это ранее, было бы сэкономлено много времени, денег и нервов.

В качестве примера возьмем условную социальную игру на Facebook. Допустим, мы запустили 5 рекламных кампаний с разными настройками и промо-материалами, которые стартовали в разное время. Результат, который мы увидим в отчете рекламного аккаунта на Facebook, когда открутим все кампании, будет выглядеть примерно так (на условное 20.01):

table1

Что мы можем сказать об эффективности кампаний? Ровным счетом ничего!

Самый очевидный, но ошибочный, подход – сравнить CPI (Cost Per Install) кампании со средним доходом с пользователя за его игровую жизнь, т.е. с его LTV (lifetime value) во всей игре (про LTV напишу отдельно ниже, пока же допустим, что мы его знаем) Так делать нельзя, так как кампании могут в разы отличаться друг от друга в эффективности.

Вы заметите, что у нас есть данные по доходу с каждой кампании. Но что с ними делать? А проблемы в следующем:

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

Можно было бы конечно подождать 2-3 месяца, когда все эти игроки наиграются и уйдут, и сравнить выручку с затратами. Но это не дело: оценивать эффективность нужно сразу, чтобы отключать неэффективные кампании и подключать новые.

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

Расчет LTV по историческим данным

Начнем с того, что нам нужно построить график LTV для нашего продукта. Не просто узнать значение LTV, а именно построить график.

Для этого сначала нам нужно выгрузить логи всех инсталлов нашей игры (за исключением тех, что были относительно недавно, то есть чей срок меньше lifetime игроков). Здесь нам важны только два поля: id игрока и момент инсталла (user_id и install_ts). Затем выгружаем все платежи из игры, где важны уже три поля:  id игрока, размер платежа, и момент платежа (user_id, money и payment_ts).

Далее мы делаем inner_join этих двух таблиц по полю user_id. В итоге получим таблицу такого вида:

table2

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

table3

Теперь сгруппируем по значению delta все платежи и посчитаем сумму значений money для каждой группы. Получим выручку всей игры, сгруппированную по “дням после инсталла”, на которые были совершены платежи в игре. Теперь, если каждое полученное значение поделить на кол-во уникальных user_id из таблицы инсталлов, посчитать сумму накопленным итогом для всех дней и построить график, получим примерно вот такой результат:

table4

Из данного графика мы можем сделать несколько выводов:

  • асимптота графика есть LTV нашей игры. В примере выше это около 1,5 долларов.
  • график приближается к асимптоте примерно через 90 дней. Это можно считать сроком жизни (lifetime) игрока, за который имеет смысл считать сам LTV.
  • на пятый день после инсталла игрок в среднем тратит 0,4 доллара, то есть 26% денег, которые он потратит за все время игровой жизни.

Последний пункт является ключевым. Это значит что уже через 5 дней после старта кампании, при достаточном кол-ве инсталлов, можно оценить прогнозный LTV (eLTV) данной кампании и сравнить с CPI. Если eLTV > CPI, кампанию считаем успешной и продолжаем ее до тех пор, пока для каждой новой “порции” трафика из рассматриваемой кампании это неравенство соблюдается.

Поскольку сервис постоянно изменяется, периодически этот коэффициент (26% в примере) тоже нужно пересчитывать.

Помимо метрики eLTV имеет смысл считать 1-day retention (можно и для других дней), то есть долю вернувшихся на день N после установки. Эта метрика не так важна как eLTV , но если она в разы ниже средней по игре, можно смело отключать кампанию, не дожидаясь пока можно будет оценить eLTV.

Я рассмотрел подход к оценке эффективности рекламных кампаний на примере условной free2play игры. Но его можно применять и и для любых других сервисов: SaaS-платформы, хостинг-услуги, аналитические сервисы. При этом горизонт планирования будет значительно более долгим, а LTV и CPI – на порядок выше.

Анализируем DAU игр Вконтакте

Введение.

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

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

Идея мне пришла после того, как я прочитал статью Галенкина о Steam Spy – его новом замечательном бесплатном сервисе анализа игр в Стиме (http://steamspy.com/). Удивительно, что до него никто не додумался до такой простой по сути идее.

Сохранение статуса игроков

Итак, наша задача – определить DAU игр. У Вконтакте есть довольно обширный набор методов API. Среди них  есть метод получения информации об интересующем приложении: stats.get. Однако, подавляющее большинство игр скрывает в настройках статистику о DAU от любопытных глаз конкурентов.

Возможно, многие из вас замечали, что во время того, как запущено то или иное приложение в ВК, у вас автоматически проставляется статус с точным названием приложения:

tKN5TJ2

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

Анализируя частоту упоминаний точного вхождения названий игр в статусах пользователей ВК, теоретически можно получить оценку DAU.

Отлично! Пробуем.

Сначала создадим stand-alone приложение в ВК и сгенерируем access_token, который будем использовать для дальнейших запросов.

Первое, что приходит в голову: берем рандомные id живых людей и для каждого id смотрим статус (метод users.get, с указанием status в fields). Боль начинается тогда, когда начинаешь прикидывать, сколько времени понадобится на то, чтобы пробежаться по списку из хотя бы миллиона юзеров. ВК разрешает стучаться к API не чаще 3 раз в секунду. Дело в том, что играющих в конкретный момент юзеров в момент обхода выборки будет 1-2% от силы. С учетом того, что все они играют в разные игры, мы получим ничтожно мало данных для анализа.

Надеясь на то, что в API все же есть способ массового получения инфы о юзерах, я наткнулся на метод groups.getMembers, где тоже можно указать status в параметре fields. Супер! Теперь за раз можно получить 1000 статусов! С этим уже можно работать. Но это не все!

(update: как оказалось, в обычном users.get тоже можно запросить статус и указать сразу до 1000 id через запятую. Так что возня с группами была лишней)

У ВК есть такой неприметный метод в самом конце списка – execute. О том, что это, я узнал из этой статьи на Хабре: http://habrahabr.ru/post/248725/

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

За один запрос мы можем запустить 25 любых других методов и получить обработанный результат!  25000 статусов за запрос – вот это поворот! :)

С основной проблемой разобрались, ок. Но из каких групп брать юзеров? Я решил, что лучше всего подойдут официальные сообщества игр, id которых легко спарсить из страничек описаний игр. Численные Id-шники самих приложений из топа и их названия можно легко получить методом apps.getCatalog.

В конечном итоге получаем простой алгоритм: берем id группы, собираем статусы участников (в больших группах я обходил не больше 150 тысяч пользователей), сопоставляем с эталонным списком названий игр. Если найдено соответствие конкретного статуса определенной игре, пишем в файл лога строку в формате: user_id;title;date. Переходим к следующей группе.

Далее я залил скрипт на виртуалку DigitalOcean, запустил и оставил на 8 часов. В результате получил файлик размером 50 мб формата csv, который я выгрузил в R и вручную проанализировал.

Анализ полученных данных.

Вот таким нехитрым способом мы получаем табличку вида 

title freq
1 Сокровища Пиратов 43222
2 Пасха 2015 40020
3 Клондайк 29546
4 Инди Кот: Три в ряд! 26142
5 Вормикс 24253
6 Аватария — мир, где сбываются мечты 22614

 

Где freq – это то, сколько раз был найден статус с игрой в выборке.

Уже определенные выводы можно сделать. Но продолжим.

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

Получим таблицу вида:

id title dau
1 2388722 Нано-ферма 162633
2 2296756 Запорожье 139185
3 1968803 World Poker Club – Покер 123437
4 2164459 Правила Войны 115087

Далее делаем inner_join по столбцу title, фильтруем все, что с freq < 20 и coef>100 (там не игры получались) и считаем coef – отношение dau к freq:

title id dau freq coef
1 Нано-ферма 2388722 162633 16759 9.70
2 Запорожье 2296756 139185 10250 13.58
3 World Poker Club – Покер 1968803 123437 4011 30.77
4 Правила Войны 2164459 115087 5481 21.00
5 Войны Престолов 2924782 88982 5485 16.22

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

Посмотрим на  “summary” значений coef:

Min.  1st Qu. Median Mean 3rd Qu. Max.
2.40 14.36 22.78 29.34 39.04 82.59

При стандартном отклонении в 19,72 коэффициент вариации равен 0,67. Много, как я и предполагал.

Посмотрим на гистограмму распределения coef:

Rplot

 

Заметно длинное правое “плечо” у распределения. Это нужно иметь в виду, если нужно определять пределы, в которых находится значение при заданном уровне точности

Зависимость значения freq от соответствующей позиции в рейтинге DAU в нашей последней таблице:

Rplot02

Теперь осталось посчитать оценку DAU для всех приложений каталога:


title freq pred
1 Сокровища Пиратов 43222 1268155
2 Пасха 2015 40020 1174207
3 Клондайк 29546 866894
4 Инди Кот: Три в ряд! 26142 767019
5 Вормикс 24253 711595
6 Аватария — мир, где сбываются мечты 22614 663506
7 Контра Сити 20654 605999
8 Долина Сладостей 20098 589685

Выводы:

Как минимум мне удалось определить порядок размера аудитории игр в ВК, у которых скрыта статистика. Я проверил принципиальную реализуемость подобного подхода к исследованию и в целом доволен проделанной работой.

Потенциально есть много способов улучшить качество оценки: увеличить объем собираемых данных (например используя несколько аккаунтов для сбора данных), улучшить случайность выборки, увеличить частоту сбора и т.д. Но я не планирую это делать)

Буду рад ответить на вопросы.

 

Парсинг сайта при помощи PhantomJS + CasperJS

В данной статье я расскажу о том, как при помощи скриптового браузера PhantomJS со связкой с CasperJS мне удалось собрать ссылки на RSS-ленты нужных сайтов. Начало истории можно узнать в предыдущей статье про алгоритм нахождения тем новостей.

О существовании подобных инструментов я узнал совсем недавно из свежей статьи на Хабре про SlimerJS. Последний отличается от Фантома другим браузерным движком и тем, что видно окно браузера. Изучив тему внимательней, я понял что  CasperJS значительно облегчает написание кода. Но сделать так, чтобы Slimer заработал вместе с ним, у меня не получилось. Плюнув, я установил Фантом – все пошло без проблем.

Вся прелесть в том, что нам не нужно имитировать браузер, так как мы им и являемся! Вся возня с куками, прописыванием мета-информации и прочим, как при работе с curl – в прошлом. Некоторое время я поупражнялся с примерами из FAQ, пробежался вдоль по документации CasperJS и приступил.

Но немного отвлечемся. Напомню, что на руках у меня был список из более чем двух тысяч ссылок на самые разные ресурсы из Яндекс-Новостей. Задача: имея этот список, получить список ссылок на rss-ленты. От парсинга яндекс-подписок я отказался по причинам, указанным в прошлой статье. Удивительно, что мне не сразу пришла мысль, что помимо кривых яндекс-подписок, есть другие крутые RSS-читалки, учитывая что сам активно пользуюсь Feedler. А что, если они тоже предоставляют ссылки на rss-ленты?

В первую очередь посмотрел упомянутый Feedler. Отпадает – rss ссылок не дает. Стал гуглить и почти сразу наткнулся на digg.com. Минималистичный дизайн сразу приглянулся. Зарегистрировался, проверил – идеально! Помимо того, что определяет 90% всех ссылок, делает это почти всегда верно, причем, если находит несколько лент, показывает все по убыванию важности (тоже весьма точно). Но и это не все! Как оказалось, не нужно даже каждый раз при поиске вписывать ссылку в поисковую форму: искомое слово подставляется get-параметром:

voBhqPa

Просто подарок судьбы!

Итак, формализуем. Скрипт должен авторизоваться на сайте, потом по циклу генерировать урл в формате, как на скрине выше, открывать страницу и парсить ссылки на RSS. Ничего сложного.

Но, как всегда, возникли некоторые затруднения. Логин только через fb, twitter или g+. А еще иногда процесс парсинга непонятно почему прерывался. Поскольку окно браузера не отображается в Фантоме, я долго не мог понять в чем дело. На помощь пришла функция, позволявшая сделать скриншот браузера и сохранить в корень программы. Так я определил, что во всем виновато всплывающее окно, предлагающее похвалить Digg в соцсетях, и блокирующее все действия. Благо, это было легко исправить, указав, что, если на странице есть элемент с определенным css-селектором, нужно нажать на него (крестик этого окна) и продолжаем дальше.

Код программы привожу ниже:

 

Результат на выходе получился не самым читаемым, так как fetchText не поддерживает разделителей. Впрочем, все ссылки все равно начинаются на http, поэтому с их последующим разделением проблем не было.

 

Событийная аналитика

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

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

При использовании данного подхода под событием мы понимаем элементарную единицу данных, которую имеет смысл записать в логи  – в наш “бортовой журнал”. Когда в изучаемой системе что-то произошло, это и значит, что у нас появилось конкретное событие, сведения о котором следует записать в логи.

В общем виде почти любое событие в игре можно представить человеческим языком вот так:

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

Но когда машина общается с машиной, как правило, применяется особый формализованный язык. Часто это XML или JSON. Мы будем использовать второй, его достаточно легко читать и человеку.

Любое событие должно быть представлено в виде одномерного массива пар ключ:значение.

Посмотрим на следующий пример:

{

  • “event”: “inapp_purchase”,
  • “user”: “Vasya Pupkin”,
  • “time”: “2015-01-14 18:00:00”
  • “object”: “coins”,
  • “coin_value”: 1000,
  • “price”: 100,
  • “sex”:”m”,
  • “age”:40,
  • “level”:10,
  • “install_date”:  “2015-01-13  00:00:00”

}

Произошло событие – внутриигровая покупка, кто совершил – Вася Пупкин, в какое время – “2015-01-14 18:00:00”, что купил – монетки, сколько монеток – 1000, сколько рублей потратил – 100, пол – мужик, возраст – 40, уровень игрока – 10,  день установки игры Васей –  “2015-01-13  00:00:00”. Ничего сложного на первый взгляд.

Но дьявол в деталях, а именно в следующем. Иногда происходит желание вместить в название ключа (то есть в название измеряемого параметра) смысл значения и наоборот. Старайтесь ни в коем случае не допускать этого!

Классический пример: в паре object: “coins” в значении мы могли бы сразу указать объем лота (т.е. кол-во купленных монеток, который у нас выделен в отдельный параметр coin_value). Получилась бы в нашем случае такая пара:

object: “coins_1000”

Не говоря уже о простом неудобстве, проблемы могут начаться сразу, как только мы захотим изменить кол-во монеток в данном лоте.  Нам придется менять значения параметра object на, скажем,  “coins_1300”. Но тогда в статистике это уже будет отдельная сущность, что может привести к плохим последствиям.

 

Проектирование структуры событий

Структура событий должна быть представлена в виде иерархической системы. Я рекомендую использовать Excel-таблицы, получается удобно. Рассмотрим пример с таким простым событием, как трата виртуальной валюты.

Итак,  у нас уже есть первая пара: event: “currency_spend”. Далее мы должны спросить себя, а что мы хотим узнать об этом событии? В игре есть два типа виртуальной валюты – hard (кристаллы) и soft (монетки). Ага, значит ключ здесь – тип виртуальной валюты, а значения – “diamonds” и “coins”:

1 

Думаем дальше. Что еще мы хотим знать? Конечно, сколько валюты потратил игрок. Ключом пусть будет “amount”, а в ячейку значения вставим тег %n%, где n  – это переменная, означающая объем потраченной валюты.

Разумеется нужно указать, на что именно была потрачена валюта. Будем считать, что в игре у каждого объекта, на который можно потратить валюту, есть уникальный id. Итак, ключ target_id, значение – %id%.

2

На этом можно было бы остановиться. Но мы ведь аналитики, нам нужно больше данных! Target_id сам по себе нам ничего не даст. Копаем дальше. Какие типы трат существуют в игре?  Мы можем купить конкретную “вещь” (семена, домик, лейку, украшение и т.д.), можем ускорить что-то в игре (постройку здания, выращивание растения или животного и т.д.), можем пропустить сложный квест, а еще можем разблокировать к покупке что-то, что доступно только “эльфам 80-уровня”. Добавляем ключ target_type и 4 возможных значения: buy, accelerate, skip, unlock.

Но у каждого из этих типов есть подтипы! Как быть? В этом случае для каждого нового “уровня вложенности” в таблице создаем еще два столбца для пары ключ-значение (ниже будет скрин).

Начнем с buy. “Обычная” покупка может быть совершена из окон следующих видов: лот в магазине, окно платных подарков друзьям, окно распродажи (кратковременные акции), окно “допродажи” при нехватке ресурса на определенные действия в игре и окно апргейда уже имеющихся объектов в игре.

Теперь accelerate – ускорение. Ускорить можно рост растения или животного, производство чего-либо в определенной постройке или процесс апгрейда здания. Но у апгрейда и производства есть разные уровни. Хотелось бы знать, например, производство какого уровня было ускорено.

Итоговая структура данного конкретного “события” будет выглядеть так:

3

Таким образом, событие “произошла трата монеток в кол-ве 100 штук на объект – молочная ферма с целью ускорить производство 5 уровня” будет выглядеть так:

{

  • “event”: “currency_spend”,
  • “type”:”coins”,
  • “amount”: 100,
  • “target_id”: “milky_farm”,
  • “target_type”: “accelerate”,
  • “subtype”:”production”,
  • “prod_lvl”:5

}

Чего-то не хватает… Точно, куда делся Вася Пупкин? Мы обязательно должны включить информацию о Васе. Но нет смысла указывать эти параметры именно внутри currency_spend, так как знать, с кем связано событие надо всегда, какое бы событие мы ни отправляли.

Параметры, которые отправляются в любом событии независимо от его типа, иногда называются суперпараметрами. Часть мы уже упоминали в первом примере.

Таким образом полное событие будет выглядеть следующим образом:

{

  • “event”: “currency_spend”,
  • “type”:”coins”,
  • “amount”: 100,
  • “target_id”: “milky_farm”,
  • “target_type”: “accelerate”,
  • “subtype”:production,
  • “prod_lvl”:5
  • “user”: “Vasya Pupkin”,
  • “time”: “2015-01-14 18:00:00”
  • “sex”:”m”,
  • “age”:40,
  • “level”:10,
  • “install_date”:  “2015-01-13  00:00:00”,
  • “paying_status”: “whale”,
  • “referer”: “ad_facebook_target”

}

 

По похожему принципу создаются все остальные события. Стоит отметить, что достаточно отправлять всего лишь три типа события: “установка”, “вход в игру” и “покупка за реал”, чтобы можно было создать собственную систему аналитики со всеми стандартными базовыми метриками (DAU, retention, ARPU и т.д.)

Пример с currency_spend характеризует так называемые custom events (“пользовательские” события), анализ которых позволяет понять работу игровой механики.

В этой статье я не стану рассказывать о технологиях. Скажу лишь, что по большей части это дело вкуса. Возможность отправки custom events существует во многих платных (Upsight, Mixpanel и др) и бесплатных системах аналитики (Flurry, Google Analytics). Во многих есть серьезные ограничения, как на кол-во параметров в событии, так на само кол-во событий. Многие предпочитают создавать собственные системы на основе различных технологий. Я так или иначе работал с MongoDB, ElasticSearch и обычной MySQL, которая вполне справлялась со своей задачей. Для анализа записанных данных существует целый ряд отдельных инструментов, как платных и так и бесплатных. Kibana, Splunk, Tablue или самописные.

Огромным плюсом при анализе сырых данных будет владение языком программирования R. Рекомендую пройти набор курсов Data Sceince на Coursera

Похожая статья есть в блоге GoPractice. Я во многом согласен с автором, кроме похода к построению структуры событий.

 

Свои Яндекс-Новости с преферансом и куртизанками

Я, как и миллионы сограждан, узнаю новости из топ-5 ленты Яндекс-Новостей на главной поисковика. Одним прекрасным днем я задумался о том, как именно работает их алгоритм.

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

Цель максимум:

Научиться предсказывать темы новостей из топ-5 яндекс-ленты.

Цель минимум:

Научится просто грамотно выделять темы новостей.

Основные шаги такие:

  1. Сбор ссылок на все СМИ, которые участвуют в Яндекс-новостях
  2. Сбор ссылок на RSS-ленты этих ресурсов
  3. Настройка парсера RSS-лент и запись сырой информации о статьях в базу данных (сбор Raw Data)
  4. Составление алгоритма определения тем новостей за определенный период (задача кластеризации) и записи информации в БД (processed data)
  5. Разработка веб-интерфейса с топом всех новостей и различными параметрами


Сбор ссылок на СМИ

Сбор ссылок я осуществлял с помощью программы Content Downloader (http://sbfactory.ru/). Крайне рекомендую! Программа платная, но не дорогая (от 1000 до 2000 рублей в зависимости от кол-ва потоков) Научиться пользоваться не сложно – есть много обучающих материалов и автор активно выходит на связь. Я пользуюсь не самой новой версией, просто потому что привык к старому интерфейсу.

Алгоритм сбора ссылок выглядел следующим образом:

а) сбор ссылок на страницы сайта http://news.yandex.ru/ методом массового обхода всего сайта (есть такая функция в Content Downloader). Весь сайт само собой обойти не удастся да и не нужно. Я собрал несколько тысяч страниц, чего вполне хватило.

б) сбор ссылок на новости СМИ со страниц, собранных выше. Чтобы указать программе, что именно нужно парсить, нужно просмотреть html-код искомого элемента. Нужная ссылка выглядит как-то вот так:

<a class=”b-link” …здесь всякий мусор… href=”http://russian.rt.com/article/68852″ target=”_blank”>Россия в 2015 году укрепит войска в Крыму, Калининграде и Арктике</a>

Указываем программе  границы парсинга:

начало:

<a class=”b-link”{skip}”href=”

конец:

” target=”_blank”>

({skip} – макрос позволяющий включить в границу все, что угодно до тех  пор пока не встретится последовательность символов, которая стоит после него)

Указываем “не включать границы” в парсинг (нам ведь нужна только ссылка а не html код)

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

Запускаем парсинг. В результате получаем огромный список ссылок на новости.

Но новости сами по себе нам не интересны, нам нужны ссылки на ресурсы.

в) Получение списка СМИ. Воспользуемся старым добрым Excel. Выгружаем список в таблицу. Удаляем все вхождения “http://”  и “www.” через ctrl+h. Далее пользуемся функцией “разделить по столбцам”. Разделителем будет слеш “/”. Удаляем все, кроме первого столбца. Мы почти у цели – осталось удалить дубли (новости то разные, но ресурсы могут быть одинаковыми). Выделяем столбец, жмем “удалить дубли” – готово!

У меня получилось более 2000 самых разных ресурсов.

 

Сбор ссылок на RSS-ленты этих ресурсов

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

По запросу “массовое определение ТИЦ” на первом же месте видим http://www.raskruty.ru/tools/cy/

То что надо! Делаем три подхода (больше 1000 url за раз нельзя) – копируем результат в новую табличку Excel, сортируем по убыванию значения ТИЦ. Есть!

А теперь, собственно, вопрос знатокам. Как, зная ссылку на ресурс, получить ссылку на его rss-ленту?

Казалось бы, что может быть проще? Ан, нет. Нет никакой закономерности в формате ссылок на rss у ресурсов. Более того страницы rss-лент не индексируются. Поэтому что-то вроде “inurl: site.ru rss” в поисковиках почти никогда не работает.

Оказалось, существует специальный поисковик RSS – http://ctrlq.org/rss/

Однако верную ссылку на RSS при указании запроса в виде site:thenextweb.com  показывает слишком редко.

Потом я вспомнил, что существует Яндекс Лента – она же rss-читалка от Яндекса. Проверив несколько топовых сайтов, я был в полном восторге – вбиваешь ссылку на сайт, получаешь ссылку на rss. Но покопавшись внимательней, обнаружил такие досаднейшие недочеты:

  1. Ссылки на rss часто устаревшие. При клике по такой ссылке, как правило, попадаешь на 404 страницу. А новости, которые показываются Яндексом с такого ресурса, могут датироваться даже 2006 годом.
  2. Для Яндекса сайт c www и без – два разных ресурса.
  3. Бывает не находит ссылку вовсе.

Смирившись с тяжкой судьбой, решил все же автоматизировать процесс поиска rss через яндекс-подписки. Ничего не получилось: проблема авторизации, https соединение и подгрузка rss-ссылки “на лету”. Признаюсь, пробовал даже автокликер, но все впустую.

Пришлось собирать ручками. Если не находил через Яндекс – искал вручную на сайте. В итоге собрал с приятелем около 500 ссылок. Потом решу, как добить остальное.

 

Настройка парсера RSS-лент и запись информации о статьях в базу данных

Я использовал php + mysql для решения задачи.

  1. “Верхний” цикл – обход rss-лент всех имеющихся ресурсов
  2. “Нижний” цикл – обход всех новостей с конкретного ресурса и выявление “свежих”.

Здесь стоит задача определения “свежести” новости. В базе данных заводится таблица “rssurls”, которая состоит из двух полей: rssurl и lastdate.

Для каждого ресурса в базе нужно при каждом обходе записывать дату последней замеченной на ресурсе статьи. Так при следующем обходе скрипт сравнивает дату конкретной статьи из RSS ленты с датой из базы и если время статьи “новее” – записывает статью в базу и обновляет дату последней публикации.

Для статей заводится отдельная таблица “articles”, куда в отдельные поля сохраняется следующая информация: id записи, rssurl, title, date, link, category, record (время записи в базу) и tags(об этом поле – в следующей части).

Title, date, link, category – парсятся из rss. RSS, кто не знает, представляет и себя обыкновенный XML-файл, а значит с ними наверняка легко работать встроенными функциями php. Так и оказалось – есть замечательная функция simplexml_load_file, которая позволяет легко получать необходимые элементы. Но у этой функции есть недостаток – она не предназначена для работы с внешними источниками. По хорошему нужно работать через cURL, но для начала и так сойдет. Около четверти ресурсов отказывались подгружаться через  simplexml_load_file, хотя ссылка в браузере открывалась.

Не смотря на то, что RSS довольно “строг”, формат данных очень часто отличался. Особенно все плохо с датами: кто указывает timezone, а кто нет, кто указывает дни недели, а кто нет  и т.д. Пришлось долго повозиться с регулярными выражениями, чтобы привести все нормальный вид.

 

Составление алгоритма определения тем новостей

Самый интересный и творческий этап. Наверняка можно было бы применить модные и сложные статистические алгоритмы кластеризации. Но мне хотелось попробовать провести анализ “вручную” и в целом – получилось неплохо.

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

Покопавшись в интернете я наткнулся на потрясающую библиотеку phpmorphy – http://phpmorphy.sourceforge.net/dokuwiki/

Библиотека среди прочего позволяет получать из любого слова на русском языке его базовую форму (по-научному процесс называется “лемматизация”). Это как раз то, что нам нужно!

Используя библиотеку, я написал функцию, которой на вход подается заголовок новости, а на выходе отдается строка из “нормированных” слов. Пример:

“Родители пропавших в Мексике студентов ворвались в казармы в Игуале” превращается в

“СТУДЕНТ РОДИТЕЛЬ ПРОПАСТЬ МЕКСИКА КАЗАРМА ВОРВАТЬСЯ ИГУАЛ”

(все вспомогательные знаки, кроме тире, игнорируются)

Дополняем функцию записи новости в таблицу articles, добавляя в поле tags строку с “нормированным” заголовком.

При первом же подсчете частот слов и их сортировке стало очевидно, что выбран верный путь. Стало ясно, что нужно добавить список стоп-слов, которые сами по себе не могут формировать новостную “тему”, но их частота упоминаний велика:

“НА”, “ЗА”, “ПО”, “ГОД”, “НЕ”, “БЫТЬ”, “ДО”, “ИЗ”, “ИЗА”, “ДЛЯ”, “ИЗ-ЗА”, “СТАТЬ”, “ЧТО”, “БОЛЕЕ”, “МОЧЬ”, “ПРИ”, и ряд других. Удаляем стоп-слова из нормированных заголовков.

Казалось бы после этого – все должно быть хорошо. Но часто попадаются “нормальные” слова, которые нельзя включить в стоп-лист, но которые точно не формируют “тему”.  Это объясняется тем, что одно и тоже слово встречается в заголовках, посвященных разным темам. Особенно часто это касается географических названий.

Встает вопрос как определять “ненастоящие” слова и убирать их из выборки? Интуиция подсказывает, что следует обратить внимание на следующие по популярности слова из заголовков, которые содержат проверяемое слово.

Пример распределения частот для “ненастоящих” слов “новый” и “СМИ”: 

  • 645 – НОВЫЙRplot
  • 44 – РОССИЯ
  • 29 – СТАРЫЙ
  • 28 – УКРАИНА
  • 24 – ДОНБАСС
  • 23 – НОМЕР

 

  • 387 – СМИ
  • 54 – РОССИЯ
  • 43 – РОССИЙСКИЙ
  • 35 – СИЛА
  • 29 – ВОЗДУШНО-КОСМИЧЕСКИЙ
  • 26 – РОСКОМНАДЗОР

 

А теперь “настоящие” слова “Нефть” и “Обстрел” 

  •  359 – НЕФТЬRplot02
  • 152 – ЦЕНА
  • 87 – БАРРЕЛЬ
  • 63 – НИЖЕ
  • 57 – ДОЛЛАР
  • 52 – УПАСТЬ

 

  • 279 – ОБСТРЕЛRplot03
  • 145 – АВТОБУС
  • 79 – ВОЛНОВАХА
  • 50 – ЧЕЛОВЕК
  • 46 – ОБСТРЕЛЯТЬ
  • 43 – ДОНБАСС

 

По форме “хвоста” можно определить “настоящесть” найденной темы.  О формулах – чуть ниже.

Еще была проблема дублирования одних и тех же “тем”. Я решил, что это из-за повторного учета слов. Будем считать, что новость не может быть посвящена разным темам одновременно. Если мы отнесли заголовок к определенной “настоящей” теме, то мы должны удалить ее из выборки, используемой для нахождения последующих тем.

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

Вернемся к “настоящести”. Я не стал особо изощряться с формулами. Считал среднее геометрическое для значений частот пяти слов из “хвоста” и делил на частоту исходного слова. Эмпирическим путем пришел к коэффициенту 0,17. Если коэффициент “настоящести” равен или выше этого значения, считаем тему “настоящей”.

При нахождении каждой отдельной “настоящей” новости в новую таблицу top записывается “измерение”: название темы, три ключевых слова, частота основного слова, дата начала периода измерения, дата конца периода измерения,  html-код трех ссылок на примеры статей по теме.

  1. Веб-интерфейс с топом всех новостей

Я настроил cron так, чтобы обход всех rss-лент и сбор новостей происходил раз в десять минут.

Сами “измерения” происходят за 6-часовой период раз в 6 часов (пока что). Позже, когда соберем больше ссылок на rss, сделаю периоды меньше а сами измерения чаще. (оптимальные параметры еще предстоит выяснить. Сам Яндекс обновляется раз в 20 минут)

В самом веб-интерфейсе вывожу данные за последний период, где “частоты” сравниваются со значением из предыдущего измерения:

6SXJiDY

 

Задача минимум выполнена. Надеюсь, работа была проделана не зря )