Системи Data Mining

Размещено на http://www.allbest.ru

Министерство образования и науки РФ

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

Пермский государственный технический университет

Кафедра микропроцессорных средств автоматизации

Реферат по дисциплине

«Интегрированные системы проектирования и управления»

на тему «Системи Data Mining»

Пермь 2009

Введение

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

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

1. Відомості про Data Mining

Data Mining переводиться як "видобуток " або " розкопка даних". Нерідко поруч з Data Mining зустрічаються слова "виявлення знань у базах даних" ( knowledge discovery in databases ) і " інтелектуальний аналіз даних". Їх можна вважати синонімами Data Mining. Виникнення всіх зазначених термінів пов'язане з новим витком у розвитку засобів і методів обрамлення даних.

До початку 90 -х років, здавалося, не було особливої потреби переосмислювати ситуацію в цій галузі. Все йшло своєю чергою в рамках напрямку, званого прикладної статистикою. Теоретики проводили конференції та семінари, писали значні статті та монографії, насиченим аналітичними викладками.

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

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

Специфіка сучасних вимог до такої переробки наступні:

* Дані мають необмежений обсяг

* Дані є різнорідними ( кількісними, якісними, текстовими )

* Результати мають бути конкретні і зрозумілі

* Інструменти для обробки сирих даних повинні бути прості у використанні

Традиційна математична статистика, довгий час претендувала на роль основного інструменту аналізу даних, відверто спасувала перед обличчям виниклих проблем. Глав -ва причина - концепція усереднення за вибіркою, що приводить до операцій над фіктивні -ми величинами ( типу середньої температури пацієнтів по лікарні, середньої висоти будинку на вулиці, що складається з палаців і халуп і т.п.). Методи математичної статистики виявилися корисними головним чином для перевірки заздалегідь сформульованих гіпотез (verification-driven data mining) і для "грубого" розвідувального аналізу, що становить основу оперативної аналітичної обробки даних (online analytical processing, OLAP). В основу сучасної технології Data Mining ( discovery - driven data mining ) покладено концепцію шаблонів ( патернів), що відображають фрагменти багатоаспектних взаємин в даних. Ці шаблони представляють собою закономірності, властиві підвибірках дан-них, які можуть бути компактно виражені у зрозумілій людині формі. Пошук шаблонів проводиться методами, що не обмеженими рамками апріорних припущень про структуру вибірці і вигляді розподілів значень анали - зіруемого показників. Приклади завдань на такий пошук при використанні Data Mining наведено в табл. 1.

Таблиця 1 Приклади формулювань завдань при використанні методів OLAP і Data Mining

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

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

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

В цілому технологію Data Mining досить точно визначає Григорій Піатецкій-Шапіро - один із засновників цього напрямку:

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

2. Застосування Data mining

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

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

data mining бізнес

2.1 Деякі бізнес-додатки Data Mining

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

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

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

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

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

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

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

виявлення шахрайства з кредитними картками. Шляхом аналізу минулих тран- ЗАКЦ, які згодом виявилися шахрайськими, банк виявляє некото -які стереотипи такого шахрайства.

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

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

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

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

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

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

Страхування

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

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

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

Інші програми в бізнесі

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

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

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

2.2 Спеціальні додатки

Медицина

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

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

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

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

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

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

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

3. Типи закономірностей

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

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

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

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

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

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

4. Класи систем Data Mining

Data Mining є мультидисциплінарної областю, виникла і розвивається на базі досягнень прикладної статистики, розпізнавання образів, методів штучного інтелекту, теорії баз даних та ін (рис. 3 ). Звідси велика кількість методів і алгоритмів, реалізованих у різних діючих системах Data Mining. Багато хто з таких систем інтегрують в собі відразу декілька підходів. Проте, як правило, в кожній системі є якась ключова компонента, на яку робиться головна ставка. Нижче наводиться класифікація зазначених ключових компонент на основі роботи[6]. Виділеним класам дається коротка характериста

Рис. 2 Data Mining - мультидисциплінарна область

4.1 Предметно-орієнтовані аналітичні системи

Предметно -орієнтовані аналітичні системи дуже різноманітні. Найбільш широ - кий підклас таких систем, що одержав поширення в галузі дослідження фінансовим-вих ринків, носить назву " технічний аналіз". Він являє собою сукупність декількох десятків методів прогнозу динаміки цін і вибору оптимальної структури інвестиційного портфеля, заснованих на різних емпіричних моделях динаміки ринку. Ці методи часто використовують нескладний статистичний апарат, але максимально враховують сформовану своїй області специфіку (професійний мова, системи різних індексів і пр. ). На ринку є безліч програм цього класу. Як правило, вони досить дешеві ( зазвичай $ 300-1000).

4.2 Статистичні пакети

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

Недоліком систем цього класу вважають вимогу до спеціальної підготовки користувача. Також відзначають, що потужні сучасні статистичні пакети є занадто " ваговитими " для масового застосування у фінансах і бізнесі. До того ж часто ці системи досить дорогі - від $ 1000 до $ 15000.

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

Як приклади найбільш потужних і поширених статистичних пакетів можна назвати SAS (компанія SAS Institute ), SPSS ( SPSS ), STATGRAPICS ( Manugistics ), STATISTICA, STADIA та інші.

4.3 Нейронні мережі

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

Основним недоліком нейромережевої парадигми є необхідність мати дуже великий обсяг навчальної вибірки.

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

Приклади нейромережевих систем - BrainMaker (CSS), NeuroShell ( Ward Systems Group ), OWL ( HyperLogic ). Вартість їх досить значна: $ 1500-8000.

Рис. 5 Поліноміальна нейросеть

4.4 Системи міркувань на основі аналогічних випадків

Ідея систем case based reasoning - CBR - на перший погляд вкрай проста. Для того щоб зробити прогноз на майбутнє чи вибрати правильне рішення, ці системи знаходять в про- Шломо близькі аналоги наявної ситуації і вибирають ту ж відповідь, який був для них правильним. Тому цей метод ще називають методом " найближчого сусіда " ( nearest neighbour ). Останнім часом поширення отримав також термін memory based reasoning, який акцентує увагу, що рішення приймається на підставі всієї ін- формації, накопиченої в пам'яті.

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

Інший мінус полягає в свавіллі, який допускають системи CBR при виборі міри "близькості ". Від цієї міри найрішучішим чином залежить обсяг безлічі прецеденти -тов, які потрібно зберігати в пам'яті для досягнення задовільною класифікації чи прогнозу [ 7 ].

Приклади систем, що використовують CBR, - KATE tools ( Acknosoft, Франція ), Pattern Recognition Workbench ( Unica, США ).

4.5Деревья рішень (decision trees)

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

Популярність підходу пов'язана як би з наочністю і зрозумілістю. Але дерева рішень принципово не здатні знаходити " кращі " ( найбільш повні і точні ) правила в даних.

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

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

4.6 Еволюційне програмування

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

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

Вартість систем до $ 5000.

4.7 Генетичні алгоритми

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

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

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

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

Прикладом може служити система GeneHunter фірми Ward Systems Group. Його вартість - близько $ 1000.

4.8 Алгоритми обмеженого перебору

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

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

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

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

Проте, система WizWhy є на сьогоднішній день одним з лідерів на ринку продуктів Data Mining. Це не позбавлене підстав. Система постійно демонструє більш високі показники при вирішенні практичних завдань, ніж всі інші алгоритми. Вар-тість системи близько $ 4000, кількість продажів - 30 000.

4.9 Системи для візуалізації багатовимірних даних

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

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

5. Система PolyAnalyst

Призначення системи. Система PolyAnalyst призначена для автоматичного і напівавт -автоматично аналізу числових баз даних і отримання з сирих даних практично по залізних знань. PolyAnalyst знаходить багатофакторні залежності між змінними в базі даних, автоматично будує і тестує багатовимірні нелінійні моделі, висловлю ющіе знайдені залежності, виводить класифікаційні правила по навчальним прикладам, знаходить в даних багатовимірні кластери, будує алгоритми рішень. Розробник системи PolyAnalyst - російська компанія Megaputer Intelligence або " Мегапьютер " [ 8 ].

Архітектура системи

За своєю природою PolyAnalyst є клієнт- серверним додатком. Користувач працюе з клієнтською програмою PolyAnalyst Workplace. Математичні модулі виділені в серверну частину - PolyAnalyst Knowledge Server. Така архітектура надає есте - ственную можливість для масштабування системи: від однокористувацького варіанту до корпоративного рішення з декількома серверами. PolyAnalyst написаний на мові С + + з використанням специфікації Microsoft's COM ( ActiveX ). Ця специфікація встановлює стандарт комунікації між програмними компонентами. Архітектура системи PolyAnalyst представлена на рис. 9.



Рис. 9 Архітектура системи PolyAnalyst

Математичні модулі (Exploration Engines) і багато інших компоненти PolyAnalyst ви-делени в окремі динамічні бібліотеки і доступні з інших додатків. Це дає можливість інтегрувати математику PolyAnalyst в існуючі ІС, наприклад, в CRM-або ERP-системи.

Загальносистемні характеристики PolyAnalyst

Типи даних

PolyAnalyst працює з різними типами даних. Це : числа, булеві змінні ( yes / no ), ка - тегоріальние змінні, текстові рядки, дати, а також вільний англійський текст.

Доступ до даних

PolyAnalyst може отримувати вихідні дані з різних джерел. Це : текстові файли з роздільником "кома " (. Csv ), файли Microsoft Excel 97 / 2000, будь ODBC - совме - Стіма СУБД, SAS data files, Oracle Express, IBM Visual Warehouse.

Підтримка OLE DB for Data Mining

Версія 4.6 PolyAnalyst підтримує специфікацію Microsoft OLE DB for Data Mining ( Ver - sion 1.0). При виконанні досліджень для більшості математичних модулів ( LR, FD, CL, FC, DT, DF, FL, PN, BA, TB ) можна створювати так звані " Mining Models " (MM). Після завершення аналізу ці моделі можна застосовувати до зовнішніх даних через стандартні інтерфейси OLE DB або ADO з інших програм або скриптів, що підтримують створення ADO або COM- об'єктів. Застосування моделі здійснюється за допомогою виконання SQL - команд ( Розширення SQL for DM ). Mining Models можна також експортувати в PMML. У планах розвитку програми намічається забезпечити інтеграцію " PolyAnalyst DataMining Provider " з Microsoft Analysis Services (у складі SQL Server 2000).

In - place Data Mining

PolyAnalyst підтримує запуск досліджень на зовнішніх даних через OLE DB інтер- фейси при без завантаження цих даних в проект PA. При виконанні дослідження PolyAnalyst отримує дані порціями через виконання SQL - запитів до зовнішніх дже-рел даних. Це дозволяє подолати обмеження пам'яті при дослідженні великих масивів даних.

Даний процес продемонстрований на рис. 10

Рис. 10 In-place Data Mining

PolyAnalyst Scheduler - режим пакетної обробки

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

У таблиці 2 описано сімейство продуктів PolyAnalyst6 : продукти і відповідні конфігурації системи.

Таблиця 2. Сімейство продуктів PolyAnalyst

Продукт	Конфигурация системы
Локальные продукты
PolyAnalyst 4.6, однопользовательская версия	Математические модули: FL, FD, PN, FC, BA, ТВ, MB, CL, DS, DT, DF, LR, LA, TA, TC, LT, SS. Пакетная обработка, поддержка OLE DB. Платформа - MS Windows NT/2000/XP
PolyAnalyst 3.5 Professional (русс.)	Математические модули: FL, FD, PN, FC, CL, DS, LR, SS. Платформа - MS Windows NT/2000/XP
PolyAnalyst 3.5 Power (русс.)	Математические модули: FD, PN, FC, CL, DS, LR, SS. Платформа - MS Windows 98/NT/2000/XP
PolyAnalyst 3.5 Lite - студенческая версия (русс.)	Математические модули: FD, FC, CL, DS, LR, SS. Платформа - MS Windows 98/NT/2000/XP
Сетевые продукты
PolyAnalyst Knowledge Server 4.6, сетевая версия	Математические модули: FL, FD, PN, FC, BA, ТВ, MB, CL, DS, DT, DF, LR, LA, TA, TC, LT, SS. Пакетная обработка, поддержка OLE DB, In-Place Data Mining. Серверная часть - MS Windows NT/2000/XP server, клиентская часть - MS Windows 98/NT/2000/XP. Клиент/серверная версия системы
Средства разработки
PolyAnalyst COM - SDK для создания собственных приложений для Data Mining	Набор COM-объектов, библиотеки, документация для разработчиков

6. Инструмент KXEN

Аббревиатура KXEN означает "Knowledge eXtraction Engines" - "движки" для извлечения знаний.

Сразу следует сказать, что разработка KXEN имеет особый подход к анализу данных [9]. В KXEN нет деревьев решений, нейронных сетей и других популярных техник.

KXEN - это инструмент для моделирования, который позволяет говорить об эволюции Data Mining и реинжиниринге аналитического процесса в организации в целом.

В основе этих утверждений лежат достижения современной математики и принципиально иной подход к изучению явлений в бизнесе.

Следует отметить, что все происходящее внутри KXEN сильно отличается (по крайней мере, по своей философии) от того, что мы привыкли считать традиционным Data Mining.

Бизнес-моделирование KXEN - это анализ деятельности компании и ее окружения путем построения математических моделей. Он используется в тех случаях, когда необходимо понять взаимосвязь между различными событиями и выявить ключевые движущие силы и закономерности в поведении интересующих нас объектов или процессов.

KXEN охватывает четыре основных типа аналитических задач:

Задачи регрессии/классификации (в т.ч. определение вкладов переменных);

Задачи сегментации/кластеризации;

Анализ временных рядов;

Поиск ассоциативных правил (анализ потребительской корзины).

Построенная модель в результате становится механизмом анализа, т.е. частью бизнес-процесса организации. Главная идея здесь - на основе построенных моделей создать систему "сквозного" анализа происходящих процессов, позволяющую автоматически производить их оценку и строить прогнозы в режиме реального времени (по мере того, как те или иные операции фиксируются учетными системами организации).

Реинжиниринг аналитического процесса

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

Особенность KXEN заключается в том, что заложенный в него математический аппарат (на основе Теории минимизации структурного риска Владимира Вапника) позволяет практически полностью автоматизировать процесс построения моделей и на порядок увеличить скорость проводимого анализа. Отличия традиционного процесса Data Mining и подхода KXEN приведены на рис. 11.

Рис. 11 Отличия традиционного процесса Data Mining и подхода KXEN

Таким образом, построение модели в KXEN из исследовательского проекта превращается в функцию предсказательного анализа в режиме on-line в формате "вопрос-ответ". Причем ответы даются в тех же терминах, в которых был сформулирован вопрос, и задача пользователя сводится к тому, чтобы задавать нужные вопросы и указывать данные для анализа.

Среди преимуществ KXEN можно назвать:

Удобная и безопасная работа с данными: данные никуда не перегружаются, KXEN обрабатывает их строка за строкой (текстовые файлы или интеграция с DB2, Oracle и MS SQL Server, в т.ч. через ODBC);

Наглядность результатов моделирования, легкость для понимания: графическое отображение моделей + score-карты;

Широкие возможности применения моделей: автоматическая генерация кода моделей на языках С++, XML, PMML, HTML, AWK, SQL, JAVA, VB, SAS, при этом модель сможет работать автономно.

Структура KXEN Analytic Framework Version 3.0

KXEN Analytic Framework по своей сути не является монолитным приложением, а выполняет роль компонента, который встраивается в существующую программную среду. Этот "движок" может быть подключен к DBMS-системам (например, Oracle или MS SQL-Server) через протоколы ODBS.

KXEN Analytic Framework представляет собой набор модулей для проведения описательного и предсказательного анализа. Учитывая специфику задач конкретной организации, конструируется оптимальный вариант программного обеспечения KXEN. Благодаря открытым программным интерфейсам, KXEN легко встраивается в существующие системы организации. Поэтому форма представления результатов анализа, с которой будут работать сотрудники на местах, может определяться пожеланиями Заказчика и особенностями его бизнес-процесса. На рис. 12 представлена структура KXEN Analytic Framework Version 3.0.



Рис. 12 Структура KXEN Analytic Framework Version 3.0

Технические характеристики продукта

KXEN Analytic FrameworkTM представляет собой набор описательных и предсказательных аналитических модулей, которые можно скомбинировать в зависимости от задачи заказчика. KXEN не является закрытым приложением, он встраивается в существующие системы организации, благодаря открытым программным интерфейсам. Поэтому форма представления результатов анализа, с которой будут работать сотрудники на местах, может определяться пожеланиями Заказчика и особенностями его бизнес-процесса.

Средства KXEN представляют собой приложения в архитектуре Клиент/сервер. Сервер KXEN осуществляет жизненный цикл модели - построение, обучение, корректировку, использование новых данных. С Клиентов осуществляется управление указанными процессами. Могут быть использованы стандартные клиентские рабочие места, поставляемые KXEN, или разработаны новые под конкретные задачи. Клиентское программное обеспечение KXEN поставляется с исходными кодами и может быть модифицировано или взято в качестве основы для собственной разработки.

Следует отметить, что для работы с KXEN от пользователя не требуется специальной квалификации и знаний в области анализа и статистики. От него требуются данные, которые требуется проанализировать, и определение типа задачи, которую нужно решить. Имеются в виду задачи описательного или предсказательного анализа или, говоря техническим языком, задачи классификации, регрессии или кластеризации.

7. Oracle Data Mining

В марте 1998 компания Oracle [10] объявила о совместной деятельности с 7 партнерами - поставщиками инструментов Data Mining. Далее последовало включение в Oracle8i средств поддержки алгоритмов Data mining. В июне 1999 года Oracle приобретает Darwin (Thinking Machines Corp.). В 2000-2001 годах выходят новые версии Darwin, Oracle Data Mining Suite. В июне 2001 года выходит Oracle9i Data Mining.

Oracle Data Mining является опцией или модулем в Oracle Enterprise Edition (версия Oracle Database 10g). Опция Oracle Data Mining (ODM) предназначена для анализа данных методами, относящимися к технологии извлечения знаний, или Data Mining. В редакциях Personal Edition, Standard Edition, OneStandard Edition эта опция недоступна.

ODM поддерживает все этапы технологии извлечения знаний, включая постановку задачи, подготовку данных, автоматическое построение моделей, анализ и тестирование результатов, использование моделей в реальных приложениях [11].

Существенно, что модели строятся автоматически на основе анализа имеющихся данных об объектах, наблюдениях и ситуациях с помощью специальных алгоритмов. Основу опции ODM составляют процедуры, реализующие различные алгоритмы построения моделей классификации, регрессии, кластеризации.

На этапе подготовки данных обеспечивается доступ к любым реляционным базам, текстовым файлам, файлам формата SAS. Дополнительные средства преобразования и очистки данных позволяют изменять вид представления, проводить нормализацию значений, выявлять неопределенные или отсутствующие значения. На основе подготовленных данных специальные процедуры автоматически строят модели для дальнейшего прогнозирования, классификации новых ситуаций, выявления аналогий. ODM поддерживает построение пяти различных типов моделей. Графические средства предоставляют широкие возможности для анализа полученных результатов, верификации моделей на тестовых наборах данных, оценки точности и устойчивости результатов. Уточненные и проверенные модели можно включать в существующие приложения путем генерации их описаний на С, C++, Java, а также разрабатывать новые специализированные приложения с помощью входящего в состав среды ODM средства разработки Software Development Kit (SDK).

Важной особенностью системы ODM являются его технические характеристики: работа в архитектуре клиент-сервер, широкое использование техники параллельных вычислений, высокая степень масштабируемости при увеличении вычислительных ресурсов.

Характеристики Oracle Data Mining :

Встроенные в Oracle Database алгоритмы извлечения знаний (DataMining Server).

DM-инфраструктура вместо готовой инструментальной среды.

API для разработки.

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

Oracle Data Mining API. Использование Java API для разработки на Java основано на принципах JDM (стандарт для Data Mining).

Версия Data Mining 10g поддерживает спектр алгоритмов, которые приведены в таблице 3.

Таблица 3 Алгоритмы, реализованные в Oracle Data Mining

Классификационные модели	Na_ve Bayes, Adaptive Bayes Network
Классификации и регрессионные модели	Support Vector Machine
Поиск существенных атрибутов	Minimal Descriptor Length
Кластеризация	Enhanced K-means, O-cluster
Поиск ассоциаций	Apriory Algorithm
Выделение признаков	Non-Negative Matrix Factorization

Особенность алгоритмов, реализованных в Oracle Data Mining, состоит в том, что все они работают непосредственно с реляционными базами данных и не требуют выгрузки и сохранения данных в специальных форматах. Кроме собственно алгоритмов, в опцию ODM входят средства подготовки данных, оценки результатов, применения моделей к новым наборам данных. Использовать все эти возможности можно как на программном уровне с помощью Java API или PL/SQL API, так и с помощью графической среды ODM Client, которая ориентирована на работу аналитиков, решающих задачи прогнозирования, выявления тенденций, сегментации и другие.

Oracle Data Mining - функциональные возможности

Функции - Oracle Data Mining строит прогнозирующие и дескрипторные модели.

Прогнозирующие модели:

классификация;

регрессия;

поиск существенных атрибутов.

Дескрипторные модели:

кластеризация;

поиск ассоциаций;

выделение признаков.

8. Сравнение систем Data Mining

Таблица 4 Сравнение систем Data Mining

	PolyAnalist	Oracle Data Mining	KXEN
Архитектура	Клиент/Сервер	Клиент/Сервер	Клиент/Сервер
Типы данных	числа, булевы переменные, категориальные переменные, текстовые строки, даты.	числа, булевы переменные, категориальные переменные, текстовые строки, даты.	числа, булевы переменные, категориальные переменные, текстовые строки, даты.
Операционная система	Серверная часть - MS Windows NT/2000/XP server Клиентская часть - MS Windows 98/NT/2000/XP	Кроссплатформенная система, возможность применения тонкого клиента.	Кроссплатформенная система, возможность применения тонкого клиента.
Особенности	Поддержка OLE DB for Data Mining, In-place Data Mining, PolyAnalyst Scheduler	обеспечивается доступ к любым реляционным базам, автоматическое построение моделей для дальнейшего прогнозирования, разработка новых специализированных приложений с помощью Software Development Kit (SDK), использование техники параллельных вычислений, высокая степень масштабируемости при увеличении вычислительных ресурсов, использование Java API для разработки на Java	Удобная и безопасная работа с данными. Наглядность результатов моделирования, легкость для понимания: графическое отображение моделей + score-карты. Автоматическая генерация кода моделей на языках С++, XML, PMML, HTML, AWK, SQL, JAVA, VB, SAS, при этом модель сможет работать автономно

Заключение

1. Рынок систем Data Mining экспоненциально развивается. В этом развитии принимают участие практически все крупнейшие корпорации (см. например http://www.kdnuggets.com). В частности, Microsoft непосредственно руководит большим сектором данного рынка (издает специальный журнал, проводит конференции, разрабатывает собственные продукты).

2. Системы Data Mining применяются по двум основным направлениям: 1) как массовый продукт для бизнес-приложений; 2) как инструменты для проведения уникальных исследований (генетика, химия, медицина и пр.). В настоящее время стоимость массового продукта от $1000 до $10000. Количество инсталляций массовых продуктов, судя по имеющимся сведениям, сегодня достигает десятков тысяч. Лидеры Data Mining связывают будущее этих систем с использованием их в качестве интеллектуальных приложений, встроенных в корпоративные хранилища данных.

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

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

В заключение отметим очередное симптоматичное событие. компания Microsoft официально объявила об усилении своей активности в области Data Mining. Специальная исследовательская группа Microsoft, возглавляемая Усамой Файядом, и пять приглашенных партнеров (Angoss, Datasage, E.piphany, SAS, Silicon Graphics, SPSS) готовят совместный проект по разработке стандарта обмена данными и средств для интеграции инструментов Data Mining с базами и хранилищами данных.

Литература

1. Айвазян С. А., Бухштабер В. М., Юнюков И. С., Мешалкин Л. Д. Прикладная статистика: Классификация и снижение размерности. -- М.: Финансы и статистика, 1989.

2. Knowledge Discovery Through Data Mining: What Is Knowledge Discovery? -- Tandem Computers Inc., 1996.

3. Кречетов Н.. Продукты для интеллектуального анализа данных. -- Рынок программных средств, № 14-15, 1997, c. 32-39.

4. Boulding K. E. General Systems Theory -- The Skeleton of Science//Management Science, 2, 1956.

5. Гик Дж., ван. Прикладная общая теория систем. -- М.: Мир, 1981.

6. Киселев М., Соломатин Е.. Средства добычи знаний в бизнесе и финансах. -- Открытые системы, № 4, 1997, с. 41-44.

7. Дюк В.А. Обработка данных на ПК в примерах. -- СПб: Питер, 1997.

8. Сайт компании SAS

www.sas.com

9. Ольга Горчинская

Семинары по технологиям Oracle9i. Инструментальные средства Oracle Data Mining

http://www.oracle.com

10. Сайт компании StatSoft

www.StatSoft.com

11. Сайт www.spc-consulting.ru/dms/

Размещено на Allbest.ru