stringtranslate.com

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

Бикластеризация , блочная кластеризация , [1] [2] Совместная кластеризация или двухмодовая кластеризация [3] [4] [5] — это метод интеллектуального анализа данных , позволяющий одновременно кластеризовать строки и столбцы матрицы . Термин был впервые введен Борисом Миркиным [6] для обозначения метода, представленного много лет назад, [6] в 1972 году Джоном А. Хартиганом . [7]

Учитывая набор образцов, представленных -мерным вектором признаков, весь набор данных может быть представлен в виде строк в столбцах (т. е. матрицы). Алгоритм бикластеризации генерирует бикластеры. Бикластер — это подмножество строк, которые демонстрируют схожее поведение в подмножестве столбцов, или наоборот.

Разработка

Бикластеризация была первоначально введена Джоном А. Хартиганом в 1972 году. [7] Термин «бикластеризация» был позже использован и уточнен Борисом Г. Миркиным. Этот алгоритм не был обобщен до 2000 года, когда Y. Cheng и George M. Church предложили алгоритм бикластеризации, основанный на среднеквадратичном значении остатка (MSR), и применили его к данным по биологической экспрессии генов. [8]

В 2001 и 2003 годах IS Dhillon опубликовал два алгоритма, применяющих бикластеризацию к файлам и словам. Одна версия была основана на разбиении двудольного спектрального графа. [9] Другая была основана на теории информации. Dhillon предположил, что потеря взаимной информации во время бикластеризации была равна расстоянию Кульбака–Лейблера (KL-расстояние) между P и Q. P представляет собой распределение файлов и признаковых слов до бикластеризации, в то время как Q — распределение после бикластеризации. KL-расстояние предназначено для измерения разницы между двумя случайными распределениями. KL = 0, когда два распределения одинаковы, и KL увеличивается по мере увеличения разницы. [10] Таким образом, целью алгоритма было найти минимальное KL-расстояние между P и Q. В 2004 году Ариндам Баннерджи использовал взвешенное расстояние Брегмана вместо KL-расстояния для разработки алгоритма бикластеризации, который подходил для любого вида матрицы, в отличие от алгоритма KL-расстояния. [11]

Чтобы объединить в кластер более двух типов объектов, в 2005 году Беккерман расширил взаимную информацию в теореме Диллона с одной пары до нескольких пар. [12]

Сложность

Сложность задачи бикластеризации зависит от точной формулировки задачи и, в частности, от функции заслуг, используемой для оценки качества данного бикластера. Однако наиболее интересными вариантами этой задачи являются NP-полные . NP-полные имеет два условия. В простом случае, когда в двоичной матрице A есть только один элемент a ( i , j ) , равный либо 0, либо 1, бикластер равен биклике в соответствующем двудольном графе . Максимальный размер бикластера эквивалентен максимальному ребру биклике в двудольном графе. В сложном случае элемент в матрице A используется для вычисления качества данного бикластера и решения более ограниченной версии задачи. [13] Это требует либо больших вычислительных усилий, либо использования эвристики с потерями для сокращения вычислений. [14]

Типы бикластеров

Бикластер с постоянными значениями (а)

Когда алгоритм бикластеризации пытается найти бикластер с постоянным значением, он переупорядочивает строки и столбцы матрицы, чтобы сгруппировать вместе похожие строки и столбцы, в конечном итоге группируя бикластеры с похожими значениями. Этот метод достаточен, когда данные нормализованы. Идеальный постоянный бикластер — это матрица (I,J), в которой все значения a(i,j) равны заданной константе μ. В материальных данных эти записи a(i,j) могут быть представлены в виде n(i,j) + μ , где n(i,j) обозначает шум . Согласно алгоритму Хартигана, путем разбиения исходной матрицы данных на набор бикластеров дисперсия используется для вычисления постоянных бикластеров. Следовательно, идеальный бикластер может быть эквивалентно определен как матрица с дисперсией, равной нулю. Чтобы предотвратить разбиение матрицы данных на бикластеры с единственной строкой и одним столбцом; Хартиган предполагает, что в матрице данных есть, например, K бикластеров. Когда матрица данных разделена на K бикластеров, алгоритм завершается.

Бикластер с постоянными значениями в строках (b) или столбцах (c)

В отличие от бикластеров с постоянным значением, эти типы бикластеров не могут быть оценены исключительно на основе дисперсии их значений. Чтобы завершить идентификацию, столбцы и строки должны быть сначала нормализованы. Однако существуют другие алгоритмы без шага нормализации, которые могут находить бикластеры, имеющие строки и столбцы с различными подходами.

Бикластер с когерентными значениями (d, e)

Для бикластеров с когерентными значениями в строках и столбцах следует рассмотреть общее улучшение по сравнению с алгоритмами для бикластеров с постоянными значениями в строках или столбцах. Этот алгоритм может содержать анализ дисперсии между группами, используя ковариацию между строками и столбцами. В теореме Ченга и Чёрча бикластер определяется как подмножество строк и столбцов с почти одинаковым баллом. Балл сходства используется для измерения когерентности строк и столбцов.



Связь между этими кластерными моделями и другими типами кластеризации, такими как корреляционная кластеризация, обсуждается в [15] .

Алгоритмы

Существует множество алгоритмов бикластеризации, разработанных для биоинформатики , в том числе: блочная кластеризация, CTWC (связанная двухсторонняя кластеризация), ITWC (взаимосвязанная двухсторонняя кластеризация), δ-бикластер, δ-pCluster, δ-паттерн, FLOC, OPC, пледовая модель, OPSM (сохраняющие порядок подматрицы), Gibbs, SAMBA (статистико-алгоритмический метод для бикластерного анализа), [16] надежный алгоритм бикластеризации (RoBA), минимизация пересечения, [17] cMonkey, [18] PRM, DCC, LEB (локализация и извлечение бикластеров), QUBIC (качественная бикластеризация), BCCA (алгоритм бикорреляционной кластеризации), BIMAX, ISA и FABIA ( факторный анализ для получения бикластера), [19] runibic, [20] и недавно предложенный гибридный метод EBIC (evolutionary-based Biclustering), [21], который, как было показано, обнаруживает множественные шаблоны с очень высокой точностью. Совсем недавно был предложен IMMD-CC [22] , разработанный на основе концепции итеративного снижения сложности. IMMD-CC способен идентифицировать центроиды кокластера из сильно разреженного преобразования, полученного с помощью итеративной многомодовой дискретизации.

Алгоритмы бикластеризации также были предложены и использовались в других прикладных областях под названиями совместная кластеризация, двумерная кластеризация и подпространственная кластеризация. [14]

Учитывая известную важность обнаружения локальных закономерностей в данных временных рядов , недавние предложения были направлены на решение проблемы бикластеризации в конкретном случае данных экспрессии генов временных рядов . В этом случае интересные бикластеры могут быть ограничены теми, у которых есть смежные столбцы. Это ограничение приводит к разрешимой проблеме и позволяет разрабатывать эффективные алгоритмы исчерпывающего перечисления , такие как CCC-бикластеризация [23] и e - CCC-бикластеризация. [24] Приближенные закономерности в алгоритмах CCC-бикластеризации допускают заданное количество ошибок на ген относительно профиля экспрессии, представляющего закономерность экспрессии в бикластере. Алгоритм e-CCC-бикластеризации использует приближенные выражения для поиска и сообщения всех максимальных CCC-бикластеров с помощью дискретизированной матрицы A и эффективных методов обработки строк.

Эти алгоритмы находят и сообщают все максимальные бикластеры с когерентными и смежными столбцами с идеальными/приблизительными шаблонами экспрессии, в линейном/ полиномиальном времени , которое получается путем манипулирования дискретизированной версией исходной матрицы экспрессии в размере матрицы экспрессии генов временного ряда с использованием эффективных методов обработки строк , основанных на деревьях суффиксов . Эти алгоритмы также применяются для решения проблем и наброска анализа вычислительной сложности.

Некоторые недавние алгоритмы пытались включить дополнительную поддержку бикластеризации прямоугольных матриц в виде других типов данных , включая cMonkey.

Продолжаются дебаты о том, как оценивать результаты этих методов, поскольку бикластеризация допускает перекрытие между кластерами, а некоторые алгоритмы позволяют исключать трудно согласуемые столбцы/условия. Не все доступные алгоритмы являются детерминированными, и аналитик должен обращать внимание на степень, в которой результаты представляют собой стабильные минимумы . Поскольку это проблема неконтролируемой классификации , отсутствие золотого стандарта затрудняет обнаружение ошибок в результатах. Один из подходов заключается в использовании нескольких алгоритмов бикластеризации с голосованием большинства или сверхбольшинства среди них для определения наилучшего результата. Другой способ заключается в анализе качества шаблонов сдвига и масштабирования в бикластерах. [25] Бикластеризация использовалась в области интеллектуального анализа текста (или классификации), которая широко известна как совместная кластеризация. [26] Текстовые корпуса представлены в векторной форме в виде матрицы D, строки которой обозначают документы, а столбцы — слова в словаре. Элементы матрицы D ij обозначают вхождение слова j в документ i. Затем применяются алгоритмы совместной кластеризации для обнаружения блоков в D, соответствующих группе документов (строк), характеризующихся группой слов (столбцов).

Кластеризация текста может решить проблему разреженного многомерного текста, что означает одновременную кластеризацию текста и слов. При кластеризации текста нам нужно думать не только об информации о словах, но и об информации о кластерах слов, которые были составлены словами. Затем, в соответствии со сходством характерных слов в тексте, в конечном итоге кластеризуются характерные слова. Это называется совместной кластеризацией. Есть два преимущества совместной кластеризации: во-первых, кластеризация теста на основе кластеров слов может значительно уменьшить размерность кластеризации, это также может быть целесообразно для измерения расстояния между тестами. Во-вторых, извлекается больше полезной информации и может быть получена соответствующая информация в тестовых кластерах и кластерах слов. Эта соответствующая информация может быть использована для описания типа текстов и слов, в то же время результат кластеризации слов может быть также использован для интеллектуального анализа текста и поиска информации.

Было предложено несколько подходов, основанных на информационном содержании полученных блоков: подходы на основе матриц, такие как SVD и BVD, и подходы на основе графов. Информационно-теоретические алгоритмы итеративно назначают каждую строку кластеру документов, а каждый столбец кластеру слов таким образом, чтобы взаимная информация была максимизирована. Матричные методы фокусируются на разложении матриц на блоки таким образом, чтобы ошибка между исходной матрицей и регенерированными матрицами из разложения была минимизирована. Графовые методы имеют тенденцию минимизировать разрезы между кластерами. При наличии двух групп документов d 1 и d 2 количество разрезов можно измерить как количество слов, которые встречаются в документах групп d 1 и d 2 .

Совсем недавно (Биссон и Хуссейн) [26] предложили новый подход использования сходства между словами и сходства между документами для совместной кластеризации матрицы. Их метод (известный как χ-Sim , для перекрестного сходства) основан на поиске сходства документа с документом и сходства слова со словом, а затем на использовании классических методов кластеризации, таких как иерархическая кластеризация . Вместо того, чтобы явно кластеризовать строки и столбцы поочередно, они рассматривают вхождения слов более высокого порядка, по сути принимая во внимание документы, в которых они встречаются. Таким образом, сходство между двумя словами вычисляется на основе документов, в которых они встречаются, а также документов, в которых встречаются «похожие» слова. Идея здесь заключается в том, что два документа по одной и той же теме не обязательно используют один и тот же набор слов для ее описания, а подмножество слов и других похожих слов, которые характерны для этой темы. Такой подход, основанный на учете сходств более высокого порядка, учитывает скрытую семантическую структуру всего корпуса, что приводит к лучшей кластеризации документов и слов.

В текстовых базах данных для коллекции документов, определенной матрицей D (размером m на n, m: количество документов, n: количество терминов), методология кластеризации на основе коэффициента покрытия [27] дает одинаковое количество кластеров как для документов, так и для терминов (слов) с использованием двухэтапного вероятностного эксперимента. Согласно концепции коэффициента покрытия количество кластеров также можно приблизительно оценить по следующей формуле , где t — количество ненулевых записей в D. Обратите внимание, что в D каждая строка и каждый столбец должны содержать по крайней мере один ненулевой элемент.

В отличие от других подходов, FABIA является мультипликативной моделью, которая предполагает реалистичные негауссовские распределения сигналов с тяжелыми хвостами . FABIA использует хорошо известные методы выбора модели, такие как вариационные подходы, и применяет байесовскую структуру. Генеративная структура позволяет FABIA определять информационное содержание каждого бикластера, чтобы отделить ложные бикластеры от истинных бикластеров.

Смотрите также

Ссылки

  1. ^ G. Govaert; M. Nadif (2008). «Блочная кластеризация с моделями смесей Бернулли: сравнение различных подходов». Computational Statistics and Data Analysis . 52 (6): 3233–3245. doi :10.1016/j.csda.2007.09.007.
  2. ^ R. Balamurugan; AM Natarajan; K. Premalatha (2015). «Оптимизация черной дыры звездной массы для бикластеризации данных экспрессии генов микрочипов». Прикладной искусственный интеллект . 29 (4): 353–381. doi : 10.1080/08839514.2015.1016391 . S2CID  44624424.
  3. ^ G. Govaert; M. Nadif (2013). Совместная кластеризация: модели, алгоритмы и приложения . ISTE, Wiley. ISBN 978-1-84821-473-6.
  4. ^ R. Balamurugan; AM Natarajan; K. Premalatha (2016). «Модифицированный метод поиска гармонии для бикластеризации данных экспрессии генов на микрочипах». Международный журнал по интеллектуальному анализу данных и биоинформатике . 16 (4): 269–289. doi :10.1504/IJDMB.2016.082205.
  5. ^ Ван Мехелен I, Бок HH, Де Бек P (2004). «Двухрежимные методы кластеризации: структурированный обзор». Статистические методы в медицинских исследованиях . 13 (5): 363–94. CiteSeerX 10.1.1.706.4201 . doi :10.1191/0962280204sm373ra. PMID  15516031. S2CID  19058237.  
  6. ^ ab Миркин, Борис (1996). Математическая классификация и кластеризация . Kluwer Academic Publishers. ISBN 978-0-7923-4159-8.
  7. ^ ab Hartigan JA (1972). «Прямая кластеризация матрицы данных». Журнал Американской статистической ассоциации . 67 (337): 123–9. doi :10.2307/2284710. JSTOR  2284710.
  8. ^ https://www.cs.princeton.edu/courses/archive/fall03/cs597F/Articles/biclustering_of_expression_data.pdf Ченг И., Чёрч Г. М. Бикластеризация данных по выражениям [C] // Ismb. 2000, 8: 93–103.
  9. ^ Диллон, Индерджит С. (2001). «Кластеризация документов и слов с использованием двудольного спектрального графового разбиения». Труды седьмой международной конференции ACM SIGKDD по обнаружению знаний и добыче данных . стр. 269–274. doi :10.1145/502512.502550. ISBN 158113391X. S2CID  11847258.
  10. ^ Dhillon, Inderjit S.; Mallela, Subramanyam; Modha, Dharmendra S. (2003). "Информационно-теоретическая совместная кластеризация". Труды девятой международной конференции ACM SIGKDD по обнаружению знаний и добыче данных . стр. 89–98. doi :10.1145/956750.956764. ISBN 1581137370. S2CID  12286784.
  11. ^ Банерджи, Ариндам; Дхиллон, Индерджит; Гош, Джойдип; Меругу, Сруджана; Модха, Дхармендра С. (2004). «Обобщенный подход максимальной энтропии к совместной кластеризации Брегмана и аппроксимации матриц». Труды десятой международной конференции ACM SIGKDD по обнаружению знаний и добыче данных . стр. 509–514. doi :10.1145/1014052.1014111. ISBN 1581138881. S2CID  2719002.
  12. ^ Беккерман, Рон; Эль-Янив, Ран; МакКаллум, Эндрю (2005). «Многоканальная распределительная кластеризация с помощью парных взаимодействий». Труды 22-й международной конференции по машинному обучению — ICML '05 . С. 41–48. doi :10.1145/1102351.1102357. ISBN 1595931805. S2CID  858524.
  13. ^ Peeters R (2003). «Проблема максимальной реберной биклики является NP-полной». Discrete Applied Mathematics . 131 (3): 651–654. doi : 10.1016/S0166-218X(03)00333-0 . S2CID  3102766.
  14. ^ ab Madeira SC, Oliveira AL (2004). «Бикластерные алгоритмы для анализа биологических данных: обзор». Труды IEEE/ACM по вычислительной биологии и биоинформатике . 1 (1): 24–45. doi :10.1109/TCBB.2004.2. PMID  17048406. S2CID  206628783.
  15. ^ Кригель, Х.-П.; Крёгер, П.; Зимек, А. (март 2009 г.). «Кластеризация многомерных данных: обзор кластеризации подпространств, кластеризации на основе шаблонов и корреляционной кластеризации». Труды ACM по обнаружению знаний из данных . 3 (1): 1–58. doi :10.1145/1497577.1497578. S2CID  17363900.
  16. ^ Tanay A, Sharan R, Kupiec M, Shamir R (2004). «Выявление модульности и организации в молекулярной сети дрожжей путем комплексного анализа высокогетерогенных данных по всему геному». Труды Национальной академии наук . 101 (9): 2981–2986. Bibcode : 2004PNAS..101.2981T. doi : 10.1073/pnas.0308661100 . PMC 365731. PMID  14973197 . 
  17. ^ Абдулла, Ахсан; Хуссейн, Амир (2006). «Новый метод бикластеризации, основанный на минимизации пересечений». Neurocomputing . 69 (16–18): 1882–1896. doi :10.1016/j.neucom.2006.02.018.
  18. ^ Рейсс DJ, Балига NS, Бонно R (2006). «Интегрированная бикластеризация гетерогенных наборов данных по всему геному для вывода глобальных регуляторных сетей». BMC Bioinformatics . 7 : 280–302. doi : 10.1186/1471-2105-7-280 . PMC 1502140. PMID  16749936 . 
  19. ^ Hochreiter S , Bodenhofer U, Heusel M, Mayr A, Mitterecker A, Kasim A, Khamiakova T, Van Sanden S, Lin D, Talloen W, Bijnens L, Gohlmann HW, Shkedy Z, Clevert DA (2010). "FABIA: факторный анализ для получения бикластера". Биоинформатика . 26 (12): 1520–1527. doi :10.1093/bioinformatics/btq227. PMC 2881408 . PMID  20418340. 
  20. ^ Orzechowski P, Pańszczyk A, Huang X, Moore JH (2018). "runibic: пакет Bioconductor для параллельной строковой бикластеризации данных по экспрессии генов". Биоинформатика . 34 (24): 4302–4304. doi :10.1093/bioinformatics/bty512. PMC 6289127. PMID  29939213 . 
  21. ^ Orzechowski P, Sipper M, Huang X, Moore JH (2018). «EBIC: параллельный алгоритм бикластеризации на основе эволюции для обнаружения закономерностей». Биоинформатика . 34 (21): 3719–3726. arXiv : 1801.03039 . doi : 10.1093/bioinformatics/bty401. PMC 6198864. PMID  29790909 . 
  22. ^ Fanaee-T H, Thoresen, M (2020). «Итеративная многомодовая дискретизация: приложения к совместной кластеризации». Discovery Science. Lecture Notes in Computer Science. Vol. 12323. pp. 94–105. doi :10.1007/978-3-030-61527-7_7. hdl : 10852/82994 . ISBN 978-3-030-61526-0. S2CID  222832035.
  23. ^ Madeira SC, Teixeira MC, Sá-Correia I, Oliveira AL (2010). «Идентификация регуляторных модулей во временных рядах данных экспрессии генов с использованием алгоритма линейной временной бикластеризации». Труды IEEE/ACM по вычислительной биологии и биоинформатике . 1 (7): 153–165. doi :10.1109/TCBB.2008.34. PMID  20150677. S2CID  7369531.
  24. ^ Madeira SC, Oliveira AL (2009). "Алгоритм бикластеризации с полиномиальным временем для поиска приблизительных моделей экспрессии во временных рядах экспрессии генов". Алгоритмы для молекулярной биологии . 4 (8): 8. doi : 10.1186/1748-7188-4-8 . PMC 2709627. PMID  19497096 . 
  25. ^ Aguilar-Ruiz JS (2005). «Сдвиг и масштабирование шаблонов на основе данных об экспрессии генов». Биоинформатика . 21 (10): 3840–3845. doi : 10.1093/bioinformatics/bti641 . PMID  16144809.
  26. ^ ab Bisson G.; Hussain F. (2008). "Chi-Sim: Новая мера сходства для задачи совместной кластеризации". 2008 Седьмая международная конференция по машинному обучению и приложениям . стр. 211–217. doi :10.1109/ICMLA.2008.103. ISBN 978-0-7695-3495-4. S2CID  15506600.
  27. ^ Can, F.; Ozkarahan, EA (1990). «Концепции и эффективность методологии кластеризации на основе коэффициента покрытия для текстовых баз данных» (PDF) . ACM Transactions on Database Systems . 15 (4): 483–517. doi :10.1145/99935.99938. hdl : 2374.MIA/246 . S2CID  14309214.

Другие

Внешние ссылки