Учебное пособие по курсу интеллектуальные системы (Часть 1) Москва 2003

Вопросы для самопроверки

1. 
   Сформулируйте особенности анализа данных на основе вычисления средних.
   
2. 
   Поясните особенности метода визуализации.
   
3. 
   Сформулируйте, какие преимущества дает представление записей в виде точек в многомерном пространстве данных.
   
4. 
   Сформулируйте отличия интерактивной аналитической обработки данных (OLAP) от традиционной обработки транзакций (OLTP).
   
5. 
   Опишите алгоритм k-ближайшего соседа.
   

Литература к главе 2

1. P.Adriaans, D.Zantinge. Data Mining.Addison Wesley Longman, 1996, 158 p.
2. Попов Э.В., Фоминых И.Б. Извлечение знаний из баз данных. - В кн.: Сборник трудов 5-ой национальной конференции "Искусственный интеллект-96", Казань, 1996.
3. J.Han, M.Kamber. Data Mining. Concept and Techniques. Morgan Kaufman Publishers, 2000, 550 p.

ГЛАВА 3. ИНТЕЛЛЕКТУАЛЬНЫЕ МЕТОДЫ ИЗВЛЕЧЕНИЯ ЗНАНИЙ

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

Дерево решений это древовидная структура, представляющая совокупность решений [1]. Деревья решений разбивают данные на группы на основе значений переменных, в результате чего возникает иерархия операторов "ЕСЛИ - ТО", которые классифицируют данные.
Если существует таблица, содержащая данные о поведении заказчика, и необходимо классифицировать эти данные или сделать предсказание, то можно обнаружить, что задачи классификации и предсказания очень тесно связаны. Попытка предсказать, какой тип поведения покажет определенный заказчик, фактически влечет предположение, что заказчик принадлежит определенному типу группы заказчиков и поэтому покажет этот определенный тип поведения.
Наша база данных содержит такие атрибуты как возраст, доход и кредит; если необходимо предсказать определенный тип поведения заказчика, можно спросить, какой из этих атрибутов дает нам больше информации. Если мы хотим предсказывать, кто будет покупать автомобильный журнал, что поможет нам больше - возраст или доход человека? Возможно, что более важен возраст, что влечет предположение, что только на основе знаний о возрасте индивидуума, мы способны предсказать, будет ли он или она покупать автомобильный журнал.
Если дело обстоит так, то следующее, что необходимо сделать - разделить множество значений этого атрибута на два подмножества, то есть необходимо исследовать, существует ли некоторый возрастной порог, отделяющий покупателей автомобильного журнала от не покупателей. Таким образом, можно начать с первого атрибута, найти определенный порог, продолжить со следующим атрибутом, найти порог для него и повторять этот процесс до тех пор, пока не будет построена правильная классификация заказчиков, таким образом, создав дерево решений для нашей БД. Существуют много алгоритмов, которые могут создавать такое дерево решений автоматически; они достаточно эффективны, так как имеют вычислительную сложность n (log n). На рис. 3.1 показаны результаты применения древовидного индуктивного алгоритма на наборе данных.

Возраст  44.50 99 %

Возраст  = 44.50 38 %

Рис. 3.1 Простое дерево решений для автомобильного журнала.

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

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

Дерево решений разделяет группу людей с возрастом более 44.5 года (где почти нет читателей) на две подгруппы: в одной с возрастом между 44.5 и 48.5, где все еще существует 8 % читателей автомобильного журнала. В то время как выше 48.5 лет интерес к этому журналу полностью отсутствует, так что эта ветвь не исследовалась алгоритмом далее. Для группы ниже 44.5 лет доход, кажется, является следующим важным атрибутом. Люди с несколько более высоким доходом (выше 34.5) не читают этот журнал, но ниже этого порога дохода, возраст внезапно снова становится решающим атрибутом: все люди в этой группе ниже возраста 31.5 подписываются на этот журнал.

Один из выводов, который можно сделать из этого дерева - это то, что люди с доходом ниже 34.5 и возрастом ниже 31.5 лет с очень большой вероятностью заинтересованы автомобильным журналом, в то время как люди с доходом более чем 34.5 и возрастом ниже 44.5 вероятно не будут им интересоваться. Это говорит о том, что дерево глубиной четыре оптимально, так как дальнейшее расширение дерева не прибавляет намного больше информации.
Древовидные индуктивные алгоритмы очень хорошо масштабируются для больших наборов данных. К тому же они сравнительно про­сты и по­нятны пользователям. В то же вре­мя нель­зя ска­зать, что де­ре­вья реше­ний всегда действуют безотказно: для оп­ре­де­лен­ных ти­пов дан­ных, на­при­мер, при об­ра­бот­ке не­пре­рыв­ных ве­ли­чин они мо­гут ока­зать­ся не­при­ем­ле­мы­ми. По­ми­мо то­го, набор операторов «ЕСЛИ  ТО» ино­гда бы­ва­ет столь же не­по­нят­ным, как и ней­рон­ная сеть, осо­бен­но ес­ли спи­сок ус­ло­вий длин­ный и слож­ный.
В среднем древовидный индуктивный алгоритм работает лучше, чем наивное предсказание (см. раздел 2.1) на нашем наборе данных и только в случае комиксов существует небольшое отклонение. Интересно, что в случае предсказания по поводу журнала о доме, система не получает хорошего дерева решения (рис. 3.3).

Рис. 3.3. Дерево решений для журнала “Дом”.

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

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