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.
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]
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]
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] .
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.
