stringtranslate.com

Biclustering

Biclustering , clustering en bloques , [1] [2] Co-clustering o clustering de dos modos [3] [4] [5] es una técnica de minería de datos que permite la agrupación simultánea de las filas y columnas de una matriz . El término fue introducido por primera vez por Boris Mirkin [6] para nombrar una técnica introducida muchos años antes, [6] en 1972, por John A. Hartigan . [7]

Dado un conjunto de muestras representadas por un vector de características de dimensión 1, todo el conjunto de datos se puede representar como filas en columnas (es decir, una matriz). El algoritmo de biclustering genera biclusters. Un bicluster es un subconjunto de filas que exhiben un comportamiento similar en un subconjunto de columnas, o viceversa.

Desarrollo

El biclustering fue introducido originalmente por John A. Hartigan en 1972. [7] El término "Biclustering" fue utilizado y refinado posteriormente por Boris G. Mirkin. Este algoritmo no se generalizó hasta el año 2000, cuando Y. Cheng y George M. Church propusieron un algoritmo de biclustering basado en la puntuación cuadrática media de residuos (MSR) y lo aplicaron a datos de expresión génica biológica. [8]

En 2001 y 2003, IS Dhillon publicó dos algoritmos que aplicaban biclustering a archivos y palabras. Una versión se basaba en la partición de gráficos espectrales bipartitos. [9] La otra se basaba en la teoría de la información. Dhillon supuso que la pérdida de información mutua durante el biclustering era igual a la distancia de Kullback-Leibler (distancia KL) entre P y Q. P representa la distribución de archivos y palabras características antes del biclustering, mientras que Q es la distribución después del biclustering. La distancia KL se utiliza para medir la diferencia entre dos distribuciones aleatorias. KL = 0 cuando las dos distribuciones son iguales y KL aumenta a medida que aumenta la diferencia. [10] Por lo tanto, el objetivo del algoritmo era encontrar la distancia KL mínima entre P y Q. En 2004, Arindam Banerjee utilizó una distancia Bregman ponderada en lugar de una distancia KL para diseñar un algoritmo de biclustering que fuera adecuado para cualquier tipo de matriz, a diferencia del algoritmo de distancia KL. [11]

Para agrupar más de dos tipos de objetos, en 2005 Bekkerman amplió la información mutua en el teorema de Dhillon desde un único par a múltiples pares. [12]

Complejidad

La complejidad del problema de Biclustering depende de la formulación exacta del problema, y ​​particularmente de la función de mérito utilizada para evaluar la calidad de un Bicluster dado. Sin embargo, las variantes más interesantes de este problema son NP-completo . NP-completo tiene dos condiciones. En el caso simple de que haya un único elemento a ( i , j ) ya sea 0 o 1 en la matriz binaria A, un Bicluster es igual a un biclique en el grafo bipartito correspondiente . El tamaño máximo de Bicluster es equivalente al biclique de arista máxima en el grafo bipartito. En el caso complejo, el elemento en la matriz A se utiliza para calcular la calidad de un Bicluster dado y resolver la versión más restringida del problema. [13] Requiere un gran esfuerzo computacional o el uso de heurísticas con pérdida para acortar el cálculo. [14]

Tipos de biclústeres

Bicluster con valores constantes (a)

Cuando un algoritmo de Biclustering intenta encontrar un Bicluster de valor constante, reordena las filas y columnas de la matriz para agrupar filas y columnas similares, y finalmente agrupar Biclusters con valores similares. Este método es suficiente cuando los datos están normalizados. Un Bicluster constante perfecto es una matriz (I,J) en la que todos los valores a(i,j) son iguales a una constante dada μ. En datos tangibles, estas entradas a(i,j) pueden representarse con la forma n(i,j) + μ donde n(i,j) denota el ruido . Según el algoritmo de Hartigan, al dividir la matriz de datos original en un conjunto de Biclusters, se utiliza la varianza para calcular Biclusters constantes. Por lo tanto, un Bicluster perfecto puede definirse de manera equivalente como una matriz con una varianza de cero. Para evitar la partición de la matriz de datos en Biclusters con solo una fila y una columna, Hartigan supone que hay, por ejemplo, K Biclusters dentro de la matriz de datos. Cuando la matriz de datos se divide en K biclusters, el algoritmo finaliza.

Bicluster con valores constantes en filas (b) o columnas (c)

A diferencia de los Biclusters de valor constante, estos tipos de Biclusters no se pueden evaluar únicamente en función de la varianza de sus valores. Para finalizar la identificación, primero se deben normalizar las columnas y las filas. Sin embargo, existen otros algoritmos, sin el paso de normalización, que pueden encontrar Biclusters que tienen filas y columnas con diferentes enfoques.

Bicluster con valores coherentes (d, e)

En el caso de los Biclusters con valores coherentes en filas y columnas, se debe considerar una mejora general con respecto a los algoritmos para Biclusters con valores constantes en filas o columnas. Este algoritmo puede contener un análisis de varianza entre grupos, utilizando la covarianza entre filas y columnas. En el teorema de Cheng y Church, un Bicluster se define como un subconjunto de filas y columnas con casi la misma puntuación. La puntuación de similitud se utiliza para medir la coherencia de filas y columnas.



La relación entre estos modelos de clúster y otros tipos de agrupamiento, como el agrupamiento por correlación, se analiza en [15] .

Algoritmos

Existen muchos algoritmos de biclustering desarrollados para bioinformática , incluyendo: agrupamiento en bloques, CTWC (agrupamiento bidireccional acoplado), ITWC (agrupamiento bidireccional interrelacionado), δ-bicluster, δ-pCluster, δ-pattern, FLOC, OPC, modelo Plaid, OPSMs (submatrices que preservan el orden), Gibbs, SAMBA (método estadístico-algorítmico para análisis de bicluster), [16] algoritmo de biclustering robusto (RoBA), minimización de cruces, [17] cMonkey, [18] PRMs, DCC, LEB (localizar y extraer biclusters), QUBIC (BIClustering cualitativo), BCCA (algoritmo de agrupamiento bicorrelativo), BIMAX, ISA y FABIA ( análisis factorial para adquisición de bicluster), [19] runibic, [20] y el método híbrido propuesto recientemente EBIC. (Biclustering basado en la evolución), [21] que demostró detectar múltiples patrones con una precisión muy alta. Más recientemente, se propuso IMMD-CC [22] , que se desarrolló con base en el concepto de reducción de complejidad iterativa. IMMD-CC puede identificar centroides de co-cúmulos a partir de una transformación altamente dispersa obtenida mediante discretización iterativa multimodo.

También se han propuesto y utilizado algoritmos de biclustering en otros campos de aplicación bajo los nombres de co-clustering, agrupamiento bidimensional y agrupamiento de subespacios. [14]

Dada la importancia conocida de descubrir patrones locales en datos de series temporales , propuestas recientes han abordado el problema del Biclustering en el caso específico de datos de expresión génica de series temporales . En este caso, los Biclusters interesantes pueden restringirse a aquellos con columnas contiguas. Esta restricción conduce a un problema manejable y permite el desarrollo de algoritmos de enumeración exhaustivos y eficientes como CCC-Biclustering [23] y e -CCC-Biclustering. [24] Los patrones aproximados en los algoritmos CCC-Biclustering permiten un número dado de errores, por gen, en relación con un perfil de expresión que representa el patrón de expresión en el Bicluster. El algoritmo e-CCC-Biclustering utiliza expresiones aproximadas para encontrar y reportar todos los CCC-Bicluster máximos mediante una matriz discretizada A y técnicas de procesamiento de cadenas eficientes.

Estos algoritmos encuentran y reportan todos los Biclusters máximos con columnas coherentes y contiguas con patrones de expresión perfectos/aproximados, en tiempo lineal/ polinomial que se obtiene manipulando una versión discretizada de la matriz de expresión original en el tamaño de la matriz de expresión génica de series temporales utilizando técnicas de procesamiento de cadenas eficientes basadas en árboles de sufijos . Estos algoritmos también se aplican para resolver problemas y esbozar el análisis de la complejidad computacional.

Algunos algoritmos recientes han intentado incluir soporte adicional para matrices rectangulares biclusterizadas en forma de otros tipos de datos , incluido cMonkey.

Existe un debate en curso sobre cómo juzgar los resultados de estos métodos, ya que el Biclustering permite la superposición entre clústeres y algunos algoritmos permiten la exclusión de columnas/condiciones difíciles de conciliar. No todos los algoritmos disponibles son deterministas y el analista debe prestar atención al grado en que los resultados representan mínimos estables . Debido a que este es un problema de clasificación no supervisada , la falta de un estándar de oro dificulta la detección de errores en los resultados. Un enfoque es utilizar múltiples algoritmos de Biclustering, con la mayoría o supermayoría votando entre ellos para decidir el mejor resultado. Otra forma es analizar la calidad de los patrones de cambio y escala en Biclusters. [25] El Biclustering se ha utilizado en el dominio de la minería de texto (o clasificación) que popularmente se conoce como co-clustering. [26] Los corpus de texto se representan en forma vectorial como una matriz D cuyas filas denotan los documentos y cuyas columnas denotan las palabras en el diccionario. Los elementos de la matriz D ij denotan la ocurrencia de la palabra j en el documento i. Luego se aplican algoritmos de co-agrupamiento para descubrir bloques en D que corresponden a un grupo de documentos (filas) caracterizados por un grupo de palabras (columnas).

La agrupación de texto puede resolver el problema de dispersión de alta dimensión, lo que significa agrupar texto y palabras al mismo tiempo. Al agrupar texto, debemos pensar no solo en la información de las palabras, sino también en la información de los grupos de palabras que se componen de palabras. Luego, de acuerdo con la similitud de las palabras características en el texto, eventualmente agruparemos las palabras características. Esto se llama co-agrupación. Hay dos ventajas de la co-agrupación: una es que agrupar la prueba en función de los grupos de palabras puede reducir extremadamente la dimensión de la agrupación, también puede ser apropiado para medir la distancia entre las pruebas. La segunda es extraer información más útil y puede obtener la información correspondiente en los grupos de prueba y los grupos de palabras. Esta información correspondiente se puede utilizar para describir el tipo de textos y palabras, al mismo tiempo, el resultado de la agrupación de palabras también se puede utilizar para la minería de texto y la recuperación de información.

Se han propuesto varios enfoques basados ​​en el contenido de información de los bloques resultantes: enfoques basados ​​en matrices como SVD y BVD, y enfoques basados ​​en grafos. Los algoritmos basados ​​en la teoría de la información asignan iterativamente cada fila a un grupo de documentos y cada columna a un grupo de palabras de modo que se maximice la información mutua. Los métodos basados ​​en matrices se centran en la descomposición de matrices en bloques de modo que se minimice el error entre la matriz original y las matrices regeneradas a partir de la descomposición. Los métodos basados ​​en grafos tienden a minimizar los cortes entre los grupos. Dados dos grupos de documentos d 1 y d 2 , el número de cortes se puede medir como el número de palabras que aparecen en los documentos de los grupos d 1 y d 2 .

Más recientemente (Bisson y Hussain) [26] han propuesto un nuevo enfoque de uso de la similitud entre palabras y la similitud entre documentos para co-agrupar la matriz. Su método (conocido como χ-Sim , por similitud cruzada) se basa en encontrar similitud documento-documento y similitud palabra-palabra, y luego usar métodos de agrupamiento clásicos como el agrupamiento jerárquico . En lugar de agrupar explícitamente filas y columnas alternativamente, consideran ocurrencias de orden superior de palabras, teniendo en cuenta inherentemente los documentos en los que ocurren. Por lo tanto, la similitud entre dos palabras se calcula en función de los documentos en los que ocurren y también de los documentos en los que ocurren palabras "similares". La idea aquí es que dos documentos sobre el mismo tema no necesariamente usan el mismo conjunto de palabras para describirlo, sino un subconjunto de las palabras y otras palabras similares que son características de ese tema. Este enfoque de tomar similitudes de orden superior toma en consideración la estructura semántica latente de todo el corpus con el resultado de generar una mejor agrupación de los documentos y las palabras.

En bases de datos de texto, para una colección de documentos definida por una matriz de documentos por términos D (de tamaño m por n, m: número de documentos, n: número de términos), la metodología de agrupamiento basada en coeficiente de cobertura [27] produce el mismo número de clústeres tanto para documentos como para términos (palabras) utilizando un experimento de probabilidad de dos etapas. De acuerdo con el concepto de coeficiente de cobertura, el número de clústeres también se puede estimar de manera aproximada mediante la siguiente fórmula , donde t es el número de entradas distintas de cero en D. Nótese que en D cada fila y cada columna debe contener al menos un elemento distinto de cero.

A diferencia de otros enfoques, FABIA es un modelo multiplicativo que supone distribuciones de señales no gaussianas realistas con colas pesadas . FABIA utiliza técnicas de selección de modelos bien conocidas, como enfoques variacionales, y aplica el marco bayesiano . El marco generativo permite a FABIA determinar el contenido de información de cada Bicluster para separar los Biclusters espurios de los verdaderos.

Véase también

Referencias

  1. ^ G. Govaert; M. Nadif (2008). "Agrupamiento de bloques con modelos de mezcla de Bernoulli: Comparación de diferentes enfoques". Estadística computacional y análisis de datos . 52 (6): 3233–3245. doi :10.1016/j.csda.2007.09.007.
  2. ^ R. Balamurugan; AM Natarajan; K. Premalatha (2015). "Optimización de agujeros negros de masa estelar para datos de expresión génica de microarrays en bicluster". Inteligencia artificial aplicada . 29 (4): 353–381. doi : 10.1080/08839514.2015.1016391 . S2CID  44624424.
  3. ^ G. Govaert; M. Nadif (2013). Co-clustering: modelos, algoritmos y aplicaciones . ISTE, Wiley. ISBN 978-1-84821-473-6.
  4. ^ R. Balamurugan; AM Natarajan; K. Premalatha (2016). "Un método de búsqueda de armonía modificado para datos de expresión génica de microarrays en bicluster". Revista internacional de minería de datos y bioinformática . 16 (4): 269–289. doi :10.1504/IJDMB.2016.082205.
  5. ^ Van Mechelen I, Bock HH, De Boeck P (2004). "Métodos de agrupamiento de dos modos: una descripción general estructurada". Métodos estadísticos en la investigación médica . 13 (5): 363–94. CiteSeerX 10.1.1.706.4201 . doi :10.1191/0962280204sm373ra. PMID  15516031. S2CID  19058237.  
  6. ^ ab Mirkin, Boris (1996). Clasificación matemática y agrupamiento . Kluwer Academic Publishers. ISBN 978-0-7923-4159-8.
  7. ^ ab Hartigan JA (1972). "Agrupamiento directo de una matriz de datos". Revista de la Asociación Estadounidense de Estadística . 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 Cheng Y, Church G M. Biclustering de datos de expresión[C]//Ismb. 2000, 8: 93–103.
  9. ^ Dhillon, Inderjit S. (2001). "Co-clustering documents and words using bipartite spectral graph particioning" (Agrupamiento de documentos y palabras mediante particionamiento de grafos espectrales bipartitos). Actas de la séptima conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos . págs. 269–274. doi :10.1145/502512.502550. ISBN 158113391X.S2CID11847258  .​
  10. ^ Dhillon, Inderjit S.; Mallela, Subramanyam; Modha, Dharmendra S. (2003). "Agrupamiento conjunto de teoría de la información". Actas de la novena conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos . págs. 89–98. doi :10.1145/956750.956764. ISBN 1581137370. Número de identificación del sujeto  12286784.
  11. ^ Banerjee, Arindam; Dhillon, Inderjit; Ghosh, Joydeep; Merugu, Srujana; Modha, Dharmendra S. (2004). "Un enfoque generalizado de máxima entropía para la agrupación conjunta de Bregman y la aproximación matricial". Actas de la décima conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos . págs. 509–514. doi :10.1145/1014052.1014111. ISBN . 1581138881. Número de identificación del sujeto  2719002.
  12. ^ Bekkerman, Ron; El-Yaniv, Ran; McCallum, Andrew (2005). "Agrupamiento distributivo multidireccional mediante interacciones por pares". Actas de la 22.ª conferencia internacional sobre aprendizaje automático - ICML '05 . págs. 41–48. doi :10.1145/1102351.1102357. ISBN 1595931805.S2CID858524  .​
  13. ^ Peeters R (2003). "El problema biclicuo de arista máxima es NP-completo". Matemáticas Aplicadas Discretas . 131 (3): 651–654. doi : 10.1016/S0166-218X(03)00333-0 . S2CID  3102766.
  14. ^ ab Madeira SC, Oliveira AL (2004). "Algoritmos de biclustering para análisis de datos biológicos: una encuesta". Transacciones IEEE/ACM sobre biología computacional y bioinformática . 1 (1): 24–45. doi :10.1109/TCBB.2004.2. PMID  17048406. S2CID  206628783.
  15. ^ Kriegel, H.-P.; Kröger, P.; Zimek, A. (marzo de 2009). "Agrupamiento de datos de alta dimensión: un estudio sobre agrupamiento de subespacios, agrupamiento basado en patrones y agrupamiento por correlación". ACM Transactions on Knowledge Discovery from Data . 3 (1): 1–58. doi :10.1145/1497577.1497578. S2CID  17363900.
  16. ^ Tanay A, Sharan R, Kupiec M, Shamir R (2004). "Revelando modularidad y organización en la red molecular de la levadura mediante análisis integrado de datos altamente heterogéneos de todo el genoma". Actas de la Academia Nacional de Ciencias . 101 (9): 2981–2986. Bibcode :2004PNAS..101.2981T. doi : 10.1073/pnas.0308661100 . PMC 365731 . PMID  14973197. 
  17. ^ Abdullah, Ahsan; Hussain, Amir (2006). "Una nueva técnica de biclustering basada en la minimización de cruces". Neurocomputing . 69 (16–18): 1882–1896. doi :10.1016/j.neucom.2006.02.018.
  18. ^ Reiss DJ, Baliga NS, Bonneau R (2006). "Biclustering integrado de conjuntos de datos heterogéneos de todo el genoma para la inferencia de redes reguladoras globales". 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: análisis factorial para adquisición de bicluster". Bioinformática . 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: un paquete Bioconductor para la biagrupación en filas paralelas de datos de expresión génica". Bioinformática . 34 (24): 4302–4304. doi :10.1093/bioinformatics/bty512. PMC 6289127 . PMID  29939213. 
  21. ^ Orzechowski P, Sipper M, Huang X, Moore JH (2018). "EBIC: un algoritmo de biclustering paralelo basado en la evolución para el descubrimiento de patrones". Bioinformática . 34 (21): 3719–3726. arXiv : 1801.03039 . doi :10.1093/bioinformatics/bty401. PMC 6198864 . PMID  29790909. 
  22. ^ Fanaee-T H, Thoresen, M (2020). "Discretización iterativa multimodo: aplicaciones a la agrupación en clústeres". Discovery Science. Lecture Notes in Computer Science. Vol. 12323. págs. 94–105. doi :10.1007/978-3-030-61527-7_7. hdl : 10852/82994 . ISBN . 978-3-030-61526-0. Número de identificación del sujeto  222832035.
  23. ^ Madeira SC, Teixeira MC, Sá-Correia I, Oliveira AL (2010). "Identificación de módulos reguladores en datos de expresión génica en series temporales utilizando un algoritmo de biclustering en tiempo lineal". Transacciones IEEE/ACM sobre biología computacional y bioinformática . 1 (7): 153–165. doi :10.1109/TCBB.2008.34. PMID  20150677. S2CID  7369531.
  24. ^ Madeira SC, Oliveira AL (2009). "Un algoritmo de biclustering de tiempo polinomial para encontrar patrones de expresión aproximados en series temporales de expresión génica". Algoritmos para la biología molecular . 4 (8): 8. doi : 10.1186/1748-7188-4-8 . PMC 2709627 . PMID  19497096. 
  25. ^ Aguilar-Ruiz JS (2005). "Patrones de cambio y escalamiento a partir de datos de expresión génica". Bioinformática . 21 (10): 3840–3845. doi : 10.1093/bioinformatics/bti641 . PMID  16144809.
  26. ^ ab Bisson G.; Hussain F. (2008). "Chi-Sim: una nueva medida de similitud para la tarea de co-agrupamiento". Séptima Conferencia Internacional sobre Aprendizaje Automático y Aplicaciones , 2008. págs. 211–217. doi :10.1109/ICMLA.2008.103. ISBN 978-0-7695-3495-4.S2CID15506600  .​
  27. ^ Can, F.; Ozkarahan, EA (1990). "Conceptos y efectividad de la metodología de agrupamiento basada en coeficientes de cobertura para bases de datos de texto" (PDF) . ACM Transactions on Database Systems . 15 (4): 483–517. doi :10.1145/99935.99938. hdl : 2374.MIA/246 . S2CID  14309214.

Otros

Enlaces externos