Бікластеризація даних
Бікластерізація — широкий спектр завдань, в яких потрібно виявляти кластери із збереженням об'єктно-ознакового опису даних. Методи бікластеризації, розроблені для цих цілей, лежать в області кластер-аналізу і отримали свою власну назву. Під терміном бікластеризація розуміється широке коло завдань і методів, а тому для нього в науковій літературі існує цілий ряд синонімів: спільна кластеризація (simultaneous clustering), кокластеризація (co-clustering), двоходова кластеризація (two-way clustering), кластеризація підпростору (subspace clustering), двовимірна кластеризація (bi-dimensional) і бокс-кластеризація (box-clustering). Підвищений інтерес до бікластеризації і виділення її в самостійну область аналізу даних виникли у зв'язку завданням аналізу масивів генетичних даних (microarray data analysis).
Актуальність теми
- Зростання інтернет — ринку;
- Метод широко застосовується в прикладних задачах різних сфер науки і техніки, у економіці, прикладній математиці, генетиці;
- Низька ефективність існуючих методів при складному наборі даних
Опис
Існує широкий спектр завдань, в яких потрібно виявляти кластери із збереженням об'єктно-ознакового опису даних: виявлення груп генів, що володіють загальними властивостями; пошук груп відвідувачів зі схожими інтересами для рекомендаційних систем; виявлення спільнот; аналіз соціальних мереж; автоматична побудова каталогів і рубрикаторів в інформаційних системах; пошук подібності документів. При вирішенні подібних завдань класичний кластерний аналіз не надає зручних засобів, що дозволяють зберегти об'єктно-ознаковий опис кластеру. Для цього розробляються методи бікластеризації.
В даний час методи кластерного аналізу є необхідними у величезній кількості прикладних задач різних галузей науки і техніки. Сама область кластеризації, незважаючи на безперервний розвиток і появу нових додатків, має міцну теоретичну базу і підтверджені результати.
Теоретична значущість
- встановлення взаємозв'язків існуючих моделей бікластеризації, методів аналізу даних на основі теорії решіток і пошуком асоціативних правил;
- побудові таксономії існуючих методів бікластеризації і її розширенні шляхом включення критеріїв класифікації нових і споріднених методів;
- розробці моделі бікластеризації на основі замкнутих множин об'єктів і ознак, теоретичному дослідженні її властивостей.
Практична значущість
Полягає в розробці ефективних моделей і методів пошуку документів-дублікатів, побудови таксономії веб-користувачів і моделей і методів рекомендаційних систем на основі бікластеризації.
Типи бікластерів
- бікластер з постійними значеннями;
- бікластер з постійними значеннями рядків або стовпців;
- бікластер з когерентним значеннями;
- бікластер з когерентним змінами.
Алгоритмічні стратегії пошуку
Алгоритми бікластеризації можуть породжувати або один бікластер, або кілька, залежно від типу завдання. Наприклад, алгоритм Ченга і Черча знаходить один бікластер за прохід, а для знаходження наступних необхідно маскувати знайдений випадковими числами і виконати повторний запуск алгоритму. Інші бікластерні підходи дозволяють знаходити безліч бікластерів за прохід. Існують також алгоритми, які дозволяють здійснювати одночасне виявлення бікластерів.[5]
Приймаючи до уваги алгоритмічну складність, стратегії пошуку пожна розбити на 5 класів:
- ітеративна комбінація кластеризації по рядках і стовпцях;
- стратегія розділяй і володарюй;
- жадібна стратегія ітеративного пошуку;
- повне перерахування бікластерів;
- визначення параметрів розподілу.
Огляд існуючих методів і моделей бікластеризації
Формальний Аналіз Понять — область прикладної математики, об'єктами дослідження в якої є (формальні) поняття та їх ієрархії. Прикметник «формальний» вказує на наявність строгого математичного визначення поняття, як пари множин, званих, слідуючи традиціям прийнятим у філософії, обсягом і змістом. Формалізація цих визначень стала можливою завдяки використанню апарату алгебраїчної теорії решіток. Включення підрозділу, присвяченого ФАП, в розділ про методи і моделях бікластеризації обґрунтовано широким спектром завдань з області аналізу даних, в яких ключовим є пошук бікластерів особливого роду — формальних понять.
Формальний контекст К - це (G, M, I), де G — множина об'єктів, М — множина ознак, І ≤ G*M— відношення.
Відношення І інтерпретується наступним чином: для g є G, m є M, має місце gIM, якщо об'єкт g володіє ознаками m.
Для формального контексту K = (G, M,I) і випадкових B ≤ M визначена пара відображень: A’ := {m є M| gLm, для всіх g є A },
A’ := {g є G| gLm, для всіх m є B },
Які задають відповідність Галуа між частково впорядкованими множинами
(2G,≤) і (2М, ≤)
а оператор (.)" є оператором замикання на — диз'юнктивним об'єднанням, тобто випадковим А є С або А є М мають місце наступні відношення:
- A ≤ A" (екстенсивність),
- A"«=A» (ідемпотентність),
- Якщо A≤C то A" ≤C", (ізотонність).
Множина А називається замкнутою, якщо A" = A
Алгоритм BiMax відповідає стратегії «розділяй і володарюй». Спочатку алгоритм визначає області матриці, що містять тільки 0, і потім виключає їх з подальшого розгляду. Ця стратегія особливо виграшна за умови розріджених даних, отримання яких з вихідних наборів залежить від вибору порогу відсікання.
Ідея, що лежить в основі алгоритму, полягає в наступному: вихідна матриця розбивається на три підматриці, одна з яких містить лише нульові значення і надалі не розглядається. Потім алгоритм рекурсивно застосовується до двох підматриць, що залишилися. Рекурсія припиняється, якщо поточна матриця, що являє собою бікластер, містить тільки одиниці.
Існуючі системи бікластеризації
Система Coron для Data Mining
Система аналізу даних Coron призначена для пошуку множин ознак і асоціативних правил. Програма володіє непоганим графічним інтерфейсом, власним форматом даних, можливістю роботи з базами даних. Для пошуку множин ознак використовуються найбільш ефективні алгоритми спільноти FIM.. Пошук асоціативних правил також використовує ефективні алгоритми, що спираються на досягнення ФАП і опинилися корисними для компактного представлення правил та побудови їх базисів. Ще однією перевагою продукту є вільний доступ і кросплатформність (в сенсі технології Java).
У величезного числа документів (за деякими джерелами до 30 %) в Інтернеті є дублікати, і пошукові машини повинні володіти ефективними засобами обчислення кластерів дублікатів. Походження дублікатів може бути різним — від дублювання компаніями власної інформації на різних серверах (створення дзеркал) до зловмисних — обману програм індексаторів вебсайтів, незаконного копіювання і спамерських розсилок.
Зазвичай дублікати документів визначаються на основі відношення подібності на документах: два документа подібні, якщо деяка числова міра їх схожості перевищує деякий поріг. По відношенню подібності обчислюються кластери схожих документів. Спочатку, після зняття HTML-розмітки документа, як лінійні послідовності слів (символів), перетворюються у множини. Тут двома основними схемами є синтаксичні та лексичні методи. До синтаксичним відноситься метод шинглірування, в якому документ в підсумку представляється набором хеш-кодів; цей метод використовується в пошукових системах Google і AltaVista. В лексичних методах велика увага приділяється побудові словника — набору дескриптивних слів; відомі його різновиди, такі I-match і метод ключових слів Іллінського.
Список використаної літератури
- Биркгоф Г. Теория решеток. — М.:Наука, 1989.
- Игнатов Д. И., Кузнецов С. О. О поиске сходства Интернет-документов с помощью частых замкнутых множеств признаков // Труды 10-й национальной конференции по искусственному интеллекту с международным участием (КИИ'06). — М.:Физматлит, 2006, Т.2, стр.249-258.
- Самохин М. В., Машинное обучение на узорных структурах, ВИНИТИ, 2006.
- R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A. Inkeri Verkamo, «Fast Discovery of Association Rules,» Advances in Knowledge Discovery, and Data Mining, U. Fayyad et al., eds., pp. 307—328, Menlo Park, Calif.: AAAI Press, 1996.
- Amine Abou-Rjeili and George Karypis. Multilevel Algorithms for Partitioning Power-Law Graphs. IEEE International Parallel & Distributed Processing Symposium (IPDPS) (in press), 2006.
- Mohammed J. Zaki, Ching-Jui Hsiao, Efficient Algorithms for Mining Closed Itemsets and Their Lattice Structure, IEEE Transaction on Knowledge and Data Engineering, Vol 17, No. 4, pp. 462—478, 2005.
- L.Е. Zhukov. Technical Report: Spectral Clustering of Large Advertiser Datasets Part I. Overture R&D, 2004.