Приклади формулювань задач при використанні методів

OLAP і Data Mining

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

Важливе положення Data Mining − нетривіальність розшукуваних шаблонів. Це означає, що знайдені шаблони повинні відображати неочевидні, несподівані (unexpected) регулярності в даних, становлять так звані “приховані знання” (hidden knowledge). Суспільство дійшло розуміння, що “сирі” дані (raw data) містять глибинний пласт знань, при грамотній розкопці якого можуть бути знайдені справжні самородки (рис. 2.21).

Рис. 2.21. Рівні знань, добування даних

У цілому технологію Data Mining достатньо точно визначає Григорій Пятецький-Шапіро − один із засновників цього напряму: Data Mining − це процес виявлення в “сирих” даних раніше невідомих, нетривіальних; практично корисних і доступних інтерпретації знань, необхідних для ухвалення рішень в різних сферах людської діяльності.

Сфера використання Data Mining нічим не обмежена − вона скрізь, де є які-небудь дані. Але в першу чергу методи Data Mining сьогодні, м'яко кажучи, заінтригували комерційні підприємства, що розгортають проекти на основі інформаційних СД (Data Warehousing). Досвід багатьох таких підприємств показує, що віддача від використовування Data Mining може досягати 1000%. Наприклад, відомі повідомлення про економічний ефект, що перевищив в 10-70 разів первинні витрати від 350 до 750 тис. дол. Відомі відомості про проект в 20 млн. дол., який окупився всього за 4 міс. Інший приклад − річна економія 700 тис. дол. за рахунок упровадження Data Mining в мережі універсамів у Великобританії.

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

Роздрібна торгівля

Підприємства роздрібної торгівлі на теперішній час збирають докладну інформацію про кожну окрему покупку, використовуючи кредитні картки з маркою магазина і комп'ютеризовані системи контролю. Ось типові задачі, які можна вирішувати за допомогою Data Mining у сфері роздрібної торгівлі:

• аналізування “споживацького кошика” (схожості) призначено для виявлення товарів, які покупці прагнуть придбавати разом. Знання складу споживацького кошика необхідне для покращання реклами, вироблення стратегії створення запасів товарів і способів їх розкладки в торгових залах тощо;

• дослідження тимчасових шаблонів допомагає торговим підприємствам ухвалювати рішення про створення товарних запасів і дає відповіді на питання типу “Якщо сьогодні покупець придбав відеокамеру, то через який час він найімовірніше купить нові батареї і плівку?”;

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

Банківська справа

Досягнення технології Data Mining використовуються в банківській справі для вирішення наступних поширених задач:

• виявлення шахрайства з кредитними картками. Шляхом аналізу минулих транзакцій, які згодом виявилися шахрайськими, банк виявляє деякі стереотипи такого шахрайства;

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

• прогнозування змін клієнтури. Data Mining допомагає банкам будувати прогнозні моделі цінності своїх клієнтів і відповідним чином обслуговувати кожну категорію.

Телекомунікації

У галузі телекомунікацій методи Data Mining допомагають компаніям енергійніше просувати свої програми маркетингу і ціноутворення з метою утримання існуючих клієнтів і привертання нових. Серед типових заходів наголосимо на наступних:

• аналізування записів про докладні характеристики викликів. Призначення такого аналізування − виявлення категорій клієнтів з схожими стереотипами користування їх послугами і розробка привабливих наборів цін і послуг;

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

Страхування

Страхові компанії протягом ряду років накопичують великі обсяги даних. Тут обширне поле діяльності для методів Data Mining:

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

• аналізування ризику. Шляхом виявлення поєднань чинників, пов'язаних із сплаченими заявами, страховики можуть зменшити свої втрати за зобов'язаннями.

Data Mining може застосовуватися в безлічі інших галузей:

• розвиток автомобільної промисловості. При збірці автомобілів виробники повинні враховувати вимоги кожного окремого клієнта, тому їм потрібні можливість прогнозування популярності певних характеристик і знання того, які характеристики звичайно замовляються разом;

• політика гарантій. Виробникам потрібно передбачати число клієнтів, які подадуть гарантійні заявки, і середню вартість заявок;

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

Медицина

Відомо багато ЕС для постановки медичних діагнозів. Вони побудовані головним чином на основі правил, що описують поєднання різних симптомів різних захворювань. За допомогою таких правил визнають не тільки, на що хворий пацієнт, але і як потрібно його лікувати. Правила допомагають вибирати засоби медикаментозної дії, визначати лікування-протипоказання, орієнтуватися в лікувальних процедурах, створювати умови найефективнішого лікування, передбачати результати призначеного курсу лікування і т. ін. Технології Data Mining дозволяють знаходити в медичних даних шаблони, що становлять основу вказаних правил.

Молекулярна генетика і генна інженерія

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

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

Прикладна хімія

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

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

Виділяють п'ять стандартних типів закономірностей, які дозволяють виявляти методи Data Mining: асоціація, послідовність, класифікація, кластеризація і прогнозування.

Асоціація має місце в тому випадку, якщо декілька подій взаємопов'язані. Наприклад, дослідження, проведене в супермаркеті, може показати, що 65% покупців кукурудзяні чіпси, беруть також і “кока-колу”, а за наявності знижки за такий комплект “колу” купують в 85% випадках. Маючи в розпорядженні відомості про подібну асоціацію, менеджерам легко оцінити, наскільки дієва знижка, надана на товари.

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

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

Кластеризація відрізняється від класифікації тим, що самі групи наперед не задані. З допомогою кластеризації засоби Data Mining самостійно виділяють різні однорідні групи даних.

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

Дерева рішень є одним з найпопулярніших підходів до рішення задач Data Mining. Вони створюють ієрархічну структуру класифікованих правил типу “ЯКЩО... ТО...” (if-then), що має вид “дерева”. Для ухвалення рішення, до якого класу віднести деякий об'єкт або ситуацію, вимагається відповісти на питання, що стоять у вузлах цього “дерева”, починаючи з його коріння. Питання мають вигляд “значення параметра А більше x?”. Якщо відповідь позитивна, здійснюється перехід до правого вузла наступного рівня; якщо негативний − то до лівого вузла; потім знову слідує питання, пов'язане з відповідним вузлом.

Популярність підходу пов'язана з наочністю і зрозумілістю. Але “дерева рішень” принципово не здатні знаходити “кращі” (якнайповніші та точніші) правила в даних. Вони реалізують наївний принцип послідовного перегляду ознак і “чіпляють” фактично осколки справжніх закономірностей, створюючи лише ілюзію логічного висновку. Разом з тим, більшість систем використовує саме цей метод. Найвідомішими є See5/С5.0 (RuleQuest, Австралія), Clementine (Integral Solutions, Великобританія), SIPINA (University Lyon, Франція), IDIS (Information Discovery, США), KnowledgeSeeker (ANGOSS, Канада). Вартість цих систем варіюється від 1 до 10 тис. дол.

Рис. 2.22. Обробка банківської інформації системою KnowledgeSeeker

Еволюційне програмування. Проілюструємо сучасний стан даного підходу на прикладі системи PolyAnalyst − вітчизняній розробці, що одержала сьогодні загальне визнання на ринку Data Mining. В даній системі гіпотези про вигляд залежності цільової змінної від інших змінних реалізується у вигляді програм деякою внутрішньою мовою програмування. Процес побудови програм будується як еволюція в світі програм (цим підхід трохи схожий на генетичні алгоритми). Коли система знаходить програму, що більш-менш задовільно виражає шукану залежність, вона починає вносити в неї невеликі модифікації і відбирає серед побудованих дочірніх програм ті, які підвищують точність. Таким чином, система “вирощує” декілька генетичних ліній програм, які конкурують між собою в точності виразу шуканої залежності. Спеціальний модуль системи PolyAnalyst перекладає знайдені залежності з внутрішньої мови системи на зрозумілу користувачу мову (математичні формули, таблиці й ін.).

Інший напрям еволюційного програмування пов'язаний з пошуком залежності цільових змінних від інших у формі функцій якогось певного вигляду. Наприклад, в одному з найвдаліших алгоритмів цього типу − методі групового обліку аргументів (МГОА) залежність шукають у формі поліномів. В даний час з систем, що продаються в Росії, МГОА реалізований в системі NeuroShell компанії Ward Systems Group.

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

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

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

Генетичні алгоритми мають ряд недоліків. Критерій відбору хромосом і використовувані процедури є евристичними і далеко не гарантують знаходження “кращого” рішення. Як і в реальному житті, еволюцію може “заклинити” на якій-небудь непродуктивній гілці. І, навпаки, можна привести приклади, як два неперспективних батьки, які будуть виключені з еволюції генетичним алгоритмом, виявляються здатними надати високоефективного нащадка. Це особливо стає помітно при вирішенні високорозмірних задач з складними внутрішніми зв'язками. Прикладом може служити система GeneHunter фірми Ward Systems Group.

Алгоритми обмеженого перебору. Алгоритми обмеженого перебору були запропоновані в середині 60-х років XX ст. М.М. Бонгардом для пошуку логічних закономірностей в даних. З тих пір вони продемонстрували свою ефективність при рішенні безліччі задач з самих різних сфер.

Ці алгоритми обчислюють частоти комбінацій простих логічних подій в підгрупах даних. Приклади простих логічних подій: X = а; X < b; X >а; а < X < b і ін., де X − якийсь параметр; “a” і “b” − константи. Обмеженням служить довжина комбінації простих логічних подій (наприклад 3). На підставі аналізу обчислених частот робиться висновок про корисність тієї або іншої комбінації для встановлення асоціації в даних, для класифікації, прогнозування й ін.

Найяскравішим сучасним представником наведеного підходу є система WizWhy підприємства WizSoft. Хоча автор системи Абрам Мейдан не розкриває специфіку алгоритму, встановленого в основу роботи WizWhy, за наслідками ретельного тестування системи були зроблені висновки про наявність тут обмеженого перебору.

Автор WizWhy стверджує, що його система знаходить всі логічні if-then правила в даних. Насправді це, звичайно, не так. По-перше, максимальна довжина комбінації в if-then правила в системі WizWhy рівна 6, і, по-друге, з самого початку роботи алгоритму проводиться евристичний пошук простих логічних подій, на яких потім будується весь подальший аналіз. Зрозумівши ці особливості WizWhy, неважко було запропонувати просту тестову задачу, яку система не змогла взагалі вирішити. Інший момент − система видає рішення за прийнятний час тільки для порівняно невеликої розмірності даних.

Проте, система WizWhy є на теперішній час одним з лідерів на ринку продуктів Data Mining. Це не позбавлено підстав. Система постійно демонструє вищі показники при рішенні практичних задач, ніж вся решта алгоритмів (рис. 2.23).

Рис. 2.23. Система WizWhy, яка знайшла правила, що пояснюють врожайність деяких сільськогосподарських ділянок

Системи для візуалізації багатовимірних даних. Тою чи іншою мірою засоби для графічного відображення даних підтримуються всіма системами Data Mining. Разом з тим, вельми значну частку ринку займають системи, що спеціалізуються винятково на цій функції. Прикладом тут може служити програма DataMiner 3D словацької фірми Dimension5 (5-е вимірювання).

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

Рис. 2.24. Візуалізація даних системою DataMiner  3D

Ринок систем Data Mining експоненціально розвивається. В цьому розвитку беруть участь практично всі найбільші корпорації. Зокрема, Microsoft безпосередньо керує великим сектором даного ринку (видає спеціальний журнал, проводить конференції, розробляє власний продукт).

Системи Data Mining застосовуються по двох основних напрямках: 1) як масовий продукт для бізнес-додатків; 2) як інструменти для проведення унікальних досліджень (генетика, хімія, медицина й ін.). В даний час вартість масового продукту від $1000 до $10 000. Кількість інсталяцій масових продуктів, судячи за наявними відомостями, сьогодні досягає десятків тисяч. Лідери Data Mining пов'язують майбутнє цих систем з використанням їх як інтелектуальних додатків, вбудованих в корпоративні СД.

Не зважаючи на велику кількість методів Data Mining, пріоритет поступово все більш зміщується у бік логічних алгоритмів пошуку в даних if-then правил. З їх допомогою вирішуються задачі прогнозування, класифікації, розпізнавання образів, сегментації БД, витягання з даних “прихованих” знань, інтерпретації даних, встановлення асоціацій в БД й ін. Результати таких алгоритмів ефективні та легко інтерпретуються.

Разом з тим, основною проблемою логічних методів виявлення закономірностей є проблема перебору варіантів за прийнятний час. Відомі методи або штучно обмежують такий перебір (алгоритми КОРА, WizWhy), або будують дерева рішень (алгоритми CART, CHAID, ID3, See5, Sipina й ін.), що мають принципові обмеження ефективності пошуку if-then правил. Інші проблеми пов'язані з тим, що відомі методи пошуку логічних правил не підтримують функцію узагальнення знайдених правил і функцію пошуку оптимальної композиції таких правил. Вдале рішення вказаних проблем може скласти предмет нових конкурентних розробок.