Петрова Е.А., Камынин В.Д.

Использование алгоритмов кластеризации в задачах персонализации

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

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

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

Анализ публикаций

Алгоритм кластеризации(Clustering algorithm) - это метод, благодаря которому данные разделяются и объединяются в небольшие группы (кластеры) по принципу аналогии. Используя разбиение на кластеры можно выявить в исследуемом массиве данных такие связи, которые невозможно обнаружить простым просмотром этих данных. Оценивая распределение данных в этих кластерах, можно лучше понять взаимосвязи различных характеристик исследуемых объектов, а также как эти взаимосвязи влияют на значение прогнозируемого атрибута.

В современной литературе описаны несколько методов кластеризации: алгоритм k-средних (k-means), нейросетевые архитектурыAРT, графовые алгоритмы кластеризации, статистические алгоритмы кластеризации, алгоритм ФОРЕЛЬ, иерархическая кластеризация или таксономия, нейронная сеть Кохонена, ансамбль кластеров.

Суть алгоритм k-средних (k-means) в том, что весь исходный набор примеров разбивается на k классов таким образом, что минимизируется евклидово расстояние между объектами внутри классов и максимизируется евклидово расстояние между классами [1].

Привлекательной особенностью нейронных сетей с адаптивным резонансом является то, что они сохраняют пластичность при запоминании новых образов, и, в то же время, предотвращают модификацию старой памяти. Нейросеть имеет внутренний детектор новизны – тест на сравнение предъявленного образа с содержимым памяти. При удачном поиске в памяти предъявленный образ классифицируется с одновременной уточняющей модификацией синаптических весов нейрона, выполнившего классификацию. О такой ситуации говорят, как о возникновении адаптивного резонанса в сети в ответ на предъявление образа. Если резонанс не возникает в пределах некоторого заданного порогового уровня, то успешным считается тест новизны, и образ воспринимается сетью, как новый. Модификация весов нейронов, не испытавших резонанса, при этом не производится [2,3].

Алгоритм функционирования самообучающихся карт (Self Organizing Maps – SOM) или карт Кохонена представляет собой один из вариантов кластеризации многомерных векторов. Примером таких алгоритмов может служить алгоритм k- средних (k -means). Важным отличием алгоритма SOM является то, что в нем все нейроны (узлы, центры классов…) упорядочены в некоторую структуру (обычно двумерную сетку). При этом в ходе обучения модифицируется не только нейрон-победитель, но и его соседи, но в меньшей степени. За счет этого SOM можно считать одним из методов проецирования многомерного пространства в пространство с более низкой размерностью. При использовании этого алгоритма вектора, схожие в исходном пространстве, оказываются рядом и на полученной карте [4].

Анализ работы Интернет-магазина представляет собой одно из важных направлений формирования программной среды для реализации механизма логического вывода при контроле поведения покупателя в различных условиях выбора товара. Методы и модели позволяют исследовать динамические процессы в условиях неопределенности и неполноты исходной информации. В данной работе основное внимание уделяется использованию адаптивной модели анализа и интерпретации информации и алгоритму интеллектуального анализа данных, который представляет собой механизм, создающий модель интеллектуального анализа данных. Для создания модели, алгоритм сначала анализирует набор данных, осуществляя поиск определенных закономерностей и трендов. Затем алгоритм использует результаты этого анализа для определения параметров модели интеллектуального анализа данных.

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

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

Персонализация

Существует следующие подходы к осуществлению персонализации [5]:

1. Системы, основанные на совокупности правил. Для таких систем правила принятия решений закладываются при их разработке, а информация о пользователе, которая используется при выполнении правил – это информация об общих характеристиках пользователя. Правила системы выполняются в случае реализации заложенных в них условий.

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

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

В данной работе для выполнения кластеризации поведения покупателя в различных условиях выбора товара используются модели адаптивной резонансной теории (ART) [2] и карты Кохонена [4].

Персонализация с использованием алгоритма ART1

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

Алгоритм ART1 работает с объектами, которые называются векторами признаков (Feature vector). Вектор признаков является группой значений в двоичном коде, которые представляют определенный тип информации. Примером вектора признаков в данной работе служить выбор покупок. Каждый объект вектора признаков показывает, приобрел ли покупатель товар (если да, то значение равно 1, если нет – 0).

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

Допустим имеются группы векторов-признаков (назовем эти примеры Е, к) и группа инициализированных векторов-прототипов(Prototype vector). Вектор-прототип является центром кластера. Количество векторов-прототипов, равное N, является максимальным количеством кластеров, которое может поддерживаться. Параметр d показывает длину вектора. Мы инициализируем параметр внимательности(rho), равный небольшому значению между 0 и 1,0, а также бета-параметр (В), равный небольшому положительному целому числу.

Изначально не существует ни одного вектора-прототипа, поэтому при выполнении алгоритма создается первый вектор-прототип из первого вектора-признаков:

(1)

Затем проверяются на схожесть все последующие векторы признаков с вектором-прототипом. Цель проверки – выяснить, насколько схож вектор признаков и текущий вектор-прототип.

Бета-параметр () – это параметр «разрушения связи», который используется в уравнении проверки на схожесть:

(2)

и выбирает прототипы, в которых больше значений 1, при условии, что все значения 1 в векторе-прототипе также присутствуют в тестируемом векторе признаков.

Если тест на схожесть прошел успешно, выполняется следующий тест, чтобы проверить вектор признаков и вектор-прототип против параметра внимательности:

(3)

Задачей данного параметра является определение размера класса. Если значение параметра велико, образуются более крупные классы (кластеры с большим количеством данных). При уменьшении значения создаются кластеры с меньшим количеством данных.

Если пройден тест на внимательность, алгоритм добавляет текущий вектор признаков в текущий вектор-прототип:

(4)

Этот процесс представляет собой простое слияние вектора признаков и вектора-прототипа с помощью операции И. Если тест на внимательность не был пройден, проверяется следующий вектор-прототип. Если все векторы-прототипы были проверены и при этом вектор признаков не был помещен в кластер, создается новый вектор-прототип из вектора признаков. Это приводит к формированию нового кластера, так как рассматриваемый вектор признаков не соответствует ни одному существующему кластеру. Далее алгоритм проходит через все векторы признаков и сравнивает их со всеми векторами-прототипами. Хотя все векторы уже размещены по кластерам, проверка необходима. Она позволяет убедиться в том, что векторы расположены в нужных кластерах. Дело в том, что последующие тесты векторов признаков могли создать новые кластеры, поэтому необходимо выполнить дополнительную проверку и удостовериться, что векторы не нужно перемещать в другие кластеры.

После проверки всех векторов признаков, которая не потребовала дополнительных изменений, процесс формирования кластеров можно считать завершенным. Чтобы избежать перемещения вектора признаков между двумя векторами-прототипами, алгоритм выполняет несколько итераций, чтобы объединить кластеры. Количество итераций должно быть достаточно большим, чтобы избежать преждевременного слияния.

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

Вектор признаков имеет вид:

и параметры алгоритма имеют следующие значения: .

Для определения в какой кластер будет помещен вектор-признаков выполняются тесты алгоритма ART1:

1. Тест на сходство:

(Нет)

(Да)

2. Тест на внимательность:

(Да)

3. Добавление текущего вектора признаков в текущий вектор-прототип:

В первом тесте была выполнена проверка на схожесть для вектора-прототипа . Используя уравнение 2, было определено, что тест завершился неудачно (0,2 не больше чем 0,5). Затем вектор признаков был проверен против вектора , результат также оказался отрицательным. После чего был проверен вектор . В этом случае тест завершился успешно, поэтому алгоритм выполняет тест на внимательность. Данный тест также завершился успешно, поэтому вектор признаков ассоциируется с кластером, который представлен вектором . Затем вектор-прототип изменяется путем выполнения операции побитового И между вектором-прототипом и вектором признаков. После обновления вектора-прототипа все векторы признаков проверяются против всех доступных векторов-прототипов: следует убедиться, что они находятся в нужных кластерах. После завершения изменений процесс заканчивается.

Персонализация с использованием алгоритма ART1 состоит из двух этапов. Сначала выполняется стандартный алгоритм ART1 для векторов признаков (данных о покупателях). Далее, чтобы получить рекомендацию, анализируется вектор признаков (отображающий покупателя, которому нужно дать рекомендацию), а также новый элемент, так называемый вектор суммирования (Sum vector). Вектор суммирования, который не входит собственно в алгоритм ART1, представляет собой сумму столбцов векторов- признаков в кластере (рис. 2).

Рисунок 2 – Рекомендация товара покупателю Интернет-магазина с использованием вектора признаков и вектора суммирования

Рассмотрим процесс выдачи рекомендации на примере. Предположим, что покупатель, которому мы должны дать рекомендацию, представлен вектором признакови. Содержимое вектора признаков соответствует примеру на рис. 1 (истории покупок клиента). Сначала по вектору суммирования необходимо определить, какие товары (столбцы) представлены в кластере (то есть не равны 0). Затем алгоритм находит самое большое значение в векторе суммирования, которое соответствует объекту в векторе признаков покупателя со значением 0. Это значение представляет товар, неприобретенный покупателем, но популярный для кластера. Такая информация является основой для рекомендации. Предположение (или статистическое предвидение) заключается в следующем: 66% покупателей в кластере уже приобрели этот товар (в примере товар с номером три), значит, высока вероятность того, что данный клиент тоже пожелает его купить.

Карты Коханена в задачах персонализации

Самоорганизующиеся карты (Self Organizing Maps – SOM), или карты Кохонена используются для решения задач кластеризации и сегментирования и являются одним из методов интеллектуального анализа данных.

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

где – функция соседства, определяющая величину корректировки веса нейрона,

– вес і-го нейрона,

– скорость обучения.

Для нейрона-победителя функция соседства равна 1 и затем плавно (по линейному или экспоненциальному закону) уменьшается при удалении от него. Таким образом, в процессе обучения подстройка весов происходит не только в одном нейроне–нейроне-победителе, но и в его окрестностях.

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

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

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

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

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

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

Выводы

Персонализация – новое направление в развитии информационных систем, актуальность которого растет с каждым днем.

Для решения задачи персонализации в данной работе были использованы методы искусственного интеллекта. Для определения в какой из трех кластеров, представленных векторами-прототипами (у М. Т. Джонса рассмотрены два кластера) будет помещен вектор-признаков, была рассмотрена работа алгоритма ART1 с выполнением тестов на сходство и на внимательность. Также авторами определен вектор суммирования, который позволил сформулировать рекомендации покупателю при покупке им определенного товара в Интернет-магазине.

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

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

Литература

1. J. B. MacQueenSome Methods for classification and Analysis of Multivariate Observations, Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability - Berkeley, University of California Press, 1967 – pp. 281-297

2. Джонс М. Т.Программирование искусственного интеллекта в приложениях - М.: ДМК Пресс, 2004. – 312 с.

3. Carpenter G. A., Grossberg S.Pattern Recognition by SelfOrganizing Neural Networks - MIT Press, Cambridge, Mass., 1991 – 678 p.

4. T. KohonenSelf-Organizing Maps - 3. ed. - New York: Springer, 2001 – 501 p.

5. B. Mobasher, S. S. AnandIntelligent Techniques for Web Personalization - Verlag Berlin Heidelberg: Springer, 2005 – pp. 9-12