Бикластеризация
Бикластеризация , кластеризация блоков , [1] [2] Совместная кластеризация или двухрежимная кластеризация [3] [4] [5] — это метод интеллектуального анализа данных , который позволяет одновременно кластеризовать строки и столбцы матрицы .Впервые термин был введен Борисом Миркиным. [6] назвать технику, внедренную много лет назад, [6] в 1972 году Джон А. Хартиган . [7]
Учитывая набор образцы, представленные -мерный вектор признаков, весь набор данных можно представить как строки в столбцы (т. е. матрица). Алгоритм бикластеризации генерирует бикластеры. Бикластер — это подмножество строк, которые демонстрируют одинаковое поведение в подмножестве столбцов или наоборот.
Разработка
[ редактировать ]Бикластеризация была первоначально предложена Джоном А. Хартиганом в 1972 году. [7] Термин «бикластеризация» позже был использован и уточнен Борисом Миркиным. Этот алгоритм не получил широкого распространения до 2000 года, когда Ю. Ченг и Джордж М. Черч предложили алгоритм бикластеризации, основанный на среднеквадратичном показателе остатков (MSR), и применили его к данным биологической экспрессии генов. [8]
В 2001 и 2003 годах И.С. Диллон опубликовал два алгоритма, применяющих бикластеризацию к файлам и словам. Одна версия была основана на двудольном разбиении спектрального графа. [9] Другой был основан на теории информации. Диллон предположил, что потеря взаимной информации во время бикластеризации равна расстоянию Кульбака-Лейблера (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, бикластер равен биклике в соответствующем двудольном графе . Максимальный размер Bicluster эквивалентен максимальной реберной биклике в двудольном графе. В сложном случае элемент матрицы A используется для вычисления качества данного бикластера и решения более ограниченной версии проблемы. [13] Это требует либо больших вычислительных усилий, либо использования эвристики с потерями для сокращения вычислений. [14]
Типы бикластеров
[ редактировать ]Бикластер с постоянными значениями (а)
Когда алгоритм бикластеризации пытается найти бикластер с постоянным значением, он меняет порядок строк и столбцов матрицы, чтобы сгруппировать похожие строки и столбцы, в конечном итоге группируя бикластеры со схожими значениями. Этот метод достаточен, когда данные нормализованы. Совершенный постоянный бикластер — это матрица (I, J), в которой все значения a (i, j) равны данной константе μ. В материальных данных эти записи a(i,j) могут быть представлены в форме n(i,j) + µ, где n(i,j) обозначает шум . Согласно алгоритму Хартигана , путем разделения исходной матрицы данных на набор бикластеров дисперсия используется для вычисления постоянных бикластеров. Следовательно, идеальный бикластер можно эквивалентным образом определить как матрицу с нулевой дисперсией. Чтобы предотвратить разделение матрицы данных на бикластеры только с одной строкой и одним столбцом; имеется, например, K Хартиган предполагает, что в матрице данных бикластеров. Когда матрица данных разбивается на K бикластеров, алгоритм завершается.
Бикластер с постоянными значениями в строках (б) или столбцах (в)
В отличие от бикластеров с постоянным значением, эти типы бикластеров не могут быть оценены исключительно на основе дисперсии их значений. Чтобы завершить идентификацию, сначала следует нормализовать столбцы и строки. Однако существуют другие алгоритмы без этапа нормализации, которые могут находить бикластеры, имеющие строки и столбцы, с помощью разных подходов.
Бикластер с согласованными значениями (г, д)
Для бикластеров с согласованными значениями в строках и столбцах следует рассмотреть общее улучшение по сравнению с алгоритмами для бикластеров с постоянными значениями в строках или столбцах. Этот алгоритм может содержать анализ дисперсии между группами, используя ковариацию между строками и столбцами. В теореме Ченга и Чёрча бикластер определяется как подмножество строк и столбцов с почти одинаковым рейтингом. Оценка сходства используется для измерения согласованности строк и столбцов.
|
|
|
|
|
Связь между этими кластерными моделями и другими типами кластеризации, такими как корреляционная кластеризация, обсуждается в статье . [15]
Алгоритмы
[ редактировать ]разработано множество алгоритмов Для биоинформатики бикластеризации , в том числе: блочная кластеризация, CTWC (связанная двусторонняя кластеризация), ITWC (взаимосвязанная двусторонняя кластеризация), δ-бикластер, δ-pCluster, δ-шаблон, FLOC, OPC, плейд-модель. , 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-бикластеризация. [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 определять информационное содержание каждого бикластера, чтобы отделить ложные бикластеры от истинных бикластеров.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Г. Говерт; М. Надиф (2008). «Блочная кластеризация с моделями смеси Бернулли: сравнение различных подходов». Вычислительная статистика и анализ данных . 52 (6): 3233–3245. дои : 10.1016/j.csda.2007.09.007 .
- ^ Р. Баламуруган; А. М. Натараджан; К. Премалатха (2015). «Оптимизация черной дыры звездной массы для бикластеризации данных об экспрессии генов на микрочипах» . Прикладной искусственный интеллект . 29 (4): 353–381. дои : 10.1080/08839514.2015.1016391 . S2CID 44624424 .
- ^ Г. Говерт; М. Надиф (2013). Совместная кластеризация: модели, алгоритмы и приложения . ИСТЭ, Уайли. ISBN 978-1-84821-473-6 .
- ^ Р. Баламуруган; А. М. Натараджан; К. Премалатха (2016). «Модифицированный метод поиска гармонии для бикластеризации данных экспрессии генов на микрочипах». Международный журнал интеллектуального анализа данных и биоинформатики . 16 (4): 269–289. дои : 10.1504/IJDMB.2016.082205 .
- ^ Ван Мехелен I, Бок Х.Х., Де Бок П. (2004). «Двухрежимные методы кластеризации: структурированный обзор». Статистические методы в медицинских исследованиях . 13 (5): 363–94. CiteSeerX 10.1.1.706.4201 . дои : 10.1191/0962280204sm373ra . ПМИД 15516031 . S2CID 19058237 .
- ^ Перейти обратно: а б Миркин, Борис (1996). Математическая классификация и кластеризация . Академическое издательство Клювер. ISBN 978-0-7923-4159-8 .
- ^ Перейти обратно: а б Хартиган Дж. А. (1972). «Прямая кластеризация матрицы данных». Журнал Американской статистической ассоциации . 67 (337): 123–9. дои : 10.2307/2284710 . JSTOR 2284710 .
- ^ https://www.cs.princeton.edu/courses/archive/fall03/cs597F/Articles/biclustering_of_expression_data.pdf Ченг Ю, Чёрч Г. М. Бикластеризация данных о выражениях [C]//Ismb. 2000, 8: 93–103.
- ^ Диллон, Индерджит С. (2001). «Совместная кластеризация документов и слов с использованием разделения двудольного спектрального графа» . Материалы седьмой международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . стр. 269–274. дои : 10.1145/502512.502550 . ISBN 158113391X . S2CID 11847258 .
- ^ Диллон, Индерджит С.; Маллела, Субраманьям; Модха, Дхармендра С. (2003). «Информационно-теоретическая совместная кластеризация» . Материалы девятой международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . стр. 89–98. дои : 10.1145/956750.956764 . ISBN 1581137370 . S2CID 12286784 .
- ^ Банерджи, Ариндам; Диллон, Индерджит; Гош, Джойдип; Меругу, Сруджана; Модха, Дхармендра С. (2004). «Обобщенный подход максимальной энтропии к сокластеризации Брегмана и матричной аппроксимации» . Материалы десятой международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . стр. 509–514. дои : 10.1145/1014052.1014111 . ISBN 1581138881 . S2CID 2719002 .
- ^ Беккерман, Рон; Эль-Янив, Ран; МакКаллум, Эндрю (2005). «Многосторонняя распределительная кластеризация посредством парных взаимодействий» . Материалы 22-й международной конференции по машинному обучению ICML '05 . стр. 41–48. дои : 10.1145/1102351.1102357 . ISBN 1595931805 . S2CID 858524 .
- ^ Питерс Р. (2003). «Задача о максимальной реберной биклике NP-полна» . Дискретная прикладная математика . 131 (3): 651–654. дои : 10.1016/S0166-218X(03)00333-0 . S2CID 3102766 .
- ^ Перейти обратно: а б Мадейра СК, Оливейра АЛ (2004). «Алгоритмы бикластеризации для анализа биологических данных: обзор». Транзакции IEEE/ACM по вычислительной биологии и биоинформатике . 1 (1): 24–45. дои : 10.1109/TCBB.2004.2 . ПМИД 17048406 . S2CID 206628783 .
- ^ Кригель, Х.-П.; Крегер, П.; Зимек, А. (март 2009 г.). «Кластеризация многомерных данных: обзор подпространственной кластеризации, кластеризации на основе шаблонов и корреляционной кластеризации». Транзакции ACM по извлечению знаний из данных . 3 (1): 1–58. дои : 10.1145/1497577.1497578 . S2CID 17363900 .
- ^ Танай А., Шаран Р., Купец М., Шамир Р. (2004). «Выявление модульности и организации молекулярной сети дрожжей путем комплексного анализа весьма гетерогенных данных по всему геному» . Труды Национальной академии наук . 101 (9): 2981–2986. Бибкод : 2004PNAS..101.2981T . дои : 10.1073/pnas.0308661100 . ПМЦ 365731 . ПМИД 14973197 .
- ^ Абдулла, Ахсан; Хусейн, Амир (2006). «Новый метод бикластеризации, основанный на минимизации пересечений». Нейрокомпьютинг . 69 (16–18): 1882–1896. doi : 10.1016/j.neucom.2006.02.018 .
- ^ Рейсс DJ, Балига Н.С., Бонно Р. (2006). «Интегрированная бикластеризация гетерогенных полногеномных наборов данных для вывода о глобальных регуляторных сетях» . БМК Биоинформатика . 7 : 280–302. дои : 10.1186/1471-2105-7-280 . ПМК 1502140 . ПМИД 16749936 .
- ^ Хохрайтер С. , Боденхофер Ю., Хойзель М., Майр А., Миттерекер А., Касим А., Хамиакова Т., Ван Санден С., Лин Д., Таллоен В., Бейненс Л., Гольманн Х.В., Шкеди З., Клеверт Д.А. (2010). «ФАБИЯ: факторный анализ для приобретения бикластеров» . Биоинформатика . 26 (12): 1520–1527. doi : 10.1093/биоинформатика/btq227 . ПМК 2881408 . ПМИД 20418340 .
- ^ Ожеховский П., Паньщик А., Хуан Х., Мур Дж.Х. (2018). «runibic: пакет Bioconductor для параллельной бикластеризации данных экспрессии генов на основе строк» . Биоинформатика . 34 (24): 4302–4304. doi : 10.1093/биоинформатика/bty512 . ПМК 6289127 . ПМИД 29939213 .
- ^ Ожеховский П., Сиппер М., Хуан Х., Мур Дж.Х. (2018). «EBIC: эволюционный алгоритм параллельной бикластеризации для обнаружения закономерностей» . Биоинформатика . 34 (21): 3719–3726. arXiv : 1801.03039 . doi : 10.1093/биоинформатика/bty401 . ПМК 6198864 . ПМИД 29790909 .
- ^ Фанаи-Т, Торесен, М (2020). «Итеративная многорежимная дискретизация: приложения к совместной кластеризации». Наука открытий . Конспекты лекций по информатике. Том. 12323. стр. 94–105. дои : 10.1007/978-3-030-61527-7_7 . hdl : 10852/82994 . ISBN 978-3-030-61526-0 . S2CID 222832035 .
- ^ Мадейра СК, Тейшейра МК, Са-Коррейя I, Оливейра АЛ (2010). «Идентификация регуляторных модулей в данных экспрессии генов временных рядов с использованием алгоритма бикластеризации линейного времени». Транзакции IEEE/ACM по вычислительной биологии и биоинформатике . 1 (7): 153–165. дои : 10.1109/TCBB.2008.34 . ПМИД 20150677 . S2CID 7369531 .
- ^ Мадейра, Южная Каролина, Оливейра, Ал. (2009). «Алгоритм бикластеризации с полиномиальным временем для поиска приблизительных закономерностей экспрессии во временных рядах экспрессии генов» . Алгоритмы молекулярной биологии . 4 (8): 8. дои : 10.1186/1748-7188-4-8 . ПМК 2709627 . ПМИД 19497096 .
- ^ Агилар-Руис Дж.С. (2005). «Сдвиг и масштабирование закономерностей на основе данных об экспрессии генов» . Биоинформатика . 21 (10): 3840–3845. doi : 10.1093/биоинформатика/bti641 . ПМИД 16144809 .
- ^ Перейти обратно: а б Биссон Г.; Хусейн Ф. (2008). «Чи-Сим: новая мера сходства для задачи совместной кластеризации». 2008 Седьмая международная конференция по машинному обучению и приложениям . стр. 211–217. дои : 10.1109/ICMLA.2008.103 . ISBN 978-0-7695-3495-4 . S2CID 15506600 .
- ^ Джан, Ф.; Озкарахан, Э.А. (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 для бикластерного анализа», Семинар IEEE по вычислительному интеллекту: теории, приложения и будущие направления», IIT Kanpur India, стр. 148–152, июль 2013 г.
- А. Танай. Р. Шаран и Р. Шамир, «Алгоритмы бикластеризации: обзор», в Справочнике по вычислительной молекулярной биологии , под редакцией Шриниваса Алуру , Чепмен (2004).
- Клюгер Ю., Басри Р., Чанг Дж.Т., Герштейн М.Б. (2003). «Спектральная бикластеризация данных микрочипов: группировка генов и условий» . Геномные исследования . 13 (4): 703–716. дои : 10.1101/гр.648603 . ПМК 430175 . ПМИД 12671006 .
- Адетайо Касим, Зив Шкеди, Себастьян Кайзер, Зепп Хохрейтер, Виллем Таллоен (2016), Прикладные методы бикластеризации для больших и многомерных данных с использованием R, Chapman & Hall/CRC Press
- Ожеховский П., Сиппер М., Хуанг Х. и Мур Дж. Х. (2018). EBIC: эволюционный алгоритм параллельной бикластеризации для обнаружения закономерностей. Биоинформатика .
Внешние ссылки
[ редактировать ]- FABIA: Факторный анализ для сбора данных о бикластерах, пакет R — программное обеспечение