Введение 1

1. Бикластеризация 4

1.1.Типы данных и бикластеров………………………………………………………………...5

1.2.Структура бикластеров……………………………………………………………………...6

2. Система бикластеризации генетических данных BicAT 7

2.1. Алгоритмы бикластеризации, реализованные в системе……………………………..10

3. Проведение экспериментов на данных рекомендательного интернет-сервиса 21

Заключение 23

Список использованной литературы 24

Методы кластерного анализа широко используются для решения большинства прикладных задач различных областей науки и техники. Постановки задач кластеризации и классификации довольно близки. Принципиальное отличие в решении заключается в следующем:

" (классификация): необходимо приписать анализируемый объект к некоторому уже известному классу,

" (кластеризация): требуемые классы порождаются на основе свойств исследуемых объектов.

Сходство объектов представляет собой базовое понятие кластерного анализа. Математическое выражение - мера (метрика) близости. Опираясь на значения этой метрики, можно говорить о близости объектов и определять, принадлежат они к одному кластеру или нет. В ходе кластерного анализа объектно-признаковое описание данных обычно заменяется матрицей сходства, например, объектов. Из-за того, что в самих кластерах общее признаковое описание составляющих их объектов явно не выражено, часто получаются классы, несколько абсурдные, с точки зрения практического смысла. Наглядный пример - цепочка слов, превращающих слово "муха" в слово "слон". Некоторые методы кластеризации работают ошибочно, то есть "мухи" и "слоны" оказываются в одном кластере. В реальных задачах такие недостатки методов кластеризации могут иметь существенное значение. Так как цена ошибочного разбиения на классы велика, а невозможность интерпретации результатов экспериментов сопутствует провалу исследований. Например, при поиске документов-дубликатов для Web-страниц, который осуществляют известные поисковые системы, такие как Google или Yandex, в одном кластере могут оказаться совершенно непохожие документы. Это происходит из-за того, что существует последовательность документов, в которой каждый документ в чем-то сходен с соседним. Причем, сходство не транзитивное и, следовательно, общее признаковое описание таких документов при вычислении сходства на каждом шаге не теряется. В итоге страдает пользователь поисковой системы, от которого скрыты эти неверно выявленные нечеткие дубликаты и поиск рискует оказаться нерелевантным.

Существует широкий спектр задач, в которых требуется выявлять кластеры с сохранением объектно-признакового описания данных:

" выявление интернет-сообществ и научных сообществ,

" поиск документов-дубликатов.

" построение автоматических каталогов в информационных системах,

" задачи выявления групп генов, обладающих похожими свойствами в биоинформатике,

" задача анализа социальных сетей,

" поиск групп пос

1. С.А. Кедров, С.О. Кузнецов Исследование групп пользователей Интернет-ресурсами методами анализа формальных понятий и разработки данных (Data Mining)//Бизнес-информатика, №1 - 2007, стр. 45 - 51

2. Кузнецов С.О., Игнатов Д.И., Объедков С.А., Самохин М.В. Порождение кластеров документов дубликатов: подход, основанный на поиске частых замкнутых множеств признаков. Интернет-математика 2005. Автоматическая обработка веб-данных. Москва: "Яndex", 2005, стр. 302 - 319

3. Belohlavek R. Lattice type fuzzy order and closure operators in fuzzy ordered sets. Proc. Joint 9th IFSA World Congress and 20th NAFIPS International Conference, 2001, Vancouver, Canada, IEEE Press, pp. 2281-2286.

4. Belohlavek R., Vychodil V. What is a fuzzy concept lattice? In: Proc. CLA 2005, 3rd Int. Conference on Concept Lattices and Their Applications, September 7-9, 2005, Olomouc, Czech Republic, pp. 34-45

5. Ben-Dor,A., Chor,B., Karp,R. and Yakhini,Z. Discovering local structure in gene expression data: the order-preserving sub-matrix problem. In Proceedings of the 6th Annual International Conference on Computational Biology, ACM Press, New York, NY, USA, pp. 49-57, 2002

6. J. Besson, C. Robardet, J-F. Boulicaut. Constraint-based mining of formal concepts in transactional data. In: Proceedings of the 8th Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2004

7. Cheng,Y. and Church,G. Biclustering of expression data. Proc. Int. Conf. Intell. Syst. Mol. Biol. pp. 93-103, 2000

8. Ihmels,J. et al. Defining transcription modules using large-scale gene expression, data. Bioinformatics, 20, 1993-2003, 2004

9. B. Mirkin, P. Arabie, L. Hubert Additive Two-Mode Clustering: The Error-Variance Approach Revisited, Journal of Classification, 12, 243-263, 1995

10. Murali,T.M. and Kasif,S. Extracting conserved gene expression motifs from gene expression data. Pac. Symp. Biocomput., 8, 77-88, 2003

11. Prelic, A., Bleuer, S., Zimmermann, P., Wille, A., Bhlmann, P., Gruissem, W., Hennig, L., Thiele, L., Zitzler, E.: A systematic comparison and evaluation of biclustering methods for gene expression data. Bioinformatics 22(9), 1122-1129, 2006

12. G. Stumme and R. Taouil and Y. Bastide and N. Pasqier and L. Lakhal. Computing Iceberg Concept Lattices with Titanic. J. on Knowledge and Data Engineering, (42)2:189--222,2002.

13. L.Е. Zhukov. Technical Report: Spectral Clustering of Large Advertiser Datasets Part I. Overture R&D, 2004

14. Игнатов Д., Диссертационная работа магистра на тему "Методы бикластеризации для анализа Интернет-данных", 2008.

Примечаний нет.