Использование технологии анализа данных в интеллектуальных информационных системах 1 - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
О представлении данных и знаний для интеллектуального анализа социологических... 1 247.25kb.
Когнитивные технологии в компьютерных системах проектирования и анализе... 1 122.15kb.
Методика определения актуальных угроз безопасности персональных данных... 1 120.44kb.
С. В. Прокопчина; Н. К. Румянцев 1 37.04kb.
Политика безопасности персональных данных, обрабатываемых в информационных... 1 216.33kb.
«Методы моделирования данных в аналитических информационных системах» 3 408.24kb.
Интеллектуальный анализ данных средствами ms sql server 1 27.08kb.
1. Термины и определения (документы фстэк россии) Безопасность персональных... 1 151.26kb.
Учебная программа Дисциплины р1 «Моделирование информационных процессов» 1 127.43kb.
Модель угроз безопасности персональным данным при их обработке в... 1 82.13kb.
Информация о курсе Название курса 1 37.97kb.
«введение в интеллектуальный анализ данных» 1 10.37kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Использование технологии анализа данных в интеллектуальных информационных системах - страница №1/1

Использование технологии анализа данных в интеллектуальных информационных системах1
Арсеньев С.Б., Бритков В.Б., Маленкова Н.А.
Аннотация

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


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

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

Методы «добычи» знаний (data mining) позволяют уменьшить остроту проблемы. Используя продвинутые аналитические методы в области добычи знаний из исходных, “сырых”, данных, многие организации увеличивают прибыль, повышают производительность, сокращают затраты и увеличивают удовлетворенность клиентов. Они уже активно используются при анализе рынка, маркетинге, прогнозе фондовых котировок и других бизнес-приложениях. Но в первую очередь эти методы сегодня должны заинтересовать коммерческие предприятия, развертывающие проекты на основе информационных хранилищ данных (Data Warehousing).

Попробуем дать сравнительную оценку возможностей анализа данных Человеком и компьютером. По оценке Дж. Неймана объем памяти мозга человека (число нейронов) составляет ~1020 бит. В то же время, физическое быстродействие отдельного биологического нейрона чрезвычайно низко по сравнению быстродействием современной вычислительной техники, оно на 8 порядков величины меньше быстродействия современного персонального компьютера и проигрывает суперкомпьютерам более десяти порядков величины. Соотношения объема и быстродействия памяти и определяют возможное использование искусственного интеллекта, систем KDD (Knowledge Discovery in Databases) – систем извлечения знаний из баз данных. Однако ни одна программа принципиально не в состоянии сегодня, ни и в ближайшей перспективе учесть многообразия различных факторов, как ассоциативное мышление человека. Как постановщик задачи Человек принципиально превосходит возможности компьютера.

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

Основные понятия и определения

Knowledge discovery in databases («обнаружение знаний в базах данных») – аналитический процесс исследования человеком большого объема информации с привлечением средств автоматизированного исследования данных с целью обнаружения скрытых в данных структур или зависимостей. Предполагается полное или частичное отсутствие априорных представлений о характере скрытых структур и зависимостей. KDD включает предварительное осмысление и неполную формулировку задачи (в терминах целевых переменных), преобразование данных к доступному для автоматизированного анализа формату и их предварительную обработку, обнаружение средствами автоматического исследования данных (data mining) скрытых структур или зависимостей, апробация обнаруженных моделей на новых, не использовавшихся для построения моделей данных и интерпретация человеком обнаруженных моделей.

Data mining («разработка данных») – исследование и обнаружение “машиной” (алгоритмами, средствами искусственного интеллекта) в сырых данных скрытых структур или зависимостей, которые


  • ранее не были известны,

  • нетривиальны,

  • практически полезны,

  • доступны для интерпретации человеком. [2]

В целом технологию data mining достаточно точно определяет Григорий Пиатецкий-Шапиро — один из основателей этого направления:

data mining — это процесс обнаружения в сырых данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности

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

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

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

 Полученная прямоугольная таблица пока еще является слишком сырым материалом для применения методов KDD, и входящие в нее данные необходимо предварительно обработать, так как они могут быть в разных форматах, могут быть неполными или избыточными. В случае избыточности данных необходимо ограничить количество полей. Некоторые поля являются неинформативными: почти все записи имеют одинаковое значение поля, или наоборот, количество записей приблизительно равно количеству значений этого поля. Наконец, полей может быть очень много, и если мы все их включим в исследование, то это сильно увеличит время счета, поскольку практически для всех методов KDD характерна сильная зависимость времени счета от количества параметров, поэтому необходимо выбрать самые значимые для исследования. Но существует не только избыточность полей, но и избыточность записей. Зачастую в системах при очень большом количестве записей их выбирают случайным образом или берут каждую n-ю запись таблицы. Конечно, количество записей сильно зависит от метода анализа, но практика показывает, что в основном записей должно быть не менее 30 и не более нескольких сотен тысяч. Во многих системах к данным предъявляют строгое требование: для каждой записи должно быть известно значение каждого поля. В этом случае приходится восполнять недостающие значения. Наиболее очевидным является заполнение отсутствующих значений средним значением. Также любая реальная база данных обычно содержит ошибки, очень неточно определенные значения, записи, соответствующие каким-то редким, исключительным ситуациям, и другие дефекты, которые могут резко понизить эффективность методов KDD, применяемых на следующих этапах анализа. Такие записи необходимо отбросить.

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



Цена при открытии торгов

Цена при закрытии

Миним. цена за день

Максим. цена за день

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

Среднее значение цены за день

Изменение цены за день


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

Замечание: если в таблице есть категориальная переменная (не числовая), которая, например, может принимать три значения, то можно вместо нее включить 3 новых переменных, которые будут принимать значение 1 для своего значения и 0 для всех остальных.

 Третий этап – это применение методов KDD. Сценарии этого применения могут быть самыми различными и включать сложную комбинацию разных методов, особенно если используемые методы позволяют проанализировать данные с разных точек зрения. Собственно этот этап исследования и принято называть data mining.

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

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

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

Одной из систем, которая объединяет в себе все перечисленные компоненты, является пакет PolyAlalyst компании «Megaputer Intelligence» (www.megaputer.ru),. В ее основу положена технология искусственного интеллекта Data Mining. При обработке исходных данных она позволяет обнаруживать многофакторные зависимости, которым придает затем вид функциональных выражений (класс функций в них практически произволен), можно также строить структурные и классификационные правила (по автоматически формируемым обучающим примерам). При этом анализу подвергаются исходные данные различных типов: действительные числа, логические и категориальные величины. Выводимые правила принимают вид либо функций, либо циклов, либо условных конструкций.

Система включает набор математических модулей, называемых Машинами исследований (Exploration engines),. В последней версии программы 4.5, выпущенной компанией «Мегапьютер» в 2000 году имеется 10 машин исследований- это:


  • Поиск законов (FL - Find Laws) – эволюционное программирование

  • Поиск зависимостей (FD - Find Dependencies) – универсальный препроцессор

  • Классификация (CL - Classify) – на основе функции принадлежности

  • Деревья решений (DT - DecisionTree) – классификация на основе деревьев решений

  • Кластеризация (FC - Cluster) – многомерный кластеризатор

  • PolyNet Predictor (PN) – полиномиальная нейронная сеть

  • Множественная линейная регрессия (LR – Linear Regression)

  • Метод "ближайшего соседа" (MB) – гибрид алгоритма Nearest Neighbor и генетических алгоритмов

  • Basket Analysis (BA) – метод корзины покупателя

  • Общая статистика (SS – Summary Statistics) – модуль суммарной статистики

Рассмотрим подробно некоторые из перечисленных методов.

Множественная линейная регрессия.



(Linear Regression).

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



,

где - функция зависимости целевой переменной от входных данных и некоторых параметров,



- параметры регрессии,

а - шум, ошибки.

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

.

Замечание: Если точки сильно «раскачиваются», выбиваются из распределений, то в последней формуле правильнее выбирать не сумму квадратов, а сумму модулей.

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



.

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



.

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

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

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

Далее алгоритм продолжается.

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



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

  2. Орномизированное тестирование. Входные переменные представлены прямоугольной таблицей, а целевая переменная столбцом данных. Делаем случайные перестановки в столбце , и получаем несколько новых столбцов . Для каждого такого столбца проводим решение регрессионной задачи, и получаем несколько ошибок . Обозначим ошибку для исходных значений , а ошибку каждого j-го столбца обозначим . Если , то определенная нами зависимость является статистически значимой.

Эту же процедуру можно использовать для определения значимости модели. Мерой значимости для этого метода является: . При выполнении этого условия установленная зависимость является статистически значимой.

Отметим, что критерий оценивает значимость для модели каждого критерия, а критерий оценивает значимость всей модели.

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

Замечание: по количеству записей этот метод является линейным, а по количеству полей – более сложный.

Кластеризация


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

Методы автоматического разбиения на кластеры редко используются сами по себе, просто для получения групп схожих объектов. Анализ только начинается с разбиения на кластеры. Коли уж кластеры обнаружены, естественно использовать другие методы data mining, чтобы попытаться установить, а что означает такое разбиение на кластеры, чем оно вызвано.

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

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

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

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

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

Деревья решений


(Decision Tree)

Это алгоритм классификации.

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

Для построения дерева используем обобщенный алгоритм. Пусть имеется таблица данных X, в которой n полей, и есть корень дерева. Y – целевая переменная.




X




































































































Y















В


А Y



























ыделяем какое-либо поле в таблице и используем его, чтобы предсказать значение целевой переменной, т.е. если значение поля x больше, меньше или равно определенному значению a, то значение переменной y будет таким-то и так далее. Это правило можно представить в виде таблицы:

Аналогичную процедуру проделываем для каждого поля таблицы. В результате получаем n предсказаний переменной Y. Из этого множества предсказаний можно выбрать лучшее по определенным критериям. Теперь с корнем дерева связываем утверждение, которое заложено в этом предсказании (например, если x>a, тогда y=true). Потомков в данном дереве будет столько, сколько значение переменной y. Таким образом мы расщепили данные на 2 половины. Теперь выбираем один из полученных узлов, которому соответствует одна половина данных, и для него проделываем ту же самую процедуру. Данное расщепление продолжается до того, пока не сработает критерий остановки: если для листа значение целевой переменной одинаково для всех данных, которые ему соответствуют, то алгоритм останавливается. Но на самом деле расщепление ограничивают раньше, так как данных может быть слишком много.



Критерии расщепления:

  1. Количество ошибок, которое дает предсказывающее правило. Например, пусть есть правило

Это правило дает определенное количество ошибок, поэтому выбираем переменную, которая даст наименьшее количество ошибок.

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

  1. Критерий взаимной энтропии. Пусть x и y – булевы переменные. Построим таблицу, в ячейках которой запишем количество записей, которые соответствуют значениям x и y. Всего есть N записей.

x/y

0

1

0

n00

n01

1

n10

n11

Обозначим

, ,

, .

Тогда




Если значение независимой переменной не зависит от конкретных переменных, то используют вероятность попадания в данную ячейку:



т.е. произведение вероятностей попадания в данный столбец и данную строку.

Значение IG: сколько информации о значении целевой переменной содержится в данной независимой переменной, т.е. чем больше значение IG, тем такой информации содержится больше.

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



Замечание: Данный критерий расщепления эффективен в случае «перекошенного» распределения данных.

  1. Критерий Джинни. В данном случае минимизируется критерий:



  1. Критерий раздвоения:



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

Модификация метода деревьев решений


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

Глобальная оптимизация


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

Методы остановки расщепления


  1. Расщепление происходит до тех пор, пока оно вообще возможно.

  2. Прунинг – усечение расщепленного дерева. Данные в таблице делятся на 2 части: одна часть используется для построения дерева, а вторая – для прунинга. Вначале полностью строится дерево, затем его используют для предсказания значения целевой переменной на второй порции данных. Затем вычисляется процент ошибок предсказаний, который получили на тех данных, на которых строили дерево, и умножается на константу, примерно равную единице (как правило, 1,3).На основании этого происходит отсечение узлов дерева снизу от листьев до тех пор, пока ошибка предсказания не больше величины .

  3. Каждое расщепление подвергается тесту: надо или не надо расщеплять. Зачастую используется проверка, насколько случайно данное расщепление.

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



Метод ближайших соседей


(memory based reasoning)
Данный метод используется и для классификации, и для прогноза числовых зависимостей.

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

Возникают вопросы: какова мера близости между записями? Сколько ближайших записей необходимо отбирать? Что представляет собой сама процедура?

В качестве расстояния между двумя записями используется мера



,

где - номер столбца,



- коэффициент для приведения всех переменных к единой системе измерения.

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



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

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

Тогда .

Если зафиксировать набор независимых переменных, то необходимо найти несколько наиболее близких «соседей» - записей, которые будут использоваться для прогноза. Обозначим - число соседей. Из соседей находим среднее и взвешиваем его:

,

где - расстояние от записи, для которой ищем прогноз, до i-го соседа.

Если - категориальная переменная, то для каждого ее значения вычисляем:

.

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


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

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



  1. Элитизм. Берется некоторый процент хромосом (оценка происходит на основе критерия ) и переносится в новое поколение.

  2. Мутация. Берутся случайные хромосомы и в них случайным образом меняются значения генов.

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

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

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

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

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



,

где - означает, используем ли мы i-ю запись для предсказания, или нет.

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

Таким образом, нашу задачу можно сформулировать так:

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

.

Необходимо найти такой набор этих параметров, для которого ошибка будет минимальной.


Баскет-анализ (анализ бинарных данных)
По сути это задача нахождения ассоциированных признаков.

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

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

Допустим, у нас есть записей (покупателей) и полей (товаров). Обозначим 2 каких-либо продукта и . Создадим таблицу , в ней выделим 2 столбца с товарами и - их купили соответственно и покупателей. Тогда количество покупателей, купивших продукт и совместно будет .

Зафиксируем продукт . Его купили человек. Пусть . Тогда вероятность, что при испытаний мы получим и больше покупок равна

.

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

С какой вероятностью при и при мы получим и больше покупателей?

Чем эта вероятность меньше, тем больше связь между товарами и , т.е. тем более неслучайно такое совпадение. Это мера расстояния между товарами. Тогда - таблица расстояний между товарами.

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

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

Пусть есть два кластера с вероятностями и , и новая пара товаров принадлежит обоим кластерам. Мы пытаемся объединить эти кластеры, высчитываем для нового кластера вероятность . Если и , то тогда слияние не производится.

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

В результате кластеризации мы получим некоторые товары, которые не принадлежат ни одному кластеру.

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

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


Эволюционное программирование

(Ядерный метод нахождения числовых зависимостей Find Laws)

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


CORE

PolyAlalyst


Внутренний



язык

программирования

Модуль

отбора

программ

Модуль

оценки

программ

Стратегия

поиска

программ


Язык программирования включает в себя:

  1. Типы данных. Существует 2 класса типов данных

  • Те, которые определены в любых областях (например, булевский, числовой)

  • Типы, которые определяются специально для данной области

  1. Функциональные примитивы

  • Булевые логические операции , ,

  • если и в противном случае

  • операция выбора , где - булевая переменная, а - числа. (if b then x else y)

Если пользователь задает новые типы, то он должен определить и их свойства (например, отношения равенства, неравенства, следующий и т.д.

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

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

  1. Структурные конструкции. Существует 2 вида конструкции:

  1. функциональная композиция.

Пусть есть программа A и есть программы B и С. Объединив их в структурную композицию получаем одну большую программу

A





B


C





Требованием к данной композиции – совпадение типов входов программы А и выходов программ В и С.



  1. итерация-рекурсия - служит для выражения всякого рода условных и безусловных циклов, а также рекурсивных конструкций..

Модуль отбора программ.

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



  • программа не должна иметь входов (параметров), от которых возвращаемое ею значение не зависит

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

  • программа не должна быть эквивалентна какой-либо из построенных ранее программ.

Программы, не удовлетворяющие этим условиям, отсеиваются.

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

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


Модуль оценки генерируемых программ.

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

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

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

Таким образом, получаем 2 процесса поиска новых программ:


  1. из полученных программ генерируем новые программы

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

Получается некоторая система с несколькими точками роста и «этажами» генерации из этих точек. В системе PolyAnalyst данный алгоритм работает тем быстрее, чем больше количество записей. Так при генерации новой программы возникает вопрос: а когда нужно строить новый этаж? Известно, что новая программа будет не хуже своего предка, но насколько потомок должен быть лучше предка, чтобы было возможно построение нового этажа? Чем больше данных, тем меньше будет улучшение потомка и тем меньше будет вероятность построения нового яруса, т.е. улучшение должно быть большим , и количество этажей построения новых моделей будет меньше, соответственно скорость алгоритма увеличиться.

Критерии остановки поиска:

  1. время,

  2. достигнутая точность.

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

Этот модуль выбирает методы продукций и компоненты для построения новых программ. Синтез новых программ ведется двумя параллельными процессами. Первый, с более низким приоритетом, осуществляет полный перебор синтаксически и семантически правильных программ в порядке возрастания их сложности, которая примерно равна числу входящих в них примитивов. Другой процесс, имеющий более высокий уровень приоритета, создает новые программы, используя так называемые обобщающие преобразования (GT – generalizing transformations). Когда PolyAnalyst находит статистически значимое решение, он генерирует отчет, сообщает пользователю наиболее значимое и наиболее точное найденные решения в аналитической форме (на языке символьных правил), статистические характеристики решений, и представляет наиболее значимое решение и ошибки в графической форме.

Применение обобщающих преобразований к существующей программе P порождает новую программу Pgt, называемую GT-производной. Для каждой программы существует большое количество классов преобразований ее структуры, которые ведут к образованию ее GT-производной, не ухудшающей оценку программы Ev[Pgt]Ev[P]. Это свойство позволяет организовать GT-поиск в пространстве программ следующим образом. Когда процесс полного поиска находит программу, для которой значение функционала Ev[P] достаточно мало, она становится “родителем” для поколения программ, создаваемых при помощи обобщающих преобразований из этой программы. Если одна из полученных программ показывает значительное уменьшение Ev[P], то она, в свою очередь, становится отправной точной для построения при помощи обобщающих преобразований новых программ, и так далее. Используя такой подход, можно построить довольно сложную программу за вполне разумный период времени.

Этот метод не лишен недостатков. Во-первых, принятый алгоритм позволяет строить модели только для статических взаимосвязей в данных. Действительно, он ищет зависимости только между значением поля yi целевой переменной и значениями полей xij той же самой записи. Реальные же данных часто определяются нелокальными динамическими связями – значениями некоторых из переменных в предыдущие моменты времени. Во-вторых, он ищет четко определенные, детерминистические связи. В реальной же жизни, как мы уже отмечали, неопределенность всегда присутствует и играет важную роль. Наконец, он ищет простые аппроксимации зависимостей в “простых” данных. Другими словами, реальные возможности эволюционного программирования ограничены.

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


Заключение
Средства data mining предполагают оказание помощи организациям в нахождении скрытых зависимостей в данных. Получаемые модели можно использовать как для предсказания будущих значений, так и для описания текущего состояния. Результат применения методов нахождения нового знания может проявляться в широком спектре, от увеличения доходов, до уменьшения расходов. Эти исследования в настоящее время широко распространяются на различные области человеческой деятельности (медицина, управление в чрезвычайных ситуациях, промышленные предприятия) [8-12]. Однако, системы, реализующие алгоритмы добычи знаний из данных не могут полностью заменить аналитиков, которые хорошо понимают деловую область, сами данные, общий характер используемых аналитических методов и обладают способностью интерпретировать полученные результаты.

Литература

  1. Киселев М.В. «Алгоритмы Data Mining». Курс лекций. Компания «Мегапьютер». 2001.

  2. Арсеньев С.Б. «Извлечение знаний из медицинских баз данных». Компания «Мегапьютер».

  3. Киселев М., Соломатин Е.. Средства добычи знаний в бизнесе и финансах. — Открытые системы, № 4, 1997.

  4. Дюк В.А. Обработка данных на ПК в примерах. — СПб: Питер, 1997.

  5. Дюк В.А. «От данных к знаниям – новые возможности обработки баз данных». Санкт-Петербургский институт информатики и автоматизации Российской Академии Наук.

  6. Knowledge Discovery Through Data Mining: What Is Knowledge Discovery? — Tandem Computers Inc., 1996.

  7. Буров К. «Обнаружение знаний в хранилищах данных». – Открытые системы, №5-6, 1999.

  8. Геловани В.А., Бритков В.Б. Интеллектуальные методы в задачах анализа больших объемов информации для поддержки принятия решений. Проблемы управления безопасностью сложных систем: Материалы IХ международной конференции-М.: ИПУ РАН, 2001 г.

  9. Arseniev S. Kiselev M., Ananyan S Regressionj-Nased Classification Methods and thier comparison with Decision Tree Algorithms - in Lectures Notes in Artificial Intelligence Springer 1263, 1997, 134-144.

  10. Arseniev S. Kiselev M., Joseph Quinlan, Mark Bloom Combination of statistical data preprocessing program ARNAVAC and symbolic knowledge discovery system PolyAnalyst for prediction of right ventricular support with left ventricular assist - Proceedings of ESCTAIC-95, Palermo, 18-23 September, 1995, p.D7

  11. Arseniev S. Kiselev M., Vanina L., Knyazev A. Application of Machine Discovery System PolyAnalyst to Modeling Electron Density Distribution in Ionospheric Region D Accepted for publication in Proceedings of IUGG-95 Conference; IASPEI/SEG Symposium (S13): "Application of Artificial Intelligence Computing in Geophysics"; July 12, 1995, Boulder, Colorado, USA

  12. Arseniev S. Kiselev M., Classen B. Patient Ventillation Management Expert Rules derived from Ulm University Clinic Using PolyAnalyst - Knowledge Discovery System Proceedings of ECML-95 Workshop on Statistics, Machine Learning and Knowledge Discovery in Databaes, Heraklion, Greece, pp 199-203.




1 Работа выполнена при финансовой поддержке РФФИ (проект N 00-01-00534).