Введення в Data Mining Частина 2

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

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



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

Тепер ми продовжимо розповідь про цю технологію і представимо вам деякі практичні аспекти її застосування на прикладі засобів Data Mining корпорації Microsoft – одного з претендентів на лідерство на ринку засобів розробки рішень Business Intelligence. Засоби Data Mining входять до складу аналітичних служб Microsoft SQL Server 2000, які, у свою чергу, включені в комплект постачання СУБД Microsoft SQL Server 2000, що робить Data Mining одним з найменш витратних способів вирішення задач подібного класу.

Засоби Data Mining корпорації Microsoft


Засоби Data Mining, що входять у комплект поставки Microsoft SQL Server 2000, містять реалізацію двох популярних алгоритмів:


Крім того, кошти Data Mining компанії Microsoft дозволяють підключати бібліотеки незалежних виробників, що реалізують інші алгоритми пошуку закономірностей. Згідно з відомостями, отриманими від менеджерів Microsoft, відповідальних за дану лінійку продуктів, наступна версія Microsoft SQL Server під кодовою назвою Yukon буде містити ще більш значний набір алгоритмів.

У цій статті ми розглянемо застосування кластеризації та алгоритму Microsoft Clustering. Однак перш з'ясуємо, що являє собою кластеризація.

Що таке кластеризація


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

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


рис. 1

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

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

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

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

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

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


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

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

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

рис. 2

Отже, можна приступити до створення кластерів.

Створення кластерів


Щоб створити кластерів слід запустити інструмент адміністрування аналітичних служб Microsoft SQL Server Analysis Manager (ми не будемо зупинятися на подробицях застосування даного інструменту; цікавляться цим питанням можуть звернутися до циклу статей "Введення в OLAP", опублікованому в нашому журналі у 2001 році, – знайти його можна на компакт-диску, прикладеному до цього номеру журналу). За допомогою Analysis Manager слід створити нову багатовимірну базу даних (назвемо її MyMiningData) і описати в ній доступ до джерела вихідних даних (в нашому випадку – до бази даних Access; рис. 3).

рис. 3

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

рис. 4

Завершити створення моделі можна в редакторі Relational Mining Model Editor, вказавши у властивостях моделі число кластерів (нехай воно буде дорівнює п'яти). Створення самих кластерів здійснюється за допомогою вибору пункту меню Tools ® Process Mining Model (рис. 5).

рис. 5

Нижче ми розглянемо, що представляють собою отримані кластери.

Результати кластеризації


об побачити результати кластеризації, потрібно вибрати пункт View ® Content в меню редактора Relational Mining Model Editor. Тут можна вивчити властивості отриманих п'яти кластерів, вибираючи їх послідовно в розділі Content Detail. У нашому прикладі найбільший інтерес представляють перші два з них – найбільші за об'ємом: 1806 і 1114 з 4681. В одному значенні поля IsSpam для всіх членів кластеру виявилося рівним нулю (що означає, що лист, параметри якого відповідають цьому кластеру, з високою ймовірністю не є спамом), в іншому – одиниці (це означає, що лист, параметри якого відповідають даному кластеру, з дуже високою ймовірністю є спамом; даний кластер зображений на рис. 6).

рис. 6

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

Таким чином, ми створили модель налаштування антиспамового фільтра. Застосування його цілком очевидно – прийняття рішення про те, чи відноситься лист до категорії спаму, залежить від того, в який з отриманих кластерів воно потрапить.

Може виникнути питання: чому при побудові даної моделі було вибрано саме п'ять кластерів? На практиці вибір числа кластерів багато в чому є ітеративним процесом. У даному випадку це було мінімальне число, при якому з'явилися кластери, дані в яких характеризувалися одним і тим же значенням параметра IsSpam, оскільки саме це дозволяє прийняти рішення, яке з великою часткою ймовірності виявиться правильним (якщо 1114 листів з 4681 з параметрами, характерними для даного кластеру, були спамом, то, швидше за все, 1115-е також виявиться спамом).

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

У наступній частині статті ми продовжимо розповідь про моделі і алгоритми Data Mining.

Література


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


Продовження статті


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


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

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

Ваш отзыв

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

*

*