Бікластеризація даних
Цю статтю треба вікіфікувати для відповідності стандартам якості Вікіпедії. (березень 2015) |
Бікластерізація — широкий спектр завдань, в яких потрібно виявляти кластери із збереженням об'єктно-ознакового опису даних. Методи бікластеризації, розроблені для цих цілей, лежать в області кластер-аналізу і отримали свою власну назву. Під терміном бікластеризація розуміється широке коло завдань і методів, а тому для нього в науковій літературі існує цілий ряд синонімів: спільна кластеризація (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.