1. Inicio
  2. Pregunta y respuesta
  3. Agrupamiento de un conjunto de datos dispersos de vectores binarios

Agrupamiento de un conjunto de datos dispersos de vectores binarios

2011-12-20 10 views
5

Si tengo un conjunto de datos disperso donde cada dato se describe mediante un vector de 1000 elementos, cada elemento de este vector puede ser 0 o 1 (mucho 0 y algo 1), ¿Conoces alguna función de distancia que pueda ayudarme a agruparlos? ¿Es algo así como la distancia euclidiana conveniente en este caso? Me gustaría saber si existe una medida de distancia conveniente y simple para una situación así, para probar mis datos.Agrupamiento de un conjunto de datos dispersos de vectores binarios

Gracias

Fuente

2011-12-20 shn

+0

¿Qué hay de la función de distorsión utilizada en K-meloids? No es muy diferente de la distancia euclidiana. – Neo

+0

@CRK K-meloids usa [distancia de Minkowski] (http://en.wikipedia.org/wiki/Minkowski_distance) con p = 1, que es un caso general de distancia euclidiana, ¿no es así? – shn

Respuesta

3

Tener un vistazo a las funciones de distancia utilizadas para los vectores de texto dispersos, tales como coseno distancia y para comparar conjuntos, como la distancia de Jaccard.

Fuente

2011-12-21 08:10:13

0

si realmente es un montón de 0 y 1 unos pocos, que podrían tratar de agrupamiento para la primera o la última 1 - ver http://aggregate.org/MAGIC/#Least significativo Bit 1

Fuente

2011-12-20 08:45:37

+0

¿Primero o el último? ¿Cómo se define la función métrica entre los dos vectores en este caso? Distancia (V1, V2) – shn

10

Su pregunta no disponga de una respuesta. Hay mejores prácticas dependiendo del dominio.

Una vez que decida la similitud de la métrica, la agrupación generalmente se realiza promediando o encontrando un medoide. Ver estos papeles en datos binarios de agrupamiento para ejemplos de algoritmos:

  • Carlos Ordóñez. Agrupamiento de flujos de datos binarios con K-means. PDF
  • Tao Li. Un modelo general para agrupar datos binarios. PDF

Para obtener ideas sobre medidas de similitud ver esta línea "tool for measuring similarity between binary strings". Mencionan: Sokal-Michener, Jaccard, Russell-Rao, Hamann, Sorensen, AntiDice, Sneath-Sokal, Rodger-Tanimoto, Ochiai, Yule, Anderberg, Kulczynski, Pearson's Phi, y Gower2, Dot Product, Cosine Coefficient, Hamming Distance. También citan estos documentos:

  • Lucas, B. T., Clustering binario Objetos
  • Lin, D., una definición de información teórica de similitud.
  • Toit, du S.H.C .; Steyn, A.G.W .; Stumpf, R.H .; Análisis gráfico de datos exploratorios; Capítulo 3, p. 77, 1986; Springer-Verlag.

(personalmente me gusta el coseno. También hay KL-divergencia, y su homólogo de distancia Jensen.)

Fuente

2011-12-20 10:39:55 cyborg

+0

Gracias por su respuesta, este es un enlace interesante. Pero, digamos que usamos Hamming (o coseno o cualquier otra distancia), ¿cómo podemos aprender el representante de cada grupo de vectores?Quiero decir, digamos que tenemos v1 = 0100100001100 y v2 = 0001100001100, están cerca uno del otro ya que difieren solo en dos bits (la 2da y 3ra posiciones), entonces la distancia de Hamming por ejemplo será 2 (el coseno será 0.7500), el problema es: ¿cuál será el vector representativo de v1 y v2? Cómo (aprender) solo los valores del vector que deberían representar v1 y v2 y todos los demás vectores que están cerca de ellos. – shn

+1

El vector representativo es un promedio (* centroid *, no binario) o un * medoid *. Lea los documentos para encontrar ejemplos sobre cómo encontrarlos. – cyborg

+1

Herramienta de vínculo muerto para medir similitudes entre cadenas binarias – Ahue

Cuestiones relacionadas

 Cuestiones relacionadas