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

By | 2015-09-15

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

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

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

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

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

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

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

установка – завершение таска №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

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

 

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *