Введення в DataMining Частина 3. Побудова дерев рішень

Попередня частина

© Наталія Єлманова
Стаття була опублікована в КомпьютерПресс 12 "2003



У попередній частині цієї статті ми розповіли про алгоритм кластеризації і розглянули його застосування на прикладі побудови антиспамового фільтра за допомогою реалізації цього алгоритму, що міститься в складі аналітичних служб Microsoft SQL Server 2000. У завершальній частині статті мова піде про застосування іншого алгоритму Data Mining, що носить назву Decision Trees (побудова дерев рішень).

У попередній частині цієї статті ми з'ясували, що представляють собою сучасні технології пошуку закономірностей у даних (Data Mining), а також коротко розглянули основні алгоритми здійснення подібного пошуку.

Що таке дерева рішень


Під терміном "дерева рішень" мається на увазі сімейство алгоритмів, заснованих на створенні ієрархічної структури, яка базується на відповіді "Так" або "Ні" на набір питань. Такі алгоритми досить популярні: в даний час вони реалізовані практично у всіх комерційних засобах Data Mining.

Як і розглянутий в попередній статті алгоритм кластеризації, сімейство алгоритмів побудови дерев рішень дозволяє передбачити значення якого-небудь параметра для заданого випадку (наприклад, поверне Чи людина вчасно виданий йому кредит) на основі великої кількості даних про інших подібних випадках (зокрема, на основі відомостей про інших осіб, яким видавалися кредити). Зазвичай алгоритми цього сімейства застосовуються для вирішення завдань, що дозволяють розділити всі вихідні дані на кілька дискретних груп.

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

Дія алгоритмів побудови дерев рішень базується на застосуванні методів регресійного і кореляційного аналізу. Один з найпопулярніших алгоритмів цього сімейства – CART (Classification and Regression Trees), заснований на поділі даних у гілки дерева на дві дочірні гілки, при цьому подальший поділ тієї чи іншої гілки залежить від того, чи багато вихідних даних описує дана гілка. Деякі інші подібні алгоритми дозволяють розділити гілку на більшу кількість дочірніх гілок. У даному випадку поділ проводиться на основі найбільш високого для описуваних гілкою даних коефіцієнта кореляції між параметром, згідно з яким відбувається поділ, і параметром, який надалі повинен бути передбачений.

А тепер розглянемо приклад реалізації подібного дерева за допомогою алгоритму Microsoft Decision Trees. Для цього нам буде потрібно Microsoft SQL Server 2000 (Enterprise Edition, Standard Edition або Personal Edition) з встановленими аналітичними службами, причому можна використовувати і ознайомчу версію.

Постановка завдання


Отже, розглянемо завдання визначення того, чи є отруйним знайдений гриб (такий приклад було розглянуто в одній з публікацій [1] і здався нам дуже вдалим). Дія нашого "визначника грибів", як і інших інструментів передбачення за допомогою Data Mining, буде складатися з двох процесів: навчання моделі (яке виконується одноразово і вимагає відносно багато часу) і прийняття рішення про те, чи відноситься конкретний гриб до категорії їстівних (що відбувається неодноразово).

В якості вихідних даних для навчання моделі ми скористаємося набором даних про більш ніж 8 тис. грибів, доступних у вигляді файлу у форматі CSV за адресою http://www.ics.uci.edu/ ~ mlearn / MLRepository.html (Ми вже користувалися іншим набором даних з цього сайту), який містить таблицю, де є колонка Edibility з двома можливими значеннями (Еdible – їстівний і poisonous – отруйний). Для спрощення роботи з цим набором даних переведемо його на російську мову і імпортуємо в яку-небудь СУБД, наприклад в Access або в Microsoft SQL Server. Створимо в цій таблиці автоматично заповнюване цілочисельне ключове поле – воно буде потрібно при створенні моделі Data Mining на основі цих даних (рис. 1).

рис. 1

Тепер можна приступити до створення самого дерева рішень.

Створення дерева рішень


Для створення дерева рішень слід запустити інструмент адміністрування аналітичних служб Microsoft SQL Server Analysis Manager. За допомогою Analysis Manager можна створити нову багатовимірну базу даних (Або скористатися тією, що була створена нами при розгляді попереднього прикладу) і описати там доступ до джерела вихідних даних (в нашому випадку – до бази даних Access; рис. 2).

рис. 2

Далі слід вибрати відповідну дочірню гілку Mining Models, з її контекстного меню вибрати пункт New Mining Model, а потім відповісти на питання майстра побудови моделей Data Mining. Зокрема, слід вказати, що для побудови моделі використовуються реляційні дані, що застосовується алгоритм Microsoft Decision Trees і що дані для аналізу розташовані в одній таблиці (при цьому потрібно вибрати її ім'я). Далі в таблиці необхідно вибрати поле, що є унікальним ідентифікатором кожного запису в наборі даних (case key), і нарешті, поля, значення яких в подальшому будуть передбачати (у нашому випадку – "їстівність"), а також поля, значення яких будуть використовуватися в якості параметрів для побудови гілок дерева. У нашому прикладі ми обрали всі 22 поля, присутні у вихідних даних (рис. 3).

рис. 3

Завершити створення моделі можна в редакторі Relational Mining Model Editor. Потім слід провести навчання моделі за допомогою вибору пункту меню Tools ® Process Mining Model.

Результати


Створене дерево рішень можна побачити, вибравши пункт View ® Content меню редактора Relational Mining Model Editor або пункт Browse з контекстного меню моделі в додатку Аnalysis Manager (рис. 4).

рис. 4

Ієрархія, представлена в отриманому дереві, створена на основі класифікації даних за правилом "Якщо …, то …"; при цьому насиченість кольору гілок залежить від кількості вихідних даних, що потрапили в зазначену гілка. У нашому випадку правила класифікації даних виглядають так:


Наступний рівень ієрархії доступний тільки для гілки, що містить дані про гриби без запаху, тому черговим параметром у цьому випадку виявляється колір спір (якщо спори зелені, то гриб отруйний), потім – Поверхня ніжки під кільцем, далі для грибів з лускатими ніжками – тип кілець, а для інших – розмір пластинки і колір капелюшка. Після цього приналежність гриба до категорії їстівних або отруйних стане очевидною.

Таким чином, алгоритм побудови дерев рішень дозволяє визначити набір значень характеристик, що дозволяють відокремити одну категорію даних від іншої (у даній ситуації – їстівні гриби від неїстівних); цей процес називають сегментацією.

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

За допомогою алгоритму побудови дерев рішень ми змогли з'ясувати, які характеристики впливають на пророкує параметр і який ступінь цього впливу. Для вивчення взаємозалежності параметрів можна скористатися інструментом Dependency Network Browser, доступним з контекстного меню моделі (рис. 5).

рис. 5

Ми бачимо, що з 22 параметрів, що описують зовнішній вид грибів, на їх їстівність впливають всього шість. При цьому за допомогою покажчика в лівій частині екрана ми можемо визначити, вплив яких саме з цих шести параметрів на пророкує значення буде найбільш істотним (6).

рис. 6

Слід підкреслити, що методи аналізу, засновані на побудові дерев рішень, найчастіше застосовуються для виявлення таких параметрів, які найбільш важливі для ухвалення однозначного рішення (наприклад, чи давати кредит фізичній або юридичній особі), а також у випадках, коли потрібно розбиття вихідних даних на очевидні групи з будь-якими ознаками. Розглянутий ж у попередній частині статті алгоритм кластеризації більше підходить у тих ситуаціях, коли залежність пророкує параметра від інших параметрів у вихідних даних не настільки очевидна.

На цьому ми завершуємо розгляд технології Data Mining, яка з кожним роком стає все більш затребуваною, а її реалізація з'являється в нових версіях багатьох популярних комерційних продуктів, таких як системи управління базами даних та засоби Business Intelligence. Тому через деякий час ми обов'язково повернемося до цієї теми.

Література



  1. Seidman.C. Data Mining with Microsoft SQL Server 2000: Technical Reference. – Microsoft Press, 2001.
  2. Ville.B., de. Microsoft Data Mining. – Digital Press, 2001

Додаткова інформація



Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*