Размещено на http://www.allbest.ru/

Разработка интеллектуальной системы подбора товара

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ И ПОСТАНОВКА ЗАДАЧИ

1.1 Задача разработки интеллектуальных систем подбора товаров

1.2 Анализ ассортимента компании

1.3 Постановка задачи

2. ИНТЕЛЛЕКТУАЛЬНЫЙ АНАЛИЗ ДАННЫХ

2.1 Задача поиска ассоциативных правил

2.2 Характеристики ассоциативных правил

2.3 Методы поиска ассоциативных правил

2.3.1 Алгоритм AIS

2.3.2 Алгоритм SETM

2.4 Применение ассоциативных правил

3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ СИСТЕМЫ

3.1 Требования к программному обеспечению

3.2 Тестирование программного обеспечения и полученные результаты

3.3 Пример оформления заказа

ВЫВОДЫ

ПЕРЕЧЕНЬ ССЫЛОК

ПРИЛОЖЕНИЕ

ВВЕДЕНИЕ

В любом бизнесе имеются данные, что в свою очередь требует создания некоторого организованного метода или механизма управления этими данными. Такой механизм принято называть системой управления базами данных (СУБД). Системы управления базами данных используются уже много лет. Основываясь на современных технологиях, доказавшие свою пользу системы управления базами данных начали развиваться в других направлениях, отвечая требованиям растущего бизнеса, все возрастающих объемов корпоративных данных [1-2].

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

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

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

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

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

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

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

1. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ И ПОСТАНОВКА ЗАДАЧИ

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

Данная система позволяет человеку выбрать продукт, а также существует возможность рекомендации дополнительных товаров. В программе достаточно удобный и простой интерфейс, позволяющий пользователям успешно совершать покупки. Система рассчитана на то, что человек не определился с тем продуктом который он хочет заказать. Для этого были введены вопросы, позволяющие определить интересы пользователя. Ответив на вопросы пользователь определяет что является для него приоритетным и на основании этих данных формирует заказ. Заказ у клиента может состоять из большого количества продуктов. Доведенный заказ формирует транзакцию. В свою очередь транзакция с данными о покупке, о дате и времени сохраняется в списке транзакций, где в дальнейшем можно просмотреть все совершенные операции с товаром [1-2].

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

1.1 ЗАДАЧА РАЗРАБОТКИ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ ПОДБОРА ТОВАРОВ

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

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

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

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

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

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

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

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

Можно назвать целый ряд причин, которые заставляют нас обращаться к персонализации в Интернете [4-5]:

а) Персонализация дает возможность более точно ориентироваться на клиента.

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

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

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

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

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

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

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

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

Такая персонализация требует использования сложных платформ eCommerce, которые поддерживают указанную персонализацию продуктов и должны быть логически связаны с системами корпоративного управления компании. Эти платформы также поддерживают все предыдущие модели персонализации, о которых говорили ранее. Этот тип платформ поможет нам значительно продвинуться на пути построения отношений с нашими клиентами, позволит сделать продукт более привлекательным для потребителей [3-5].

Таким образом, все модели персонализации помогают в реализации глобальной стратегии ориентации на клиента.

Рассмотрим задачу персонализации на примере компании Amazon - как в компании проводится персонализация, распознается пользователь.

Для распознавания пользователя и персонализации компания Amazon использует анализ «cookie-файлов» [3-5].

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

Передача данных cookie происходит следующим образом:

а) При вводе адреса URL сайта в адресной строке, браузер отправляет сайту запрос на веб-страницу, если ввести адрес http://www.amazon.com, браузер запросит у сервера Amazon главную страницу сайта.

б) Отправляя запрос, браузер проверяет, сохранен ли на локальном жестком диске файл cookie для Amazon. Если такой файл есть, браузер отправляет серверу сохраненные в нем пары «имя - значение» вместе с адресом URL. Если файла cookie нет, браузер отправляет только адрес.

в) Веб-сервер Amazon получает запрос на страницу и данные cookie, которые он может использовать для идентификации пользователя.

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

д) Веб-сервер может изменять пары «имя - значение» или добавлять новые при каждом посещении сайта.

Помимо пар «имя - значение», сервер может включать в файлы cookie и другие данные - например, срок их действия или пути, позволяющие связать определенные значения cookie с разными разделами сайта.

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

В данной бакалаврской работе предлагается рассмотреть задачу интеллектуального подбора товаров (персонализации) косметической компании. Далее приводится анализ ассортимента продукции данной компании.

1.2 АНАЛИЗ АССОРТИМЕНТА КОМПАНИИ

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

1)Уход за кожей лица:

а) для мужчин:

- средства для бритья представлены гелем для бритья для нормальной кожи Eclat и пеной для бритья для нормальной кожи;

- другое: мужской бальзам для век, мужской увлажняющий крем;

- средства после бритья - парфюмированный бальзам после бритья, увлажняющий бальзам после бритья.

б) ежедневный уход:

- дневной крем ? дневной крем, интенсивный увлажняющий крем;

- крем для глаз - омолаживающий крем для век, смягчающий крем для век;

- ночной крем - ночной крем глубокого увлажнения, ночной крем-антиоксидант серии «Виноград».

в) специальный уход:

- маски для лица: восстанавливающая маска для лица, отшелушивающая маска;

- cкрабы для лица - скраб для лица серии «Виноград», очищающий скраб серии «Natural Balance».

2) Декоративная косметика:

а) косметика для глаз:

- карандаш для глаз - контурный карандаш для глаз;

- подводка - жидкая подводка, подводка- карандаш;

- тушь ? водостойкая, разделяющая тушь.

б) косметика для губ:

- блеск для губ - защитный блеск, ароматный блеск;

- карандаш для губ - карандаш для губ «Идеальный», контурный карандаш;

- помада - губная помада, помада - стимулятор объема.

в) декоративная косметика для лица:

- пудра - рассыпчатая пудра, компактная пудра;

- румяна - двойные румяна;

- тональная основа - матирующая тональная основа, тональная основа против следов усталости.

3) Косметика для ногтей:

- лак - быстросохнущий, лак для ногтей с двойной кисточкой.

4) Ароматы:

а) для женщин:

- бодрящие - «Embrace Her», туалетная вода «Midsummer»;

- восточные - парфюмерная вода «Petal Quartz», туалетная вода «Fire».

б) для мужчин:

- восточные ? туалетная вода «Eclat», туалетная вода «De Marco»;

- древесные - туалетная вода «Signature», туалетная вода «Soul».

5) Уход за кожей тела:

а) гели для душа: бодрящий гель для душа «Лайм и имбирь», восстанавливающий гель для душа;

б) скрабы для тела: крем ? скраб, сахарный скраб для тела «Мед и молоко»;

в) мыло: жидкое мыло для рук «Мед и молоко», мыло «Лайм и имбирь», крем-мыло «Молоко и мед»;

г) уход за руками - антибактериальный гель для рук, защитный крем для рук и ногтей;

д) уход за ногами - бальзам снимающий тяжесть в ногах, крем антиперспирант, тальк для ног.

6) Уход за волосами:

а) шампуни: защитный шампунь для окрашенных волос, шампунь против перхоти, шампунь для увеличения объема;

б) инструменты для укладки волос ? лак для волос длительной фиксации, моделирующий гель для волос, моделирующий мусс для создания объема.

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

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

1.3 ПОСТАНОВКА ЗАДАЧИ

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

Основные задачи бакалаврской работы:

- анализ основных методов создания систем интеллектуального подбора товаров;

- анализ теории ассоциативных правил как средство реализации систем поддержки принятия решений в выборе товара;

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

Разработанная система при заданном запросе должна подбирать клиенту необходимый продукт и предлагать дополнительные товары в зависимости от интересов. Для этого клиент должен описать критерии, по которым система определит потребности. Система должна быть реализована с помощью Python 2.6 и My SQL SERVER.

2. Интеллектуальный анализ данных

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

Английский термин «Data Mining» не имеет однозначного перевода на русский язык (добыча данных, вскрытие данных, информационная проходка, извлечение данных/информации) поэтому в большинстве случаев используется в оригинале. Наиболее удачным непрямым переводом считается термин «интеллектуальный анализ данных» (ИАД) [6-9].

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

Существуют разные способы получения информации о предметной области:

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

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

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

Изначально в системах вывода по прецедентам в качестве источников фонового знания выступали эксперты - высококвалифицированные специалисты предметных областей, а также текстовые материалы - от учебников до протоколов, и, разумеется, базы данных (имплицитные источники знаний). Роль эксперта (затратная по ресурсам и времени) заключалась в вербализации, то есть переводе таких источников в эксплицитную форму. Учитывая, что важнейшей задачей в процессе формализации извлечения знаний является минимизация роли эксперта, его роль должны взять на себя средства добычи данных [6-9].

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

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

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

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

Машинное обучение предполагает использование различных методов, например: деревьев решений; ассоциативных правил; генетических алгоритмов; нейронных сетей.

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

В табл. 2.1. приведено краткое описание основных алгоритмов Data Mining. Каждый из методов имеет свои преимущества и недостатки [8-9].

Преимущество деревьев решений и ассоциативных правил состоит в их читабельности - они похожи на предложения на естественном языке. Однако при большом количестве факторов данных бывает очень сложно понять смысл такого представления. Недостаток: они не предназначены для широких числовых интервалов. Это связано с тем, что каждое правило или узел в дереве решений представляет одну связь (зависимость, отношение). Чтобы представить зависимости для большого интервала значений потребуется слишком много правил или узлов.

Преимущество нейронных сетей в компактном представлении числовых отношений для широкого диапазона значений. А недостаток - в сложности интерпретации.

Таблица 2.1 - Основные алгоритмы Data Mining

Алгоритм	Описание
Ассоциативные правила	Выявляют причинно следственные связи и определяют вероятности или коэффициенты достоверности, позволяя делать соответствующие выводы. Правила представлены в форме «если <условия>, то <вывод>». Их можно использовать для прогнозирования или оценки неизвестных параметров (значений).
Деревья решений и алгоритмы классификации	Определяют естественные «разбивки» в данных, основанные на целевых переменных. Сначала выполняется разбивка по наиболее важным переменным. Ветвь дерева можно представить как условную часть правила. Наиболее часто встречающимися примерами являются алгоритмы классификационных и регрессионных деревьев (Classification and regression trees, CART) либо хи-квадрат индукция (Chi-squared Automatic Induction, CHAID).
Искусственные нейронные сети	Здесь для предсказания значения целевого показателя используется наборы входных переменных, математических функций активации и весовых коэффициентов входных параметров. Выполняется итеративный обучающий цикл, нейронная сеть модифицирует весовые коэффициенты до тех пор, пока предсказываемый выходной параметр соответствует действительному значению. После обучения нейронная сеть становится моделью, которую можно применить к новым данным с целью прогнозирования.
Генетические алгоритмы	Этот метод использует итеративный процесс эволюции последовательности поколений моделей, включающий операции отбора, мутации и скрещивания. Для отбора определенных особей и отклонения других используется «функция приспособленности» (fitness function). Генетические алгоритмы в первую очередь применяются для оптимизации топологии нейронных
Генетические алгоритмы	сетей и весов. Однако, их можно использовать и самостоятельно, для моделирования.
Кластерный анализ	Подразделяет гетерогенные данные на гомогенные или полугомогенные группы. Метод позволяет классифицировать наблюдения по ряду общих признаков. Кластеризация расширяет возможности прогнозирования.
Вывод путем сопоставления (Memory-Based Reasoning, Mbr) или вывод, основанный на прецедентах (Case-Based Reasoning, Cbr)	Эти алгоритмы основаны на обнаружении некоторых аналогий в прошлом, наиболее близких к текущей ситуации, с тем, чтобы оценить неизвестное значение или предсказать возможные результаты (последствия).

Существует широкий спектр инструментов для поддержки проектов Data Mining. К ним относятся как общедоступные алгоритмы визуализации и машинного обучения, так и сложные программные пакеты, где используются обе стратегии, работающие на параллельных процессорах. Стоимость последних может достигать нескольких сотен тысяч долларов. Поиск наилучшего инструмента для Data Mining решения зависит от ряда условий, таких как цель проекта (например, анализ потребительской корзины) и размер исследуемой базы данных. При выборе инструментов и алгоритмов очень важна гибкость, поскольку в зависимости от выбора стратегии может быть получен разный результат [8-9].

Для анализа природной среды в настоящее время широко применяются методы, получившие в литературе название интеллектуального анализа данных (ИАД), этому русскому понятию соответствуют английские термины Data Mining (добыча данных), On line Analytical Processing, OLAP (оперативный анализ данных), Knowledge Discovery (обнаружение знаний) или Intelligent Analysis Data (разведывательный анализ данных). Термин ИАД кажется несколько рекламным. Методы ИАД едва ли более «интеллектуальны», чем методы, применяющиеся в других разделах программного обеспечения, но поскольку термин устоялся, будем его использовать. В табл. 2.1. приведено краткое описание основных алгоритмов Data Mining [8-9].

2.1 ЗАДАЧА ПОИСКА АССОЦИАТИВНЫХ ПРАВИЛ

Ассоциация - это одна из задач Data Mining. Целью поиска ассоциативных правил (association rule) является нахождение закономерностей между связанными событиями в базах данных [10-16].

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

Часто встречающиеся приложения с применением ассоциативных правил:

а) розничная торговля: определение товаров, которые стоит продвигать совместно; выбор местоположения товара в магазине; анализ потребительской корзины; прогнозирование спроса;

б) перекрестные продажи: если есть информация о том, что клиенты приобрели продукты A, Б и В, то какие из них вероятнее всего купят продукт Г?

в) маркетинг: поиск рыночных сегментов, тенденций покупательского поведения;

г) сегментация клиентов: выявление общих характеристик клиентов компании, выявление групп покупателей;

д) оформление каталогов, анализ сбытовых кампаний фирмы, определение последовательностей покупок клиентов (какая покупка последует за покупкой товара А);

е) анализ Web-логов.

Простой пример ассоциативного правила: покупатель, приобретающий шампунь для волос, приобретет кондиционер для волос с вероятностью 50%.

Впервые задача поиска ассоциативных правил (association rule mining) была предложена для нахождения типичных шаблонов покупок, совершаемых в супермаркетах, поэтому иногда ее еще называют анализом рыночной корзины (market basket analysis) [10-12].

Рыночная корзина ? это набор товаров, приобретенных покупателем в рамках одной отдельно взятой транзакции.

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

Транзакция ? это множество событий, которые произошли одновременно.

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

Полученные в результате анализа шаблоны включают перечень товаров и число транзакций, которые содержат данные наборы.

Транзакционная или операционная база данных (Transaction database) представляет собой двумерную таблицу, которая состоит из номера транзакции (TID) и перечня покупок, приобретенных во время этой транзакции.

TID ? уникальный идентификатор, определяющий каждую сделку или транзакцию.

Пример транзакционной базы данных, состоящей из покупательских транзакций, приведен в таблице 2.2. В таблице первая колонка (TID) определяет номер транзакции, во второй колонке таблицы приведены товары, приобретенные во время определенной транзакции [10-13].

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

Таблица 2.2 - Транзакционная база данных TID

TID	Приобретенные покупки
1	Пена для бритья, гель для душа, бальзам после бритья
2	Гель для душа, мыло
3	Гель для душа, пена для бритья, мыло, бальзам после бритья
4	Духи, мыло
5	Пена для бритья, гель для душа, бальзам после бритья, мыло
6	Крем для тела

2.2 ХАРАКТЕРИСТИКИ АССОЦИАТИВНЫХ ПРАВИЛ

Ассоциативное правило имеет вид: «Из события A следует событие B».

В результате такого видеоанализа устанавливаем закономерность следующего вида: «Если в транзакции встретился набор товаров (или набор элементов) A, то можно сделать вывод, что в этой же транзакции должен появиться набор элементов B)» Установление таких закономерностей дает нам возможность находить очень простые и понятные правила, называемые ассоциативными [13-15].

Основными характеристиками ассоциативного правила являются поддержка и достоверность правила.

Рассмотрим правило «из покупки геля для душа следует покупка мыла» для базы данных, которая была приведена выше в таблице 2.2. Понятие поддержки набора уже рассмотрели. Существует понятие поддержки правила.

Правило имеет поддержку s, если s% транзакций из всего набора содержат одновременно наборы элементов A и B или, другими словами, содержат оба товара.

Гель для душа - это товар A, мыло ? это товар B. Поддержка правила «из покупки геля для душа следует покупка мыла» равна 3, или 50%.

Достоверность правила показывает, какова вероятность того, что из события A следует событие B.

Правило «Из A следует B» справедливо с достоверностью с, если c% транзакций из всего множества, содержащих набор элементов A, также содержат набор элементов B. Число транзакций, содержащих гель для душа, равно четырем, число транзакций, содержащих мыло, равно трем, достоверность правила равна (3/4)*100%, т.е. 75%.

Достоверность правила «из покупки геля для душа следует покупка мыла» равна 75%, т.е. 75% транзакций, содержащих товар А, также содержат товар B [13-15].

Рассмотрим границы поддержки и достоверности ассоциативного правила. При помощи использования алгоритмов поиска ассоциативных правил аналитик может получить все возможные правила вида «Из A следует B», с различными значениями поддержки и достоверности. Однако в большинстве случаев, количество правил необходимо ограничивать заранее установленными минимальными и максимальными значениями поддержки и достоверности.

Если значение поддержки правила слишком велико, то в результате работы алгоритма будут найдены правила очевидные и хорошо известные. Слишком низкое значение поддержки приведет к нахождению очень большого количества правил, которые, возможно, будут в большей части необоснованными, но не известными и не очевидными для аналитика. Таким образом, необходимо определить такой интервал, «золотую середину», который с одной стороны обеспечит нахождение неочевидных правил, а с другой - их обоснованность [14-16].

Если уровень достоверности слишком мал, то ценность правила вызывает серьезные сомнения. Например, правило с достоверностью в 3% только условно можно назвать правилом.

2.3 МЕТОДЫ ПОИСКА АССОЦИАТИВНЫХ ПРАВИЛ

На сегодняшний день существует большое количество методов поиска ассоциативных правил в разных источниках данных. Основными являются методы AIS и SETM. Рассмотрим более подробно каждый из этих методов.

2.3.1 АЛГОРИТМ AIS

Первый алгоритм поиска ассоциативных правил, называвшийся AIS, (предложенный Agrawal, Imielinski and Swami) был разработан сотрудниками исследовательского центра IBM Almaden в 1993 году. С этой работы начался интерес к ассоциативным правилам; на середину 90-х годов прошлого века пришелся пик исследовательских работ в этой области, и с тех пор каждый год появляется несколько новых алгоритмов [14-16].

В алгоритме AIS кандидаты множества наборов генерируются и подсчитываются «на лету», во время сканирования базы данных. Каждая транзакция проверяется на наличие больших наборов, выявленных при предыдущем проходе. Соответственно, новые наборы формируются путем расширения имеющихся наборов. Этот алгоритм неэффективен, поскольку генерирует и учитывает слишком много наборов-кандидатов, которые недостаточно большие (нечастые).

2.3.2 АЛГОРИТМ SETM

Создание этого алгоритма было мотивировано желанием использовать язык SQL для вычисления часто встречающихся наборов товаров. Как и алгоритм AIS, SETM также формирует кандидатов «на лету», основываясь на преобразованиях базы данных. Чтобы использовать стандартную операцию объединения языка SQL для формирования кандидата, SETM отделяет формирование кандидата от их подсчета [14-16].

Неудобство алгоритмов AIS и SETM ? излишнее генерирование и подсчет слишком многих кандидатов, которые в результате не оказываются часто встречающимися. Для улучшения их работы был предложен алгоритм Apriori.

Работа данного алгоритма состоит из нескольких этапов, каждый из этапов состоит из следующих шагов:

а) формирование кандидатов;

б) подсчет кандидатов.

Формирование кандидатов (candidate generation) ? этап, на котором алгоритм, сканируя базу данных, создает множество i-элементных кандидатов (i - номер этапа). На этом этапе поддержка кандидатов не рассчитывается.

Подсчет кандидатов (candidate counting) ? этап, на котором вычисляется поддержка каждого i-элементного кандидата. Здесь же осуществляется отсечение кандидатов, поддержка которых меньше минимума, установленного пользователем (min_sup). Оставшиеся i-элементные наборы называем часто встречающимися.

Рассмотрим работу алгоритма Apriori на примере базы данных D. Иллюстрация работы алгоритма приведена на рисунке 2.1. Минимальный уровень поддержки равен 3.

Рисунок 2.1 - Алгоритм Apriori

На первом этапе происходит формирование одноэлементных кандидатов. Далее алгоритм подсчитывает поддержку одноэлементных наборов. Наборы с уровнем поддержки меньше установленного, то есть 3, отсекаются. В нашем примере это наборы e и f, которые имеют поддержку, равную 1. Оставшиеся наборы товаров считаются часто встречающимися одноэлементными наборами товаров: это наборы a, b, c, d.

Далее происходит формирование двухэлементных кандидатов, подсчет их поддержки и отсечение наборов с уровнем поддержки, меньшим 3. Оставшиеся двухэлементные наборы товаров, считающиеся часто встречающимися двухэлементными наборами ab, ac, bd, принимают участие в дальнейшей работе алгоритма.

Если смотреть на работу алгоритма прямолинейно, на последнем этапе алгоритм формирует трехэлементные наборы товаров: abc, abd, bcd, acd, подсчитывает их поддержку и отсекает наборы с уровнем поддержки, меньшим 3. Набор товаров abc может быть назван часто встречающимся.

Однако алгоритм Apriori уменьшает количество кандидатов, отсекая - априори ? тех, которые заведомо не могут стать часто встречающимися, на основе информации об отсеченных кандидатах на предыдущих этапах работы алгоритма [14-16].

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

Так наборы товаров ad, bc, cd были отброшены как нечасто встречающиеся, алгоритм не рассматривал товаров abd, bcd, acd.

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

Алгоритм Apriori рассчитывает также поддержку наборов, которые не могут быть отсечены априори. Это так называемая негативная область (negative border), к ней принадлежат наборы-кандидаты, которые встречаются редко, их самих нельзя отнести к часто встречающимся, но все подмножества данных наборов являются часто встречающимися.

В зависимости от размера самого длинного часто встречающегося набора алгоритм Apriori сканирует базу данных определенное количество раз. Разновидности алгоритма Apriori, являющиеся его оптимизацией, предложены для сокращения количества сканирований базы данных, количества наборов-кандидатов или того и другого. Были предложены следующие разновидности алгоритма Apriori: AprioriTID и AprioriHybrid [14-16].

а) AprioriTid.

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

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

б) AprioriHybrid.

Анализ времени работы алгоритмов Apriori и AprioriTid показывает, что в более ранних проходах Apriori добивается большего успеха, чем AprioriTid; однако AprioriTid работает лучше Apriori в более поздних проходах. Кроме того, они используют одну и ту же процедуру формирования наборов-кандидатов. Основанный на этом наблюдении, алгоритм AprioriHybrid предложен, чтобы объединить лучшие свойства алгоритмов Apriori и AprioriTid. AprioriHybrid использует алгоритм Apriori в начальных проходах и переходит к алгоритму AprioriTid, когда ожидается, что закодированный набор первоначального множества в конце прохода будет соответствовать возможностям памяти. Однако, переключение от Apriori до AprioriTid требует вовлечения дополнительных ресурсов.

Некоторыми авторами были предложены другие алгоритмы поиска ассоциативных правил, целью которых также было усовершенствование алгоритма Apriori. Кратко изложим суть нескольких, для более подробной информации можно рекомендовать [14-16].

Один из них ? алгоритм DHP, также называемый алгоритмом хеширования. В основе его работы ? вероятностный подсчет наборов-кандидатов, осуществляемый для сокращения числа подсчитываемых кандидатов на каждом этапе выполнения алгоритма Apriori. Сокращение обеспечивается за счет того, что каждый из k-элементных наборов-кандидатов помимо шага сокращения проходит шаг хеширования. В алгоритме на k-1 этапе во время выбора кандидата создается так называемая хеш-таблица. Каждая запись хеш-таблицы является счетчиком всех поддержек k-элементных наборов, которые соответствуют этой записи в хеш-таблице. Алгоритм использует эту информацию на этапе k для сокращения множества k-элементных наборов-кандидатов. После сокращения подмножества, как это происходит в Apriori, алгоритм может удалить набор-кандидат, если его значение в хеш-таблице меньше порогового значения, установленного для обеспечения [14-16].

К другим усовершенствованным алгоритмам относятся: PARTITION, DIC, алгоритм «выборочного анализа».

PARTITION алгоритм. Этот алгоритм разбиения (разделения) заключается в сканировании транзакционной базы данных путем разделения ее на непересекающиеся разделы, каждый из которых может уместиться в оперативной памяти. На первом шаге в каждом из разделов при помощи алгоритма Apriori определяются «локальные» часто встречающиеся наборы данных. На втором подсчитывается поддержка каждого такого набора относительно всей базы данных. Таким образом, на втором этапе определяется множество всех потенциально встречающихся наборов данных.

Алгоритм DIC, Dynamic Itemset Counting. Алгоритм разбивает базу данных на несколько блоков, каждый из которых отмечается так называемыми «начальными точками» (start point), и затем циклически сканирует базу данных.

2.4 ПРИМЕНЕНИЕ АССОЦИАТИВНЫХ ПРАВИЛ

Для реализации данного бакалаврского проекта был выбран метод Apripri.

Допустим, имеется транзакционная база данных D. Присвоим значениям товаров переменные (табл. 2.3) [10-17].

Таблица 2.3 - Транзакционная база данных TID

TID	Приобретенные покупки
1	Пена для бритья, гель для душа, бальзам после бритья
2	Гель для душа, мыло
3	Гель для душа, пена для бритья, мыло, бальзам после бритья
4	Духи, мыло
5	Пена для бритья, гель для душа, бальзам после бритья, мыло
6	Крем для тела

Пена для бритья = a; Гель для душа = b; Бальзам после бритья = c;

Мыло = d; Духи = e; Крем для тела = f;

Рассмотрим набор товаров (Itemset), включающий, например, {пена для бритья, гель для душа, бальзам после бритья}. Выразим этот набор с помощью переменных, получаем: abc={a,b,c}

В ассоциативных правилах существует понятие поддержки. Это набор товаров встречается в разработанной базе данных три раза, т.е. поддержка этого набора товаров равна 3: SUP(abc)=3. При минимальном уровне поддержки, равной трем, набор товаров abc является часто встречающимся шаблоном. В таблице 2.4 приведены часто встречающиеся товары.

При минимальном уровне поддержки, равной трем, набор товаров abc является часто встречающимся шаблоном. min_sup=3, {Пена для бритья, гель для душа, бальзам после бритья} ? часто встречающийся шаблон [10-17].

Поддержкой называют количество или процент транзакций, содержащих определенный набор данных.

Для данного набора товаров поддержка, выраженная в процентном отношении, равна 50%. SUP(abc)=(3/6)*100%=50%

Поддержку иногда также называют обеспечением набора. Таким образом, набор представляет интерес, если его поддержка выше определенного пользователем минимального значения (min support). Эти наборы называют часто встречающимися (frequent).

В ассоциативных правилах также существует понятие достоверности. Правило «Из A следует B» справедливо с достоверностью С, если c% транзакций из всего множества, содержащих набор элементов A, также содержат набор элементов B.

Число транзакций, содержащих мыло, равно четырем, число транзакций, содержащих пену для бритья, равно трем, достоверность правила равна (3/4)*100%, т.е. 75%.

Достоверность правила «Из покупки мыла следует покупка пены для бритья» равна 75%, т.е. 75% транзакций, содержащих товар А, также содержат товар B.

Таблица 2.4 - Часто встречающиеся наборы товаров

TID	Приобретенные покупки		TID	Приобр. покупки
1	Пена для бритья, гель для душа, бальзам после бритья		100	a, b, c
2	Гель для душа, мыло		200	b, d
3	Гель для душа, пена для бритья, мыло, бальзам после бритья		300	b, a, d, c
4	Духи, мыло		400	e, d
5	Пена для бритья, гель для душа, бальзам после бритья, мыло		500	a, b, c, d
6	Крем для тела		600	f

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

3. Программная реализация системы

3.1 ТРЕБОВАНИЯ К ПРОГРАММНОМУ ОБЕСПЕЧЕНИЮ

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

Для работы программы требуется:

- операционная система Windows 98/2000/XP;

- установленная среда Python 2.6;

- установленный SQL Server 2005.

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

3.2 ТЕСТИРОВАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ И ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ

Главная форма программы «Apriori», как показано на рисунке 3.1, отображает все продукты, добавленные в базу данных, а также кнопки с дополнительными сервисами. С главной формы можно перейти к корзине, где можно подобрать продукцию (рис. 3.2), просмотреть популярные наборы (рис. 3.3), а также посмотреть правила (рис. 3.4).

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



Рисунок 3.1 - Главная форма

Рисунок 3.2 - Подбор продукции

Рисунок 3.3 ? Популярные наборы (с учетом уровня поддержки 2-5)



Рисунок 3.4 ? Правила

Рисунок 3.5 - Добавление категории

Рисунок 3.6 - Список транзакций

3.3 ПРИМЕР ОФОРМЛЕНИЯ ЗАКАЗА

персонализация интеллектуальный товар ассоциативный

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

а) Оформление заказа с помощью «Эксперта выбора».

Для того чтобы воспользоваться «Экспертом выбора» необходимо на главной форме программы нажать кнопку корзина. На экране появится окно, где есть кнопка «Эксперт выбора» (рис. 3.7).

Рисунок 3.7 - «Эксперт выбора»

После нажатие данной кнопки, пользователю предлагается ответить на три вопроса. Вопрос №1 представлен на рисунке 3.8, вопрос №2 представлен на рисунке 3.9, вопрос №3 представлен на рисунке 3.10.

Рисунок 3.8 - Вопрос №1



Рисунок 3.9 - Вопрос №2

Рисунок 3.10 - Вопрос №3

После ответов на данные вопросы, программа покажет интересующие пользователя продукты. Пользователь выбирает соответствующий продукт и нажимает кнопку «Добавить в корзину» (рис. 3.11).

Рисунок 3.11 - Выбор продукта

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

Рисунок 3.12 - Покупка продукции

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

б) Оформление заказа «вручную».

Для оформления заказа «вручную» необходимо на главной форме системы нажать кнопку «Транзакции», которую можно увидеть на рисунке 3.6. После чего следует нажать на кнопку «Добавить данные» (рис 3.13), и через запятую следует ввести необходимые товары.

Рисунок 3.13 - Добавление транзакции

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

ВЫВОДЫ

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

Интеллектуальная система создана с использованием средств СУБД SQL SERVER, а также среды Python 2.6. Работа с системой не требует от пользователей особых знаний в области баз данных. При заданном запросе система подбирает клиенту необходимый продукт и предлагает дополнительные товары в зависимости от интересов. Для этого клиент должен описать критерии, по которым система определит потребности. Программа является легкой в освоении и эксплуатации, что достаточно важно для конечного пользователя.

ПЕРЕЧЕНЬ ССЫЛОК

1. Agrawal R. Mining Association Rules Between Sets of Items in Large Databases. / R. Agrawal, T. Imielinski, A. Swami. // SIGMOD Conference 1993. ? Р. 207-216.

2. Hipp J. Algorithms for association rule mining - A general survey and comparison. / J. Hipp, U. Gьntzer, G. Nakhaeizadeh. // SIGKDD Explorations. ? №2(2). - 2000. - Р. 1-58.