Bisectriz k-means algoritmo de agrupamiento explicación

Question

Se me solicitó que escribiera un algoritmo bisector de k-medias, pero no entendí el algoritmo. Sé el algoritmo k-means.

Puede explicar el algoritmo, pero no en academic language

Gracias.

Answer 1

La idea es dividir iterativamente la nube de puntos en 2 partes. En otras palabras, construyes un árbol binario aleatorio donde cada división (un nodo con dos hijos) corresponde a dividir los puntos de tu nube en 2.

Empiezas con una nube de puntos.

• Calcule su centroide (baricentro) w

• Seleccionar un punto en el cL azar entre los puntos de la nube

• Construir el punto cR como el punto de cL simétrica cuando se compara con w (el segmento Cl-> w es el mismo que w-> cR)

• independiente los puntos de su nube en dos, los más cercanos a cR pertenecen a una debajo de las nubes R, y los más cercanos a cL pertenece a la subcloud L

• reiteramos que es subnubes R y L

Notas:

Usted puede descartar los puntos al azar una vez que se ha utilizado. Sin embargo, mantenga los centroides de todos los subcoulds.

Deténgase cuando sus subclouds contengan exactamente un punto.

Si desea k clusters, simplemente tome k centroides de modo que contengan todos los puntos de la nube inicial. Puedes hacer cosas mucho más elaboradas si quieres (minimizando la variación de las nubes, etc.). Supongamos que quieres 4 clusters (una potencia de dos para mayor comodidad). Entonces solo necesitas cortar las nubes en dos, y luego cortar cada una subcloud en dos. Si desea 8 clústeres, vuelva a cortar estos subcloud de una vez en dos. Y nuevamente para 16 grupos.

Si desea agrupar K con una potencia no igual a 2 (digamos 24), observe la potencia inferior más cercana de dos. Es 16. Todavía te faltan 8 grupos. Cada "cluster de nivel 16" es el centroide de un "nivel 16 subcloud". Lo que harás es tomar 8 "niveles-16-clusters" (al azar, por ejemplo) y reemplazarlos con los dos "hijos" "level-32-clusters". (Estos dos "niveles-32-clústeres" secundarios corresponden a dos "subclouds nivel-32" que se suman al nivel "subcloud-nivel 16")