Введення в 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
рис. 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

рис. 2

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

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


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

рис. 3

рис. 3

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

рис. 4

рис. 4

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

рис. 5

рис. 5

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

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


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

рис. 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>

*

*