Agrupación sin una matriz de distancia

Question

Recientemente he terminado un proyecto en el que he utilizado scikit-learn DBSCAN módulo para encontrar los clústeres en un plazo relativamente corto de cadenas de texto. He utilizado una cadena personalizada de la similitud métrica para permitir vectorizados cómputo de un $n^2$ matriz de similitud.

Sé que es posible reducir el tiempo de la complejidad de DBSCAN a $O(n \, \log n)$ mediante el uso de un apropiado ($O(\log n)$ tiempo de búsqueda) indexación de la estructura para la búsqueda de los vecinos de un determinado punto de datos. DBSCAN Tiempo de complejidad

¿Cómo puedo lograr esto cuando mis datos son binarios función de los vectores de longitud 1296? Es allí una manera eficaz para el índice de búsquedas de puntos con un número arbitrario de dimensiones? Si esto es así, esta funcionalidad integrada en scikit-learn o tengo que rollo mi propia solución?

Answer 1

Invertida listas funcionan muy bien para los datos dispersos. Esto es lo que por ejemplo, utiliza Lucene.

No sé cómo extensible scikit-learn. Un montón de código parece estar escrito en Cython, por lo que es Python-como el código compilado a través de la C. de Este modo, sería más difícil de extender.

ELKI, la herramienta de minería de datos yo estoy contribuyendo mucho, tiene un - aún inédito y de indocumentados, Lucene addon. Esto podría funcionar para usted. Espero que en algún momento también tienen un índice invertido dispersas vectores en ELKI principal (debido a la Lucene dependencia, tengo la intención de mantener este addon separado).

También tenemos (no integrada) código de un prefijo índice de árbol para acelerar la distancia de Levenshtein. Pero esto necesita un poco más de trabajo para su integración, y tal vez algunos perfiles.

La mayoría de las veces, únicamente los índices de trabajo para una determinada distancia. No hay ningún índice general que puede apoyar arbitraria distancias en el mismo tiempo. Existen algunos índices (por ejemplo, M-tree, y iDistance, ambos disponibles en ELKI) que trabajan con diferentes distancias, pero sólo una distancia en un tiempo. Pero lo bien que trabajan para sus datos y la distancia varía mucho. Generalmente, usted necesita un buen numérico contraste en sus similitudes.

La cuestión que hay que preguntarse es: ¿hay una manera de encontrar todos los objetos dentro de un radio de $\varepsilon$ (o una similitud mayor que $\varepsilon$) sin comparar cada objeto a cualquier otro objeto.

Tenga en cuenta que para DBSCAN puede utilizar falso distancias. Las distancias reales no son utilizados; sólo una decisión binaria ($d\leq\varepsilon$). Este es oficializado como GeneralizedDBSCAN. Así que si tu puede implementar una "función de distancia" que devuelve 0 para "similar" y 1 para "no similares", y conectarlo en scikit-learn DBSCAN, usted debería estar bien. Dependiendo de la arquitectura de scikit-learn, usted tal vez puede conectar un índice personalizado disfrazado de función de distancia. Invertida listas son un buen candidato para datos binarios.