Ik heb een grote verzameling vectoren in 3 dimensies. Ik moet deze clusteren op basis van Euclidische afstand, zodat alle vectoren in een bepaalde cluster een Euclidische afstand tussen elkaar hebben die kleiner is dan een drempel “T”.
Ik weet niet hoeveel clusters er zijn. Aan het einde kunnen er individuele vectoren zijn die geen deel uitmaken van een cluster omdat de euclidische afstand niet kleiner is dan “T” met een van de vectoren in de ruimte.
Welke bestaande algoritmen/aanpak moet hier worden gebruikt?
Antwoord 1, autoriteit 100%
Je kunt hiërarchische clusteringgebruiken. Het is een vrij eenvoudige benadering, dus er zijn veel implementaties beschikbaar. Het is bijvoorbeeld opgenomen in Python’s scipy.
Zie bijvoorbeeld het volgende script:
import matplotlib.pyplot as plt
import numpy
import scipy.cluster.hierarchy as hcluster
# generate 3 clusters of each around 100 points and one orphan point
N=100
data = numpy.random.randn(3*N,2)
data[:N] += 5
data[-N:] += 10
data[-1:] -= 20
# clustering
thresh = 1.5
clusters = hcluster.fclusterdata(data, thresh, criterion="distance")
# plotting
plt.scatter(*numpy.transpose(data), c=clusters)
plt.axis("equal")
title = "threshold: %f, number of clusters: %d" % (thresh, len(set(clusters)))
plt.title(title)
plt.show()
Wat een resultaat oplevert dat lijkt op de volgende afbeelding.
De drempelwaarde die als parameter wordt gegeven, is een afstandswaarde op basis waarvan wordt besloten of punten/clusters worden samengevoegd tot een ander cluster. De gebruikte afstandsmetriek kan ook worden gespecificeerd.
Merk op dat er verschillende methoden zijn om de intra-/interclusterovereenkomst te berekenen, b.v. afstand tussen de dichtstbijzijnde punten, afstand tussen de verste punten, afstand tot de clustercentra enzovoort. Sommige van deze methoden worden ook ondersteund door de hiërarchische clusteringmodule van scipys (enkele/volledige/gemiddelde… koppeling). Volgens je bericht denk ik dat je complete koppelingwilt gebruiken.
Merk op dat deze benadering ook kleine (eenpunts) clusters toestaat als ze niet voldoen aan het gelijkheidscriterium van de andere clusters, d.w.z. de afstandsdrempel.
Er zijn andere algoritmen die beter zullen presteren, die relevant zullen worden in situaties met veel datapunten. Zoals andere antwoorden/opmerkingen suggereren, wil je misschien ook eens kijken naar het DBSCAN-algoritme:
- https://en.wikipedia.org/wiki/DBSCAN
- http://scikit-learn.org/stable/auto_examples/cluster/ plot_dbscan.html
- http://scikit- learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html#sklearn.cluster.DBSCAN
Voor een mooi overzicht van deze en andere clusteringalgoritmen, bekijk ook deze demopagina (van Python’s scikit-learn bibliotheek):
Afbeelding gekopieerd van die plaats:
Zoals je kunt zien, doet elk algoritme een aantal aannames over het aantal en de vorm van de clusters waarmee rekening moet worden gehouden. Of het nu gaat om impliciete aannames die worden opgelegd door het algoritme of om expliciete aannames die worden gespecificeerd door parametrering.
Antwoord 2, autoriteit 27%
Het antwoord van moooeeeep raadde het gebruik van hiërarchische clustering aan. Ik wilde uitleggen hoe je de drempel van de clustering kiest.
Eén manier is om clusteringen te berekenen op basis van verschillende drempels t1, t2, t3,… en vervolgens een metriek te berekenen voor de “kwaliteit” van de clustering. Het uitgangspunt is dat de kwaliteit van een clustering met het optimaleaantal clusters de maximale waarde van de kwaliteitsmetriek zal hebben.
Een voorbeeld van een metriek van goede kwaliteit die ik in het verleden heb gebruikt, is Calinski-Harabasz. In het kort: je berekent de gemiddelde afstanden tussen clusters en deelt deze door de afstanden binnen de clusters. De optimale clustertoewijzing zal clusters hebben die het meest van elkaar gescheiden zijn, en clusters die het “strakst” zijn.
Trouwens, u hoeft geen hiërarchische clustering te gebruiken. Je kunt ook iets als k-means gebruiken, het voor elke kvooraf berekenen en dan de kkiezen met de hoogste Calinski-Harabasz-score .
Laat het me weten als je meer referenties nodig hebt, en ik zal mijn harde schijf doorzoeken op wat papieren.
Antwoord 3, autoriteit 14%
Bekijk het DBSCAN-algoritme. Het clustert op basis van de lokale dichtheid van vectoren, d.w.z. ze mogen niet meer dan enkele εvan elkaar verwijderd zijn, en kan het aantal clusters automatisch bepalen. Het beschouwt ook uitbijters, d.w.z. punten met een onvoldoende aantal ε-buren, om geen deel uit te maken van een cluster. De Wikipedia-pagina linkt naar een paar implementaties.
Antwoord 4
Gebruik OPTICS, wat goed werkt met grote datasets.
OPTICS: bestelpunten om de clusterstructuur te identificeren Nauw verwant aan DBSCAN, vindt kernmonster met hoge dichtheid en breidt clusters hiervan uit 1. In tegenstelling tot DBSCAN, behoudt clusterhiërarchie voor een variabele buurtradius. Beter geschikt voor gebruik op grote datasets dan de huidige sklearn-implementatie van DBSCAN
from sklearn.cluster import OPTICS
db = OPTICS(eps=3, min_samples=30).fit(X)
Verfijn eps, min_samplesvolgens uw vereisten.
Antwoord 5
Misschien heb je geen oplossing: dit is het geval wanneer de afstand tussen twee afzonderlijke invoergegevenspunten altijd groter is dan T. Als je het aantal clusters alleen uit de invoergegevens wilt berekenen, kun je kijken naar MCG, een hiërarchische clusteringmethode met een automatisch stopcriterium: zie de gratis seminarpaper op https:// hal.archives-ouvertes.fr/hal-02124947/document(bevat bibliografische referenties).
Antwoord 6
Ik wil toevoegen aan het antwoord van moooeeeep door hiërarchische clustering te gebruiken.
Deze oplossing werkt voor mij, hoewel het vrij “willekeurig” is om de drempelwaarde te kiezen.
Door te verwijzen naar andere bronnen en zelf te testen, kreeg ik een betere methode en de drempel kon gemakkelijk worden gekozen door dendrogram:
from scipy.cluster import hierarchy
from scipy.spatial.distance import pdist
import matplotlib.pyplot as plt
ori_array = ["Your_list_here"]
ward_array = hierarchy.ward(pdist(ori_array))
dendrogram = hierarchy.dendrogram(hierarchy.linkage(ori_array, method = "ward"))
plt.title('Dendrogram')
plt.xlabel('Customers')
plt.ylabel('Euclidean distances')
plt.show()
Je zult de plot zo zien
klik hier.
Door vervolgens de horizontale lijn te tekenen, laten we zeggen op afstand = 1, zal het aantal voegwoorden het gewenste aantal clusters zijn. Dus hier kies ik drempel = 1 voor 4 clusters.
threshold = 1
clusters_list = hierarchy.fcluster(ward_array, threshold, criterion="distance")
print("Clustering list: {}".format(clusters_list))
Nu zal elke waarde in cluster_list een toegewezen cluster-id zijn van het corresponderende punt in ori_array.