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

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

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

Разработка

Бикластеризация была впервые введена Дж. А. Хартиганом в 1972 году.[8] Термин бикластеризация позже употребил Миркин. Этот алгоритм не был обобщен до 2000 года, когда Я. Ченг и Г. М. Черч предложили алгоритм бикластеризации, основанный на дисперсии, и применили его к данным экспрессии биологических генов.[9] Их статья до сих пор остается самой важной литературой в области бикластеризации экспрессии генов.

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

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

Сложность

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

Тип бикластера

Различные алгоритмы бикластеризации имеют разные определения бикластера.[14]

Они есть:

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

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

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

2. бикластеры с постоянными значениями в строках или столбцах

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

3.Бикластеры с согласованными значениями

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


а) Бикластер с постоянными значениями
2.02.02.02.02.0
2.02.02.02.02.0
2.02.02.02.02.0
2.02.02.02.02.0
2.02.02.02.02.0
б) Бикластер с постоянными значениями в строках
1.01.01.01.01.0
2.02.02.02.02.0
3.03.03.03.03.0
4.04.04.04.04.0
5.05.05.05.05.0
в) Бикластер с постоянными значениями по столбцам
1.02.03.04.05.0
1.02.03.04.05.0
1.02.03.04.05.0
1.02.03.04.05.0
1.02.03.04.05.0
г) Бикластер с когерентными значениями (аддитивный)
1.04.05.00.01.5
4.07.08.03.04.5
3.06.07.02.03.5
5.08.09.04.05.5
2.05.06.01.02.5
д) Бикластер с когерентными значениями (мультипликативный)
1.00.52.00.20.8
2.01.04.00.41.6
3.01.56.00.62.4
4.02.08.00.83.2
5.02.510.01.04.0


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

Алгоритмы

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


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

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

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

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

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

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

На основе информационного содержания результирующих блоков было предложено несколько подходов: матричные подходы, такие как СВД и BVD, и подходы на основе графиков. Теоретико-информационная алгоритмы итеративно назначьте каждую строку кластеру документов, а каждый столбец - кластеру слов, чтобы общая информация была максимальной. Методы, основанные на матрицах, сосредоточены на разложении матриц на блоки, так что ошибка между исходной матрицей и регенерированными матрицами из разложения сводится к минимуму. Графические методы, как правило, сводят к минимуму разрезы между кластерами. Учитывая две группы документов d1 и г2, количество сокращений можно измерить как количество слов, которые встречаются в документах групп d1 и г2.

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

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

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

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

Рекомендации

  1. ^ Г. Говерт; М. Надиф (2008). «Блочная кластеризация с моделями смеси Бернулли: Сравнение различных подходов». Вычислительная статистика и анализ данных. 52 (6): 3233–3245. Дои:10.1016 / j.csda.2007.09.007.
  2. ^ Р. Баламуруган; ЯВЛЯЮСЬ. Натараджан; К. Премалата (2015). "Оптимизация звездной массы черных дыр для бикластеризации данных экспрессии генов микрочипов". Прикладной искусственный интеллект в международном журнале. 29 (4): 353–381. Дои:10.1080/08839514.2015.1016391. S2CID  44624424.
  3. ^ Г. Говерт; М. Надиф (2013). Совместная кластеризация: модели, алгоритмы и приложения. ISTE, Wiley. ISBN  978-1-84821-473-6.
  4. ^ Р. Баламуруган; ЯВЛЯЮСЬ. Натараджан; К. Премалата (2016). «Модифицированный метод поиска гармонии для данных экспрессии генов микроматрицы бикластеризации». Международный журнал интеллектуального анализа данных и биоинформатики. 16 (4): 269–289. Дои:10.1504 / IJDMB.2016.082205.
  5. ^ Ван Мехелен I, Бок Х. Х., Де Бок П. (2004). «Двухрежимные методы кластеризации: структурированный обзор». Статистические методы в медицинских исследованиях. 13 (5): 363–94. CiteSeerX  10.1.1.706.4201. Дои:10.1191 / 0962280204см373ра. PMID  15516031. S2CID  19058237.
  6. ^ а б Миркин, Борис (1996). Математическая классификация и кластеризация. Kluwer Academic Publishers. ISBN  978-0-7923-4159-8.
  7. ^ Хартиган Дж. А. (1972). «Прямая кластеризация матрицы данных». Журнал Американской статистической ассоциации. 67 (337): 123–9. Дои:10.2307/2284710. JSTOR  2284710.
  8. ^ Хартиган Дж. А. (1972). «Прямая кластеризация матрицы данных». Журнал Американской статистической ассоциации. 67 (337): 123–129. Дои:10.1080/01621459.1972.10481214.
  9. ^ https://www.cs.princeton.edu/courses/archive/fall03/cs597F/Articles/biclustering_of_expression_data.pdf Cheng Y, Church G M. Бикластеризация данных выражения [C] // Ismb. 2000, 8: 93–103.
  10. ^ Диллон И. С. Совместная кластеризация документов и слов с использованием разделения двудольного спектрального графа [C] // Труды седьмой международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных. АКМ, 2001: 269–274.
  11. ^ Диллон И. С., Маллела С., Модха Д. С. Информационно-теоретическая совместная кластеризация [C] // Труды девятой международной конференции ACM SIGKDD по открытию знаний и интеллектуальному анализу данных в KKluwer Academic Publisher. АКМ, 2003: 89–98.
  12. ^ Банерджи А., Диллон И., Гош Дж. И др. Обобщенный подход максимальной энтропии к совместной кластеризации Брегмана и аппроксимации матриц [C] // Труды десятой международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных. АКМ, 2004: 509–514.
  13. ^ Пеэтерс Р. (2003). «Задача максимальной краевой биклики является NP-полной». Дискретная прикладная математика. 131 (3): 651–654. Дои:10.1016 / S0166-218X (03) 00333-0.
  14. ^ а б c Мадейра, Южная Каролина, Оливейра А.Л. (2004). «Алгоритмы бикластеризации для анализа биологических данных: обзор». IEEE / ACM Transactions по вычислительной биологии и биоинформатике. 1 (1): 24–45. Дои:10.1109 / TCBB.2004.2. PMID  17048406. S2CID  206628783.
  15. ^ Kriegel, H.-P .; Kröger, P .; Зимек, А. (март 2009 г.). «Кластеризация многомерных данных: обзор кластеризации подпространств, кластеризации на основе шаблонов и корреляционной кластеризации». Транзакции ACM при обнаружении знаний из данных. 3 (1): 1–58. Дои:10.1145/1497577.1497578. S2CID  17363900.
  16. ^ Танай А., Шаран Р., Купец М., Шамир Р. (2004). «Выявление модульности и организации в молекулярной сети дрожжей с помощью комплексного анализа высокогетерогенных данных по всему геному». Proc Natl Acad Sci USA. 101 (9): 2981–2986. Bibcode:2004ПНАС..101.2981Т. Дои:10.1073 / pnas.0308661100. ЧВК  365731. PMID  14973197.
  17. ^ Абдулла, Ахсан; Хуссейн, Амир (2006). «Новый метод бикластеризации, основанный на минимизации пересечений». Нейрокомпьютинг. 69 (16–18): 1882–1896. Дои:10.1016 / j.neucom.2006.02.018.
  18. ^ Рейсс DJ, Балига Н.С., Бонно Р. (2006). «Интегрированная бикластеризация разнородных наборов данных по всему геному для вывода глобальных регуляторных сетей». BMC Биоинформатика. 7: 280–302. Дои:10.1186/1471-2105-7-280. ЧВК  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 HWH, Shkedy Z, Clevert DA (2010). «FABIA: факторный анализ для бикластерного приобретения». Биоинформатика. 26 (12): 1520–1527. Дои:10.1093 / биоинформатика / btq227. ЧВК  2881408. PMID  20418340.
  20. ^ Ожеховски П., Паньщик А., Хуанг Х, Мур Дж. Х. (2018). "runibic: пакет Bioconductor для параллельной строковой бикластеризации данных экспрессии генов". Биоинформатика. 34 (24): 4302–4304. Дои:10.1093 / биоинформатика / bty512. ЧВК  6289127. PMID  29939213.
  21. ^ Орзеховски П., Зиппер М., Хуанг X, Мур Дж. Х. (2018). «EBIC: эволюционный алгоритм параллельной бикластеризации для обнаружения паттернов». Биоинформатика. 34 (21): 3719–3726. arXiv:1801.03039. Дои:10.1093 / биоинформатика / bty401. ЧВК  6198864. PMID  29790909.
  22. ^ Fanaee-T H, Thoresen, M (2020). «Итеративная многомодовая дискретизация: приложения для совместной кластеризации». Конспект лекций по информатике. 12323: 94–105. Дои:10.1007/978-3-030-61527-7_7. ISBN  978-3-030-61526-0.
  23. ^ Madeira SC, Teixeira MC, Sá-Correia I, Oliveira AL (2010). «Идентификация регуляторных модулей в данных экспрессии генов временного ряда с использованием алгоритма линейной временной бикластеризации». IEEE / ACM Transactions по вычислительной биологии и биоинформатике. 1 (7): 153–165. Дои:10.1109 / TCBB.2008.34. PMID  20150677. S2CID  7369531.
  24. ^ Мадейра, Южная Каролина, Оливейра А.Л. (2009). «Алгоритм бикластеризации с полиномиальным временем для поиска приблизительных паттернов экспрессии во временных рядах экспрессии генов». Алгоритмы молекулярной биологии. 4 (8): 8. Дои:10.1186/1748-7188-4-8. ЧВК  2709627. PMID  19497096.
  25. ^ Агилар-Руис Ж.С. (2005). «Сдвиг и масштабирование паттернов из данных экспрессии генов». Биоинформатика. 21 (10): 3840–3845. Дои:10.1093 / биоинформатика / bti641. PMID  16144809.
  26. ^ а б Биссон Г. и Хуссейн Ф. (2008). Chi-Sim: новая мера сходства для задачи совместной кластеризации. ICMLA. С. 211–217. Дои:10.1109 / ICMLA.2008.103. ISBN  978-0-7695-3495-4. S2CID  15506600.
  27. ^ Can, F .; Озкарахан, Э. А. (1990). «Концепции и эффективность методологии кластеризации на основе коэффициента покрытия для текстовых баз данных» (PDF). Транзакции ACM в системах баз данных. 15 (4): 483–517. Дои:10.1145/99935.99938. HDL:2374.MIA / 246. S2CID  14309214.

Другие

  • Н.К. Верма, С. Баджпай, А. Сингх, А. Награре, С. Мина, Ян Цуй, «Сравнение алгоритмов бикластеризации» на Международной конференции по системам в медицине и биологии (ICSMB 2010) в ИИТ Харагпур, Индия, стр. 90– 97, 16–18 декабря.
  • Дж. Гупта, С. Сингх и Н.К. Верма «MTBA: MATLAB Toolbox для анализа бикластеризации», Семинар IEEE по вычислительному интеллекту: теории, приложения и будущие направления », IIT Kanpur India, стр. 148–152, июль 2013 г.
  • А. Танай. Р. Шаран и Р. Шамир, "Алгоритмы бикластеризации: обзор", In Справочник по вычислительной молекулярной биологии, Отредактировано Шринивас Алуру, Чепмен (2004)
  • Клюгер Y, Басри Р., Чанг Дж. Т., Герштейн МБ (2003). «Спектральная бикластеризация данных микрочипов: гены и условия совместной кластеризации». Геномные исследования. 13 (4): 703–716. Дои:10.1101 / гр.648603. ЧВК  430175. PMID  12671006.
  • Адетайо Касим, Зив Шкеди, Себастьян Кайзер, Зепп Хохрайтер, Виллем Таллоен (2016), Прикладные методы бикластеризации для больших и многомерных данных с использованием R, Chapman & Hall / CRC Press
  • Орзеховски П., Сиппер М., Хуанг X. и Мур Дж. Х. (2018). EBIC: эволюционный алгоритм параллельной бикластеризации для обнаружения паттернов. Биоинформатика.

внешняя ссылка