Бикластеризация
Бикластеризация, блоковая кластеризация,[1] сокластеризация, также двухмодальная кластеризация [2] [3] — методика data mining, которая позволяет одновременную кластеризацию строк и столбцов матрицы. Термин был впервые предложен Б.Г. Миркиным,[4] хотя сам метод был придуман гораздо раньше[4] (J.A. Hartigan[5]).
Принимая на вход набор строк в столбцах (матрица размера ), алгоритм бикластеризации генерирует бикластеры — подмножество строк, которые проявляют похожее поведение через подмножество столбцов.
История развития
Бикластеризация была впервые представлена J. A. Hartigan в 1972 году[6]. Термин бикластеризация был позднее введен Б.Г. Миркиным[4]. Этот алгоритм не был обобщён до 2000 года, когда Y. Cheng и G. M. Church предложили алгоритм бикластеризации, основанный на дисперсии, и применили его к биологическим данным по экспрессии генов[7]. Их статья до сих пор остаётся одним из наиболее важных литературных материалов в области бикластеризации экспрессии генов.
В 2001 и 2003 годах I. S. Dhillon предложил два алгоритма, в которых бикластеризация применяется для файлов и слов. Одна из версий была основана на разделении двудольных спектральных графов[8]. Вторая была основана на теории информации. Dhillon допустил, что потеря взаимной информации при бикластеризации равна KL (расстояние Кульбака-Лейблера) между P и Q. P означает распределение файлов и характеристических слов перед бикластеризацией. Q, в свою очередь, — распределение после кластеризации. KL-расстояние необходимо в качестве меры отличий между двумя случайными распределениями. KL = 0, когда два распределения одинаковы, и возрастает, если возрастает отличие[9]. Таким образом, целью алгоритма являлась минимизация KL-расстояния между P и Q. В 2004 A. Banerjee использовал взвешенное расстояние Брегмана вместо KL-расстояния, чтобы разработать алгоритм бикластеризации, подходящий для любого типа матрицы, в отличие от KL алгоритма[10].
С целью кластеризовать более чем два типа объектов Bekkerman в 2005 году расширил взаимную информацию в теореме Dhillon от одной пары до множества пар.
Сложность задачи
Сложность задачи бикластеризации зависит от конкретной формулировки, в особенности от функции, используемой для оценки качества полученного бикластера. Наиболее интересные варианты этих задач являются NP-полными и требуют больших вычислительных мощностей или использования эвристических подходов[11][12].
Типы бикластеров
Различные алгоритмы бикластеризации имеют различные определения бикластера.[12]
Основные типы:
- Бикластер с постоянными значениями (a),
- Бикластер с постоянными значениями по строкам (b) или столбцам (c),
- Бикластер со сцепленными значениями (d, e).
На основе обзора С. Мадейры и А. Оливейры[12] и некоторых других была так же предложена таксономия методов бикластеризации на основе типов бикластеров, их структуры, характера порождения, стратегии поиска и типов значений данных.[13] [14]
См. также
Примечания
Литература
- Шаблон:Статья
- A. Tanay. R. Sharan, and R. Shamir, «Biclustering Algorithms: A Survey», In Handbook of Computational Molecular Biology, Edited by Srinivas Aluru, Chapman (2004)
- Шаблон:Статья
Ссылки
- ↑ Шаблон:Статья
- ↑ Шаблон:Книга
- ↑ Шаблон:Статья
- ↑ 4,0 4,1 4,2 Шаблон:Книга
- ↑ Шаблон:Статья
- ↑ Шаблон:Cite web
- ↑ https://www.cs.princeton.edu/courses/archive/fall03/cs597F/Articles/biclustering_of_expression_data.pdf Шаблон:Wayback Cheng Y, Church G M. Biclustering of expression data[C]//Ismb. 2000, 8: 93-103.
- ↑ Dhillon I S. Co-clustering documents and words using bipartite spectral graph partitioning[C]//Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2001: 269—274.
- ↑ Dhillon I S, Mallela S, Modha D S. Information-theoretic co-clustering[C]//Proceedings of the ninth ACM SIGKDD international conference on KKluwer Academic Publishersnowledge discovery and data mining. ACM, 2003: 89-98.
- ↑ Banerjee A, Dhillon I, Ghosh J, et al. A generalized maximum entropy approach to bregman co-clustering and matrix approximation[C]//Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2004: 509—514.
- ↑ Шаблон:Cite web
- ↑ 12,0 12,1 12,2 Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья