Zsoft: Введение
     
 
Компания Zsoft
О компании
Партнёры
Заказчики
Услуги
Вакансии

Data Mining
Введение
Применение
Пример
Стандарты
Глоссарий

Продукты
Библиотека Xelopes:
О продукте
Применение
Лицензия
Документация
Демо

3D визуализатор Exero
О продукте

Визуализатор Recomendation Engine
Демо

Введение



На протяжении последних десяти лет в информационной индустрии наблюдается устойчивый рост интереса к технологиям анализа данных и основанным на этих технологиях системам поддержки принятия решений. За всей областью закрепился, ставший уже привычным в англоязычной литературе, термин Data Mining или Knowledge Discovery. На русском языке употребляют также словосочетание "интеллектуальный анализ данных". Приведем классическое определение этого термина, предложенное в 1996 году в работе Fayyad, Piatetsky-Shapiro, и Smyth "Advances in Knowledge Discovery and Data Mining":
"The non-trivial process of identifying valid, novel, potentially useful, and ultimately understandable patterns in data"- Нетривиальный процесс обнаружения новых, потенциально полезных, корректных и интерпретируемых закономерностей в данных.

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

Последние тенденции и новшество в индустрии хранения и анализа данных, заключаются в переходе к концепции Data Warehouse (Хранилища Данных). Это основанный на современных системах управления базами данных, "предметно-ориентированный, интегрированный, неизменчивый, поддерживающий хронологию набор данных, организованный для целей поддержки принятия решений" (W. H. Inmon. Building the Data Warehouse. - Wellesley, MA: QED Pub-lishing Group, 1992). Введение этого нового слоя в архитектуру информационно-аналитических приложений было продиктовано не только соображениями концептуальной чистоты системы, но и неудачным опытом реализации систем анализа непосредственно в среде СУБД. Последние ориентированы, как правило, на решение задач оперативного сбора информации и поддержки транзакций (OLTP), что, во-первых, обуславливает выбор определенной модели хранения данных - реляционной, а, во-вторых, приводит к тому, что работающая OLTP система активно использует все вычислительные ресурсы. Оба эти фактора, приводят к тому, что аналитические подсистемы, требующие очищенных и, порой избыточных, данных, а также значительных вычислительных ресурсов, работают в системах, совмещенных с OLTP неудовлетворительно. Data Warehouse призван решить все эти вопросы и стать основой для построения системы анализа данных.

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

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

Оперативно-аналитический анализ или OLAP. В OLAP данные агрегируются, предоставляя аналитику любую степень обобщения по любому интересующему его разрезу. В отличие от информационно-поискового анализа, здесь мы можем обнаружить различного рода закономерности и тенденции в данных, которые иначе были бы не видны. OLAP был закономерным этапом в развитии систем хранения и анализа данных и показательно, что сам термин ввел в литературу именно E. F. Codd - основоположник реляционной модели. В 1993 в работе "Providing OLAP (On-Line Analytical Processing) to User-Analysts: An IT Mandate." он рассмотрел ее недостатки, указав в первую очередь на невозможность "объединять, просматривать и анализировать данные с точки зрения множественности измерений, то есть самым понятным для аналитиков способом". Итак, резюмируя, OLAP, вводит нас в сферуобобщенных данных.

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

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

Например, текст или изображения. Исторический подход основывается на том, что есть целый ряд исторически сложившихся дисциплин, например теория нейронных сетей или нечеткая логика, перечисляя которые определяют предмет и границы области Data Mining. Мы, следуя уже сложившейся в англоязычной литературе традиции, будем придерживаться более формального подхода. А именно, называть все технологии Data Mining Machine Learning (машинным обучением) и делить их на две большие группы: Supervised learning и Unsupervised Learning. В первом случае - "обучение с учителем", задача анализа данных, например, классификация, осуществляется в несколько этапов. Сначала с помощью какого-либо алгоритма Data Mining, строится модель анализируемых данных - классификатор. Затем, классификатор подвергается "обучению". Другими словами, проверяется качество его работы и, если оно неудовлетворительно, происходит "дополнительное обучение" классификатора. Так происходит до тех пор, пока мы не достигнем требуемого уровня качества или не убедимся, что вы-бранный алгоритм не работает корректно с данными, либо же сами данные не имеют структуры, которую можно выявить. Unsupervised Machine Learning объединяет технологии, выявляющие дескриптивные модели. Например, закономер-ности в покупках совершаемых клиентами большого магазина. Очевидно, что если эти закономерности есть, то модель должна их представить и неуместно го-ворить об ее обучении. Отсюда и название -Unsupervised Learning. Дальнейшая классификация технологий Data Mining опирается на то, какие задачи этими тех-нологиями решаются. Supervised Machine Learning, таким образом, подразделяется на классификацию и регрессию. А Unsupervised Learning на Basket and SequenceAnalysis и Clustering (анализ рыночных корзин, сиквенциальный анализ и кластеризацию)

Постановка задач классификации и регрессии такова:
Рассмотрим область из M точек В соответствии с терминологией Data Mining точки xi d-мерного пространства называются векторами, а значения векторов вдоль каждого измерения называются атрибутами. Каждой точке xi ставятся в соответствие значения функции yi, i=1, ..., M, где для случая регрессии и для случая классификации. Множество точек xi и связанных с ними yi, будем называть тренировочным набором данных. Также рассмотрим другое множество точек того же пространства и связанные с ними "эталонные" значения функции. Это множество будем называть обучающим набором данных. Предполагается, что оба множества имеют нечто общее, что позволяет говорить о некой присущей им структуре. Например, оба являются различными выборками из серии проводимых экспериментов, где исследуется зависимость yi от набора параметров xi.

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

Рассмотрим геометрическую интерпретацию задач классификации и регрессии в двумерном пространстве (рис 1). Каждой точке ставится в соответствие значение yi где символ "+" соответствует значению +1, а символ "-" значению -1. Очевидно, что данные имеют четко выраженную структуру: все точки класса "+" сосредоточены в центральной области. Построение классификационной функции сводится к построению поверхности, которая обводит центральную область. fc определяется как функция, имеющая значения +1 внутри обведенной области и -1 вне.
Рис 1. Классификация в двумерном пространстве

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

Не вдаваясь в подробности реализации и теоретические предпосылки каждого из алгоритмов, приведем общую классификацию самых распространенных. Во-первых, их можно разделить на мультивариантные и унивариантные, исходя из того, будет ли алгоритм в своей работе оперировать атрибутами векторов как целым, или же рассматривать их по отдельности. Далее, алгоритмы можно классифицировать по базовым методикам, которые они используют. Это деление достаточно условное и служит, скорее, дидактическим целям. Итак, алгоритмы основанные на методиках математической статистики - это деревья решений CART, дискриминантный анализ и регрессия, Naive Bayes. Использующие положения теории информации - деревья решений ID3 и С4.5, MDLP, классификационные правила. Отдельную группу составляет одна из самых успешных методик классификации и регрессии - Support Vector Machine. Далее мы можем перечислить нейронные сети, нечеткую логику, дискретные методы, как то, Sparse Grid и вейвлетная классификация, а также группу алгоритмов, которые основываются, скорее, на соображениях здравого смысла, чем на какой-либо определенной математической теории. Например, Nearest Neighbor Classifier.

Классическим примером применения классификации на практике является решение проблемы о возможной некредитоспособности клиентов банка. Этот вопрос, тревожащий любого сотрудника кредитного отдела банка, можно, конечно, разрешить интуитивно. Если образ клиента в сознании банковского служащего соответствует его представлению о кредитоспособном клиенте, то кредит выдавать можно, иначе - отказать. По схожей схеме работают установленные в тысячах американских банках системы Data Mining. Лишенные субъективной предвзятости, они опираются в своей работе только на историческую базу данных банка, где записывается детальная информация о каждом клиенте и, в конечном итоге, факт его кредитоспособности (вернул ли клиент ранее выданный кредит или нет).
Клиенты банка, в этих системах, интерпретируется как вектора в пространстве ?
Ad.?Различные данные о клиентах (возраст, годовой доход, профессия и т. д.) соответствуют атрибутам вектора. Факт возврата (невозврата) кредита играет роль функции: yi=.
Часть упомянутой исторической базы можно рассматривать как тренировочный набор данных, а другую часть - как обучающий набор. При таком подходе, задача определения риска, связанного с клиентами, сводится к Data Mining задаче построения классификатора. Решить ее можно с помощью нескольких методик. Также очевидно, что она имеет решение, поскольку интуитивно понятно, какого рода закономерности в данных обуславливают риск, связанный с клиентом. Высокий доход и хорошая профессия, безусловно, хороший аргумент в пользу благонадежности клиента.

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

Анализ рыночных корзин (Basket Analysis) и сиквенциальный анализ являются одними из самых популярных приложений Data Mining. Дадим формальную постановку задачи Basket Analysis, называемой также, задачей поиска ассоциативных правил (Association Rules).Рассмотрим множество произвольных объектов. Далее, рассмотрим множество транзакций D, где каждая транзакция является некоторым набором объектов из
.
С каждой транзакцией ассоциируем уникальный идентификатор. Назовем его TID. Будем говорить, что транзакция T содержит набор объектов X из множества , если .
Ассоциативным правилом будем называть связь между наборами объектов в форме
Ассоциативное правило на множестве транзакций D имеет confidence c, если c% всех транзакций в D, которые содержат X, также будут содержать Y. Ассоциативное правило имеет на множестве транзакция D support s, если s% всех транзакций содержат набор
,
т. е. одновременно содержат как X, так и Y. Задача поиска ассоциативных правил - это выявлений всех ассоциативных связей на множестве транзакций D при заданных значениях минимального support и confidence.

Изложенные выше идеи, допускают очень простую интерпретацию, если привести пример из области маркетинга. Собственно, маркетинговые исследования и послужили отправной точкой для разработки именно этого направления Data Mining. Одна из основных задач в маркетинге - это анализ того, что и почему покупатели супермаркетов кладут себе в корзинку (basket). Если в этих покупках обнаруживаются закономерности, то их анализ и осмысление способны очень серьезно изменить маркетинговую стратегию магазина. Это, в конечном итоге, сказывается на его прибыли и способности выжить в конкурентной борьбе. Итак, для решения задачи анализа, будем полагать, что все товары магазина образуют упомянутое выше множество
.
Все покупки, сделанные клиентом за один раз, другими словами его тележка с товарами, соответствуют одной транзакции. Множество всех тележек, прошедших через кассы магазина соответствует множеству всех транзакций D. Если для алгоритма анализа мы зададим значения support=50% и confidence=30%, то в результате его работы, получим все группы товаров
,
которые одновременно встречаются более чем в 50% всех транзакций. Причем, в 30% всех транзакций, где содержится набор товаров X также, обязательно будет присутствовать набор Y.

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

Кластеризация может применяться практически в любой области, где необходимо исследование экспериментальных или статистических данных. Рассмотрим пример из области маркетинга. Известно, что люди, имеющие схожий социальный статус, также имеют схожие стереотипы поведения. Это проявляется, в частности, в том, что в их потребительских корзинах есть очень много общего и, в свою очередь, они значительно отличаются от потребительских корзин людей из другой социальной группы. Таким образом, располагая демографическими данными потенциальных клиентов, мы можем выделить, используя кластеризацию, несколько явно выраженных социальных групп и проводить уже узко направленные, целевые маркетинговые акции. Это, конечно же, будет гораздо дешевле и эффективнее, чем проводить маркетинг, предполагая, что потребности целевой аудитории однородны.
Для научных исследований, изучение результатов кластеризации, а именно выяснение причин по которым объекты объединяются в группы, способно открыть новые перспективные направления. Традиционным примером, который обычно приводят для этого случая, является периодическая таблица элементов. В 1869 году Дмитрий Менделеев разделил 60 известных в то время элементов, на кластеры или периоды. Элементы, попадавшие в одну группу, обладали схожими характеристиками. Изучение причин, по которым элементы разбивались на явно выраженные кластеры, в значительной степени, определило приоритеты научных изысканий на годы вперед. Но лишь спустя пятьдесят лет квантовая физика дала убедительные объяснения периодической системы.

Data Mining является достаточно новой и постоянно развивающейся областью информационных технологий. Однако уже сейчас, мы можем наблюдать вступление этой области в стадию относительной зрелости. Об этом, в частности, свидетельствует появление ряда стандартов, пытающихся упорядочить и согласовать достижение всей индустрии анализа данных за последнее десятилетие. Стандарты затрагивают три основных аспекта Data Mining. Во-первых, унификацию интерфейсов, посредством которых любое приложение может получить доступ к функциональности Data Mining. Здесь сложилось два направления. Это стандартизация интерфейсов для объектных языков программирования (CWM Data Mining, JDM, OLE DB for Data Mining) и попытки разработки надстройки над языком SQL, которая позволяла бы обращаться к инструментарию Data Mining встроенному непосредственно в реляционную базу данных (SQL/MM, OLE DB for Data Mining). Второй аспект стандартизации - это выработка единого соглашения по хранению и передачи моделей Data Mining. Не трудно догадаться, что основой для подобного стандарта является язык XML. Сам стандарт носит название PMML (Predicted Model Markup Language). И, наконец, существует стандарт CRISP, который дает рекомендации по организации процесса Data Mining в целом.

В завершение, приведем обзор рынка Data Mining в России. Очевидным фактом является растущая потребность бизнеса в инструментах, имеющих аналитическую функциональность. Также очевидно, что профессиональные предложения здесь практически отсутствуют. Однако решение существует. Программные продукты и опыт компании ZSoft позволяют решить сложившуюся проблему наиболее эффективным и экономичным образом. По результатам опроса, проведенного наиболее влиятельным ресурсом Интернета в области Data Mining www.kdnuggets.com, программный продукт Xelopes по популярности и распространенности занимает одно из первых мест, в списке из двадцати пяти других коммерческих продуктов.





Выбрать язык

Ссылки
Третье издание
Второе издание