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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Бикластеризация, блоковая кластеризация,[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]

Основные типы:

  1. Бикластер с постоянными значениями (a),
  2. Бикластер с постоянными значениями по строкам (b) или столбцам (c),
  3. Бикластер со сцепленными значениями (d, e).

На основе обзора С. Мадейры и А. Оливейры[12] и некоторых других была так же предложена таксономия методов бикластеризации на основе типов бикластеров, их структуры, характера порождения, стратегии поиска и типов значений данных.[13] [14]

Примечания

[править | править код]
  1. G. Govaert, M. Nadif. Block clustering with bernoulli mixture models: Comparison of different approaches, (англ.) // Computational Statistics and Data Analysis[англ.] : journal. — Elsevier, 2008. — Vol. 52. — P. 3233—3245.
  2. G. Govaert, M. Nadif. Co-clustering: models, algorithms and applications (англ.). — ISTE, Wiley, 2013. — ISBN 978-1-84821-473-6.
  3. Van Mechelen I., Bock H. H., De Boeck P. Two-mode clustering methods:a structured overview (неопр.) // Statistical Methods in Medical Research[англ.]. — 2004. — Т. 13, № 5. — С. 363—394. — doi:10.1191/0962280204sm373ra. — PMID 15516031.
  4. 1 2 3 Mirkin, Boris. Mathematical Classification and Clustering (англ.). — Kluwer Academic Publishers, 1996. — ISBN 0-7923-4159-7.
  5. Hartigan J. A. Direct clustering of a data matrix (англ.) // Journal of the American Statistical Association : journal. — American Statistical Association, 1972. — Vol. 67, no. 337. — P. 123—129. — doi:10.2307/2284710. — JSTOR 2284710.
  6. Hartigan J A. Direct clustering of a data matrix[J]. Journal of the american statistical association, 1972, 67(337): 123—129. Дата обращения: 30 апреля 2016. Архивировано 15 марта 2022 года.
  7. https://www.cs.princeton.edu/courses/archive/fall03/cs597F/Articles/biclustering_of_expression_data.pdf Архивная копия от 4 марта 2016 на Wayback Machine Cheng Y, Church G M. Biclustering of expression data[C]//Ismb. 2000, 8: 93-103.
  8. 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.
  9. 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.
  10. 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.
  11. Peeters R. The maximum edge biclique problem is NP-complete[J]. Discrete Applied Mathematics, 2003, 131(3): 651—654. Дата обращения: 30 апреля 2016. Архивировано 24 сентября 2015 года.
  12. 1 2 3 Madeira S. C., Oliveira A. L. Biclustering Algorithms for Biological Data Analysis: A Survey (англ.) // IEEE Transactions on Computational Biology and Bioinformatics : journal. — 2004. — Vol. 1, no. 1. — P. 24—45. — doi:10.1109/TCBB.2004.2. — PMID 17048406.
  13. Игнатов Д.И. Методы бикластеризации для анализа интернет-данных // CITForum.ru. — 2008. Архивировано 1 мая 2023 года.
  14. Ignatov D.I., Watson B.W. Towards a Unified Taxonomy of Biclustering Methods (англ.) // Proceedings of Russian and South African Workshop on Knowledge Discovery Techniques Based on Formal Concept Analysis (RuZA 2015). CEUR Workshop Proceedings, 2015. — 2015. — Vol. 1552. — P. 23—39. Архивировано 19 апреля 2022 года.

Литература

[править | править код]