Аннотация

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

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

Введение

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

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

В этой главе рассматривается вопрос об использовании эволюционных алгоритмов (ЭA), в частности, генетические алгоритмы (ГА) [29], [47] и генетического программирования (ГП) [41], [6],в сборе данных и открытии знаний. Мы ориентируемся на классификации задач сбора данных, который является обращенной задачей ЭА и извлекают знание высокого уровня из данных. Кроме того, мы обсуждаем использование ЭA для того, чтобы выполнить некоторую предварительную обработку и шаги постобработки процесса открытия знаний, уделяя особое внимание при выборе атрибутов и сокращения группы классификаторов. Мы показываем, как требования открытия знаний и сбора данных влияет на проект ЭА.

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

Эта глава организована следующим образом. Раздел 2 представляет краткий обзор открытия знаний и сбора данных. Раздел 3 обсуждает несколько аспектов дизайна ГА для открытия правила. Раздел 4 обсуждает ГА для того, чтобы выполнить некоторых предварительную обработку и шаги постобработки процесса открытия знаний. Раздел 5 обращается к использованию ГП в открытии правила. Раздел 6 обращается к использованию из НП в фазе предварительной обработки процесса открытия знаний. Наконец, раздел 7 представляет обсуждение, которое завершает главу.

2. Краткий обзор интеллектуального сбора данных и анализа знаний

Этот раздел делится на три части. ПОДРАЗДЕЛ 2,1 обсуждает желательные свойства обнаруженных знаний. П. 2.2 рассматриваются основные задачи сбора данных. П. 2.3 приводится обзор процесса открытия знаний

2.1 желаемых свойств обнаружен знаний

В сущности, сбора данных состоит из (полу-) автоматического извлечения знаний из данных. Это заявление поднимает вопрос, какого вида из знания мы должны попытаться обнаружить. Хотя это - субъективная проблема, мы можем упомянуть три общих свойства, которые должно удовлетворить обнаруженное знание; а именно, оно должно быть точным, понятным и интересным. Давайте кратко рассмотрим каждую из этих свойств. (См. также раздел 3.3.) Как будет показано в следующем разделе, в сборе данных мы часто интересуемся обнаружением знания, в которое имеет определенную предсказательную силу. Основная идея состоит в том, чтобы предсказать состояние, которое некоторый признак (и) примет в “будущем”, основанный на ранее наблюдаемых данных. В этом контексте мы хотим, чтобы у обнаруженного знания была высокая прогнозирующая степень точности. Это необходимо всякий раз, когда обнаруженные знания, будут использоваться для поддержки принятия решения, которое будет сделано человеком. Если обнаруженное "знание" - только черный ящик, который делает предсказания, не объясняя их природу, пользователь, возможно, не доверится этим знаниям [48]. Понятность знаний может быть достигнута при использовании представлений знаний высокого уровня. Популярный, в контексте анализа данных, представляет собой набор из IF-THEN (прогноз) правил, где каждое правило имеет вид:

IF <некоторые_условия_удовлетворены>
THEN <прогнозировать_некоторое_значение_для_атрибута>

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

2.2 задача сбора данных

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

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

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

IF (Неоплаченный_займ? = “нет”) and (Текущий_баланс > $3,000)
   THEN (Кредит = “хорошо”)
IF (Неоплаченный_займ? = “да”) THEN (Кредит = “плохо”)

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

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

Фактически, это тривиально, чтобы получить 100 % прогнозирующей точности в обучении, установленном, полностью жертвуя прогнозирующей работой на испытательной установке, которая была бы бесполезна. Чтобы видеть это, предположите, что для обучения, установленного с n примерами, алгоритм сбора данных "обнаруживает" правила n, то есть одно правило для каждого учебного примера, такого что, для каждого "обнаруженного" правила: (a) антецедент правила содержит условия с точно теми же самыми парами значения атрибута как соответствующий учебный пример; (b) урок, предсказанный последовательным правилом, то же самое как фактический урок соответствующего учебного примера. В этом случае "обнаруженные" правила тривиально достигли бы 100 % прогнозирующей точности на учебном наборе, но будут бесполезны для того, чтобы предсказать урок примеров, невидимых во время обучения. Другими словами не было бы никакого обобщения, и "обнаруженные" правила захватят только особенности учебного набора, или только "запомнят" учебные данные. В языке машинного изучения и сбора данных, правила сверхсоответствовали бы учебным данным.

Для всесторонней дискуссии о том, как измерить прогнозирующую точность правил классификации, читатель отнесен в [34], [67].

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

2.2.2 Моделирование зависимости. Эта задача может быть расценена как обобщение задачи классификации. В прежнем мы хотим предсказать ценность нескольких признаков - а не единственного признака цели, как в классификации. Мы сосредотачиваемся снова на открытии предсказания (IF-THEN) правила, так как это - представление знаний высокого уровня.

В наиболее общем виде, какой-нибудь атрибут может происходить как в предшествующие (IF part) правила и в последующей (THEN part) другого правила - но не как в предшествующие и последующие этого же правила. Например, мы могли бы обнаружить следующие два правила:

IF (Текущий_баланс > $3,000) AND (Зарплата = “высокая”)

THEN (Кредит = “хорошо”)

IF (Кредит = “хорошо”) AND (Возраст > 21) THEN (Ссуда_гранта = “да”)

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

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

2.2.3 кластеризации. Как уже упоминалось выше, в задачи классификации класс подготовки примера приведен в качестве вклада в алгоритм сбора данных, характеризующих форму обучения с учителем. Напротив, в задачу кластеризации алгоритмом сбора данных должны, в некотором смысле, "открыть" класс сам по себе, путем разбиения примеров в кластеры, которые представляет собой форму обучения без учителя [19], [20].

Примеры, которые похожи друг на друга (то есть примеры аналогичных значений атрибутов), как правило, распределяются в один кластер, тогда как примеры отличаются друг от друга, как правило, присваивается различным кластерам. Обратите внимание, что после того, как кластеры будут найдены, каждый кластер может рассматриваться как "класс", так что теперь мы можем запустить алгоритм классификации на кластерных данных, используя имя кластера, как этикетку класса. ГА для кластеризации обсудили например в работах [50], [17], [33].

2.2.4 Открытие Правил Ассоциации. В стандартной форме эти задачи (без учета изменений, предложенных в литературе) каждые данные экземпляра (или "записи") состоят из множества двоичных признаков называемых пунктами. Каждый экземпляра обычно соответствует потребительской сделке, где у данного экземпляра есть истинная или ложная ценность в зависимости от того, купил ли соответствующий клиент то изделие в той сделке. Правило ассоциации - отношения формы, IF X THEN Y, где X и Y наборы экземпляров и X C Y = ?[1],[2]. Пример правила ассоциации:

IF жареный_картофель THEN напиток, кетчуп

Хотя и классификация и правила ассоциации имеют IF THEN структура, есть важные различия между ними. Мы кратко упоминаем здесь два из этих различий. Во-первых, у правил ассоциации может быть больше чем один пункт в последовательном правиле, тогда как у правил классификации всегда есть один признак (одна цель) в последствии. Во-вторых, в отличие от задачи ассоциации, задача классификации асимметрична относительно признаков предсказания и признака цели. Предсказание признаков может произойти только в предыдущем правиле, тогда как признак цели происходит только в последовательном правиле. Более детальное обсуждение о различиях между классификацией и правилами ассоциации может быть найдено в [24].

2.3 Процесс Открытия Знаний

Применение алгоритма сбора данных в набор данных можно рассматривать как основной этап более широкого процесса, который часто называют процесс обнаружения знаний [18]. В дополнение к шагу сбораданных, сам по себе этот процесс включает также ряд других шагов. Для простоты, эти дополнительные меры можно условно разделить на предварительную обработку обнаруженных данных и знаний и постобработку. Мы используем термин предварительной обработки данных в общем смысле, в том числе следующие действия (среди прочих) [55]:

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

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

Некоторые данные методы очистки для сбораданных рассмотрены в [32], [59].

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

(d) Выбор признака - Этот шаг состоит из отбора подмножества признаков, важных для классификации среди всех оригинальных признаков. Это будет обсуждено в подразделе 2.3.1.

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

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

Рис. 1. Обзор процесса открытия знаний

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

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

Мотивацией для такого рода предварительной обработки является то, что несоответствующие признаки могут, так или иначе "перепутать" алгоритм сбора данных, приводя к открытию неточного или бесполезного знания [38]. Рассматривая чрезвычайный пример, предположите, что мы пытаемся предсказать, хорош ли клиент для выдачи кредита или плох, и предположите, что набор данных включает признак Имя_Клиента. Алгоритм сбора данных мог бы обнаружить слишком определенные правила формы:

IF (Имя_Клиента = “Какое-то_Имя”) THEN (Кредит = “Хорошо”).

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

Методы выбора атрибутов можно разделить на 2 подхода: фильтр и обертка. В фильтре, метод выбора атрибута не зависит от алгоритма сбора данных, которые должны применяться для выбранных атрибутов.

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

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

2.3.2 Постобработка обнаруженного знания. Знание полученные алгоритмом сбора данных, должны подвергнуться некоторой постобработке. Поскольку в этой главе мы концентрируемся на обнаружении знания выражаемых в IF-THEN предсказаниях правил, мы заинтересованы главным образом в постобработке обнаруженного набора правил.

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

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

Их поиск является скорее более трудной и амбициозной целью, как упомянуто в разделе 2.1.

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

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

Некоторые из этих методов основаны на идее сравнения обнаруженных правил по отношению к другим правилам, а не против убеждений пользователя. В этом случае основная идея состоит в том, что интересность правила, зависит не только от качества самого правила, но и от его сходство с другими правилами. Некоторые объективные показатели интересности правил рассмотрены в [26], [22], [23].

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

3. Генетические Алгоритмы (ГА) для Открытия Правил

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

В этом разделе мы обсуждаем несколько аспектов ГА для открытия правил. Этот раздел разделен на три части. Подраздел 3.1 обсуждает, как можно разработать индивидуальный прогноз, чтобы представить предсказание правила (if then). Подраздел 3.2 обсуждает, как генетические операторы могут быть приспособлены, чтобы обрабатывать индивидуальные представленные правила.

Раздел 3.3 обсуждаются некоторые вопросы, связанные с проектированием фитнес-функции для правил открытия.

3.1 Отдельное Представление

3.1.1 Мичиганский подход против Питтсбургского подхода. Генетические алгоритмы (ГА), разработанные для открытия правил можно разделить на две большие категории, основанные, на правилах кодирования в популяции особей ("хромосом"). В Мичиганском подходе каждую отдельную особь кодирует единственное правило предсказания, а в Питтсбургском подходе каждую отдельную особь кодирует множество правил предсказания. Нужно отметить, что некоторые авторы используют термин “мичиганский подход” в узком смысле, относятся только к классификатору систем [35], где взаимодействие правил принимают во внимание специфическим в своем роде методом кредитного назначения.

Тем не менее, мы используем термин " мичиганский подход " в широком смысле, для обозначения любого подхода, при котором каждый отдельный ГА кодирует одно правило прогнозирования. Выбор между этими двумя подходами сильно зависит от рода правила которые мы хотим обнаружить. Это связано с видом задачи интеллектуального анализа данных, которую мы решаем. Пусть задача классификации. Тогда нам, как правило, необходимо оценить качество набора правил в целом, а не качество одного правила. Иными словами, взаимодействие между правилами имеет важное значение. В этом случае, Питсбургский подход кажется более естественным. С другой стороны, Мичиганский подход может быть более естественным в других видах задач интеллектуального анализа данных. Пример задачи, где цель состоит в том, чтобы найти маленький набор высококачественных правил предсказания, и каждое правило часто оценивается независимо от других правил [49]. Другим примером является задача обнаружения редких событий [65].

Возвращаясь к классификации, которая находится в центре внимания этой главы, в двух словах плюсы и минусы каждого из подходов заключается в следующем. Питтсбургский подход непосредственно учитывает правила взаимодействия при вычислении фитнес функции особями. Однако, этот подход приводит к синтаксически более длинным особям, что приводит к тому, что фитнес-вычисления становяться более вычислительно дорогими. Кроме того, может потребоваться некоторых изменений в стандартных генетических операторах, чтобы справиться с довольно сложными особями. Примеры ГА для классификации, которые используют Питтсбургский подход являются GABIL [13], GIL [37], а HDPDCS [51].

В отличие от этого, в Мичиганском подходе особи более просты и синтаксически короче. Это уменьшать время, потраченное на вычисление фитнес функци и упрощение конструкции генетических операторов. Однако, это преимущество дорого обходиться. Прежде всего, так как фитнес функция оценивает качество каждого правила отдельно, теперь нелегко вычислить качество набора правил в целом - то есть принимать во внимание взаимодействия правил. Другая проблема состоит в том, что, так как мы хотим обнаружить ряд правил, а не единственное правило, мы не можем позволить популяции GA сходиться единственной особи, а именно это обычно происходит в стандартном га. Это вводит потребность в некотором особом методе [45], который, очевидно, не нужен случае Питсбургского подхода. Мы можем избежать потребности в этом особом методе в Мичиганском подходе, управляя GA, каждый раз когда обнаруживается новое правило. Недостаток этого подхода состоит в том, вычислительном отношении слишком дорогой. Примерами ГА для классификации, которые используют Мичиганский подход, является COGIN [30] и REGAL [28]. До сих пор мы видели, что особь GA может представить единственное правило или несколько правил, но мы еще не сказали, как правило(а) закодировано(ны) в геноме особи. Мы теперь поворачиваемся к этому вопросу. Для слудующего нашего обсуждения, предположим, что у правила есть форма “ЕСЛИ (IF) cond1 И... И condn ТОГДА (then)урок = ci“, где cond1... condn являются условиями значения атрибута (например, Пол = "М.") и ci, является уроком, предсказанным правилом. Мы делим наше обсуждение на две части, представление предшествующего правила ("If" часть правила) и представление правила утверждения ("then" часть правила). Эти два вопроса рассматриваются в следующих двух подразделах.

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

3.1.2 Представление Предшествующих Правил (связь условий). Простой подход для кодирования условий правил в особях это использование двоичного кодирования. Предположим, что данный атрибут может принимать K дискретных значений. Тогда мы можем кодировать условие на значение этого атрибута с помощью K бит. I-ое значение (I = 1 ,..., к) области признака является частью условия правила, если и только если i-тый разряд " включен" [13]. Например, предположим, что данное лицо представляет собой предшествующее правило с одним условием атрибут-значение, где атрибут Семейное положение и ее значения могут быть "холост", "в браке", "в разводе" и "вдовец". Тогда условие с участием этого атрибута будут закодированы в геноме по 4 бита. Если эти биты взять, скажем, значения "0 1 1 0", то они будут представлять следующие предшествующие правила:

IF (Семейное положение = " в браке " ИЛИ " в разводе")

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

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

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

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

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

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

(Возраст> 25) (Семейное положение = "Молодожены")

(имеет_работу = "да") (возраст <21)

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

IF (возраст> 25) и (возраст <21).

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

(Возраст> 25) (Семейное положение = " Молодожены ") (“пустой условие”)

(Возраст <21) (“пустое условие”) (имеет_работу = "да")

Теперь каждый признак занимает то же самое положение в этих двух особях, то есть признаки выровнены [21]. Следовательно, кроссовер произведет только действительных особей

Этот пример поднимает вопрос о том, как определить, для каждого гена, является ли он в нормально выраженном состоянии или пустом состоянии. Простой способ решения этой проблемы заключается в следующем. Пусть собираемые данные содержат M атрибутов. Тогда каждая особь содержит M генов, каждый из которых разделен на две части. Первый указывает на само условие (например, возраст> 25), тогда как вторая часть является битом. Если этот бит "1"\"0" условие включено \исключено из списка правил предшествующих представленной особи.

Другими словами, "пустых условиях" в приведенном выше примере представлены выключение этого бита. в вышеупомянутом примере представлены, выключая этот бит. Так как мы хотим предшествующие правила с переменным числом условий, этот бит обычно подвергается изменению под действием генетических операторов [43].

3.1.3 Представление Правило Последовательный (Прогноз класса). Вообще говоря, есть по крайней мере три способа представления предсказания класса ("Then " часть правила) в эволюционном алгоритме. Первая возможность кодировать его в геном особи [13], [30] – с возможным учетом его эволюции.

Вторая возможность связать всех особей популяции с теми же самыми предсказаниями класса, которые никогда не изменятся во время выполнения алгоритма. Следовательно, если мы хотим открыть для себя множество правил классификации прогнозирования K различных классов мы должны были бы запустить эволюционный алгоритм по крайней мере К раз, так что в I-й итерации, I = 1, .., K, алгоритм обнаруживает только правила прогнозирования I-го класса [37], [43].

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

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

3.2 генетические операторы для обнаружения правил .

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

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

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

3.2.2 Обобщение / Специализирущий кроссовер. Основная идея этого особого вида кроссовера является обобщение или специализирование данного правила, в зависимости от того, в настоящее время переобучению или недообучение данных, соответственно [27], [3]. Переобучению было кратко обсужденоя в разделах 2.2.1 и 2.3.1. недообучение является двойственная ситуация, в которой правило покрывает слишком много примеров подготовки, и поэтому должны быть специализированными. более полное обсуждение переобучению и недообученю в правиле индукции (независимых эволюционных алгоритмов) можно найти, например, В работе [57].

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

Затем обобщающий / специализирующийся оператор кроссовера может быть реализованы как логическое ИЛИ и как логическое И, соответственно. Это показано на Рис. 2, в случае, если вышеуказанная побитовые логические функции используются для вычисления значений битов между двумя пункты перехода через символ "|".

дети произведенные дети произведенные

родители обобщенным кроссовер, специализирующихся кроссовером

0 1 0 1 0 1 1 1 0 0 0 1

1 0 1 0 1 1 1 0 1 0 0 0

Рис. 2. Пример обобщения / специализирующихся кроссовер

3.2.3 Обобщенный/Специализирующийся- Оператор Условий. В предыдущем разделе мы видели, что оператор скрещивания могут быть изменены обобщить/специализируются правило. Однако, обобщение/специализация правило также может быть сделано таким образом, независимо от кроссовера. Предположим, например., что данная особь представляет собой правило, предшествующие с двумя атрибут-значение условия, а именно-опять же, существует неявный логических И соединяющий два условия в (1):

(Возраст > 25) (Семейное_положение = "1"). (1)

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

(Возраст > 21) (Семейное_ положение = "1"). (2)

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

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

3.3. Фитнес Функции для Правило поиска.

Напомним, что, как обсуждалось в разделе 2.1, в идеале обнаружили правила должны: (а)

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

Пусть правило имеет вид: IF THEN С, где это предшествующее (совместно с условиями) и С последующим (предсказания класса), как обсуждалось ранее. Очень простой способ измерения интеллектуального точность правило состоит в вычислении так называемого фактора доверия (CF) правило, определяется как:

CF = | A& C | / |A |,

где |A | является ряд примеров, удовлетворяющий всем условиям в предшествующие и | A& C | является ряд примеров, которые удовлетворяют обе предшествующие и класса предсказывает последующее C. Например, если правила охватывает 10 примеров (т. е. | | = 10), из которых 8 имеют класс предсказал по правилу (т. е. | A& C | = 8), то CF правило CF = 80%.

К сожалению, такие простые меры точности интеллектуального способствует правила подгонки данных. Например, если | A | = | & C | = 1, то CF правило 100%. Однако такие правила, скорее всего, представляющих особенность стиля в конкретном примере подготовки, и, вероятно, будет иметь плохую точности прогноза на тестовом наборе. Решение этой проблемы описано далее.

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

TP = Правдивых Положительных = количество примеров удовлетворяющих и С

FP = ложных срабатываний = количество примеров удовлетворяющих но не C

FN = ложноотрицательных = число примеров, не отвечающих но удовлетворяющих C

TN = Правдивых Минус = число примеров, не отвечающих ни C

Ясно, что выше значений TP и TN, и ниже значения FP и FN, лучше правила.

фактический класс С не C Предсказанный С TP FP

класс не C FN TN

Рис. 3. беспорядочная матрица для классификации правила

Отметим, что вышеупомянутые CF мера определяется, с точки зрения обозначения

рис. 3, по: CF = TP / (TP + FP). Теперь мы можем измерять интеллектуального точность правило, принимая во внимание не только ее CF, но и меру того, как "полный" правила, т.е. то, что доля примеров, имеющих предсказал класса C, что на самом деле, охватываемых правила предшествующее. Мера полноты правило, обозначается Comp, вычисляется по формуле:

Comp = TP / (TP + FN).

Для того чтобы объединить CF и Comp меры можно определить целевую функцию, такую как:

Fitness = CF ? Comp.

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

Fitness = W1 ? (CF ? Comp.) + W2 ? Simp,

где Simp является мерой правило простоты (нормированная на принимать значения в диапазоне от 0 .. 1) и W1 и W2 определяемых пользователем веса. Меры Simp может быть определена по-разному, в зависимости от предметной области и на пользователя. В общем, его значение обратно пропорционально числу условий в предшествующие правила - то есть, короче правило, тем проще.

Некоторые функции пригодности, которые принимают во внимание как интеллектуального точность и понятность правила описаны в литературе - см., например, [37], [28], [51], [21].

Нода и его коллеги [49] предложили фитнес-функция, которая принимает во внимание не только точности прогноза, но и мерой степени интересности из правила. Их GA следует подходить Мичиган и была разработана для решения задач моделирования зависимости. Их функции пригодности существенно взвешенной суммы двух слагаемых, где один срок меры интеллектуального точности правила и других долгосрочных мер степени интересности правила. Веса, присваиваемые каждому члену задаются пользователем. Другой целевой функции с участием мера правило интересности, точнее изменение известной J-мера, обсуждается в [4].

В вышеупомянутых проектов мера правило интересности объективно.

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

4. Генетические алгоритмы (ГА) для обнаружения знаний

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

4.1 генетических алгоритмов (ГА) для предварительной обработки данных

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

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

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

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

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

Такие альтернативные схемы кодирования была предложена Cherkauer и Shavlik [12]. В их схеме, каждый ген содержит либо отдельных атрибутов Ai, г = 1 ,..., т, или нет атрибута, обозначается 0. Длина отдельных фиксировано, но это не обязательно равна м, количество атрибутов. Атрибут выбирается, если оно происходит не реже одного раза в человека. Например, считая 10-атрибутов набора данных и 5-гена строки, отдельные "0 0 A8 A8 A4" представляет из вариантов решения, где только атрибуты A8 и A4 уделять алгоритм классификации.

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

В любом случае можно использовать ГА для оптимизации веса атрибутов непосредственно (присвоение, чтобы атрибуты вес были пропорциональный его актуальности), а не просто выбрать атрибуты. Этот подход был использован в частности для оптимизации атрибут весов для ближайшего соседа алгоритмов [39], [54].

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

В частности, результаты работы [42] показывают, что в больших масштабах атрибут выбора задач, где количество атрибутов больше, чем 100, ГА становится единственным практическим способом, чтобы получить разумную подмножества атрибутов.

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

Дальнейшее обсуждение использования генетических алгоритмов в атрибутах подбора можно найти в [5], [63], [31], [46].

5. Генетическое программирование (ГП) для Правило Обнаружения

ГП. можно рассматривать как более открытый поиск парадигмы, по сравнению с Г. А. [41], [6]. Поиск с помощью ГП может быть очень полезным в классификации и других задач прогнозирования, так как система может произвести много различных комбинаций атрибутов - с использованием нескольких различных функций, доступных в набор функций - которые не будут рассматриваться обычными ГА. Поэтому, даже если оригинальный набор атрибутов содержит не так много предсказательной силы сам по себе, система может эффективно создавать "Производные атрибуты" с большей предсказательной силой, применяя набор функций для оригинальных атрибутов. Потенциал ГП для создания этих производных атрибутов будет обсуждаться более подробно в разделе 6.

Прежде чем мы перейдем к этому разделу, мы обсудим следующие две проблемы в использовании GP для правила открытия, а именно отдельные представления (п. 5,1) и открытие понятные правила (п. 5,2).

5.1 индивидуальных представлений

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