Agrupación de conjuntos de datos grandes y dispersos

Question

Tengo unos cuantos conjuntos de datos de "interacciones" entre pares de elementos de este tipo:

element1 element2 1
element2 element3 1
element4 element5 1
...
element505535 element4 2

donde el valor de la 3ª columna es la "fuerza" de la interacción. Casi todas estas fuerzas son "1". Una fuerza de 1 significa que esta interacción se observó una vez. Una fuerza de 2 significa 2x, etc. En realidad he ido un paso más allá y normalizado todos mis conjuntos de datos por el número total de interacciones observadas en el conjunto de datos para que los valores de interacción de los conjuntos de datos puedan ser comparados.

Cada archivo contiene entre 5 y 6 millones de interacciones y cada conjunto de datos está obviamente inframuestreado, ya que contiene ~500k elementos (lo que hace una matriz cuadrada de ~250 billones de posiciones).

Me gustaría agrupar estos conjuntos de datos para poder hacer afirmaciones sobre qué tipos de elementos tienden a agruparse con qué otros tipos de elementos. Obviamente, la robustez de la agrupación será un factor a tener en cuenta, pero esto se ve parcialmente mejorado por el hecho de que haré réplicas biológicas de los datos.

He probado algunos enfoques de agrupación "ingenuos" para ver qué podía hacer fácilmente con los datos. Soy plenamente consciente de que se trata de formas problemáticas de agrupación, ya sea porque no son robustas o porque dependen de que los datos estén muy submuestreados, pero esto es lo que he hecho:

1. Agrupar elementos siempre que haya al menos una interacción entre cada elemento del grupo y al menos otro elemento del grupo. Al hacer esto, todos los elementos acaban en un único clúster. Esto era importante hacerlo porque me indica que no hay pares de elementos que estén totalmente aislados del resto del grupo.

2. Encontrar "supercúmulos", es decir, cúmulos en los que cada miembro del cúmulo interactúa con todos los demás miembros del cúmulo (por ejemplo, un triángulo para un cúmulo de 3 y una caja con una X en medio para un cúmulo de 4, etc.). Esto produce casi exclusivamente clusters con 2 y 3 elementos después de que se haya analizado alrededor del 10% de los datos (esto aún está en marcha).

Me encantaría poder hacer algún tipo de agrupación jerárquica utilizando mis valores de "fuerza de interacción" como medida de distancia entre cada par de elementos (las interacciones no observadas tienen una fuerza de 0). ¿Alguien sabe de una manera de hacer HC en este tipo de datos grandes y dispersos, o sabe de un método de agrupación que podría ser más apropiado? Hasta ahora he utilizado R.

Answer 1

¿Son datos de interacción de proteínas? En cualquier caso, hay muchos algoritmos que puedes probar. Soy autor de mcl un algoritmo de agrupación bastante utilizado en bioinformática. Podría probarlo fácilmente, después de instalarlo, dándole los datos exactamente en el formato que describe; la línea de comandos sería "mcl yourdata --abc" (la opción abc indica a mcl que espere este formato concreto). No es necesario ni posible especificar el número de clusters, ya que la estructura de clusters surge del proceso calculado por mcl de forma emergente. Los datos de interacción de proteínas pueden ser bastante voluminosos y ruidosos -- y otras fuentes de datos también, por supuesto. Especialmente la presencia de nodos de muy alto grado (digamos con cientos o miles de vecinos) puede oscurecer la estructura de los clusters. En este escenario, en ausencia de pesos, puede merecer la pena intentar reducir el grafo de entrada mediante, por ejemplo, una transformación k-NN que tenga en cuenta la relación de incidencia del grafo en dos pasos. mcl también proporciona medios para hacer esto, así como una herramienta que enumera varios rasgos del grafo bajo una serie de transformaciones cada vez más estrictas, de forma que sea posible elegir dicha transformación con conocimiento de causa. En cuanto a la agrupación jerárquica, es posible lograr agrupaciones a diferentes niveles de granularidad variando el llamado parámetro de inflación de mcl. Por ejemplo, puede proporcionar tres valores (1,4, 2 y 5) para obtener agrupaciones con distintos niveles de granularidad. También es posible organizar las agrupaciones así obtenidas en una estructura de datos estrictamente jerárquica.