Wat ass K-Means Clustering?

K-bedeit Clustering ass eng net iwwerwaacht Léieren Algorithmus, an aus allen onkontrolléierten Léieralgorithmen, K-heescht Clustering kéint am meeschte verbreet sinn, dank senger Kraaft an Einfachheet. Wéi funktionéiert K-bedeit Clustering genau?

Déi kuerz Äntwert ass datt K-heescht Clustering funktionnéiert duerch e Referenzpunkt erstellen (en Zentroid) fir eng gewënschte Zuel vu Klassen, an dann Datenpunkte fir Klassecluster zouzeweisen baséiert op wéi engem Referenzpunkt am noosten ass. Och wann dat eng séier Definitioun fir K-bedeit Clustering ass, loosst eis e bëssen Zäit huelen fir méi déif a K-bedeit Clustering ze dauchen an eng besser Intuition ze kréien fir wéi et funktionnéiert.

Clustering definéieren

Ier mir déi exakt Algorithmen ënnersichen, déi benotzt gi fir K-bedeit Clustering auszeféieren, loosst eis e bëssen Zäit huelen fir Clustering am Allgemengen ze definéieren.

Cluster si just Gruppe vun Artikelen, a Cluster ass just Elementer an dës Gruppen ze setzen. Am Data Science Sënn, Clustering Algorithmen Zil zwee Saachen ze maachen:

• Vergewëssert Iech datt all Datenpunkten an engem Cluster sou ähnlech wéi méiglech matenee sinn.
• Vergewëssert Iech datt all Datenpunkten a verschiddene Stärekéip sou ongläich wéi méiglech sinn.

Clustering Algorithmen gruppéiere Saachen zesummen op Basis vun enger Metrik vun Ähnlechkeet. Dëst gëtt dacks gemaach andeems Dir de "Zentroid" vun de verschiddene méigleche Gruppen an der Dataset fonnt hutt, awer net exklusiv. Et gi vill verschidde Clustering Algorithmen awer d'Zil vun all Clustering Algorithmen ass d'selwecht, d'Gruppen intrinsesch zu engem Dataset ze bestëmmen.

K-Mëtt Clustering

K-Means Clustering ass eng vun den eelsten an am meeschte benotzten Typen vu Clustering Algorithmen, an et funktionnéiert op Basis vu Vektorquantiséierung. Et gëtt e Punkt am Raum, deen als Hierkonft gewielt gëtt, an da ginn Vecteure vum Urspronk op all Datenpunkten an der Datesaz gezunn.

Am Allgemengen kann K-bedeit Clustering a fënnef verschidde Schrëtt opgedeelt ginn:

• Setzt all Instanzen an Ënnersätz, wou d'Zuel vun den Ënnersetze gläich ass K.
• Fannt de mëttlere Punkt / Zentroid vun den nei erstallte Clusterpartitionen.
• Baséiert op dës centroids, zougewisen all Punkt zu engem spezifesche Stärekoup.
• Berechent d'Distanz vun all Punkt op d'Zentroiden, a gitt Punkten un d'Cluster, wou d'Distanz vum Centroid de Minimum ass.
• Nodeems d'Punkten un d'Cluster zougewisen sinn, fannt Dir déi nei Zentroid vun de Stärekoup.

Déi uewe genannte Schrëtt ginn widderholl bis den Trainingsprozess fäerdeg ass.

An der éischter Phase sinn Zentroiden iergendwou ënnert den Datepunkte plazéiert.
Foto: Weston.pace iwwer Wikimedia Commons, GNU Free Documentation License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Alternativ, nodeems d'Zentroiden plazéiert sinn, kënne mir K-Bedeitungsclusterung virstellen wéi d'Austausch zréck an zréck tëscht zwou verschiddene Phasen: Datepunkte markéieren an Zentroiden aktualiséieren.

Am zweete Schrëtt gëtt eng Distanzmetrik wéi euklidesch Distanz benotzt fir ze berechnen op wéi engem Zentroid e bestëmmte Punkt am nootste läit, an da ginn d'Punkte un d'Klass vun deem Zentroid zougewisen. Foto: Weston.pace iwwer Wikimedia Commons, GNU Free Doc License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

An der Datepunkt Etikettéierungsphase gëtt all Datepunkt e Label zougewisen, deen et an de Stärekoup placéiert, deen zum nooste Centroid gehéiert. Déi nootste Zentroid gëtt typesch mat quadrateschen Euklideschen Distanz bestëmmt, obwuel aner Distanzmetriken wéi Manhattan Distanz, Cosinus a Jaccard Distanz kënne benotzt ginn ofhängeg vun der Aart vun Daten déi an de Clustering Algorithmus gefüttert ginn.

Am drëtte Schrëtt sinn d'Zentroid op d'Moyenne vun allen Datenpunkte geréckelt. D'Klassen ginn dann nei zougewisen. Foto: Weston.pace iwwer Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

Am Centroid Update Schrëtt ginn d'Zentroid berechent andeems Dir déi mëttler Distanz tëscht all den Datepunkte fënnt, déi momentan an engem Cluster enthale sinn.

Wéi wielen ech de richtege Wäert fir "K"

Bedenkt datt K-bedeit Clustering en net iwwerwaachte Algorithmus ass an d'Zuel vun de Klassen am Viraus net bekannt ass, wéi entscheet Dir iwwer déi entspriechend Zuel vu Klassen / de richtege Wäert fir K?

Eng Technik fir de richtege K-Wäert ze wielen gëtt den "der Ielebou Technik". D'Ellbog Technik besteet aus engem K-bedeit Clustering Algorithmus fir eng Rei vu verschiddene K-Wäerter ze lafen an eng Genauegkeetsmetrik ze benotzen, typesch d'Zomm vum Quadratfehler, fir ze bestëmmen wéi eng Wäerter vu K déi bescht Resultater ginn. D'Zomm vum Quadratfehler gëtt festgeluegt andeems d'Duerchschnëttsdistanz tëscht dem Zentroid vun engem Stärekoup an den Datepunkten an deem Stärekoup berechent gëtt.

De Begrëff "Ellbogentechnik" kënnt aus der Tatsaach, datt wann Dir den SSE mat Bezuch op déi verschidde Wäerter vu K plott, de resultéierende Linneplot dacks eng "Ellbog" Form huet, wou SSE séier erofgeet fir déi éischt puer Wäerter vu K, mee dann Niveau aus. An esou Konditiounen ass de Wäert vu K um Ellbog de beschte Wäert fir K, well et séier ofhuelend Rendement no dësem Wäert gëtt.

Mini-Batch K-Means Clustering

Wéi Datesätz méi grouss ginn, wiisst d'Berechnungszäit och. Basis K-bedeit Clustering kann eng laang Zäit daueren fir ze kompletéieren wann se op massiven Datesätz lafen, an als Resultat sinn Tweaks op K-bedeit Clustering gemaach ginn fir d'raimlech an temporär Käschten vum Algorithmus ze reduzéieren.

Mini-Batch K-bedeit Clustering ass eng Variant op K-bedeit Clustering wou d'Gréisst vum Dataset, deen ugesi gëtt, ofgeschloss ass. Normal K-bedeit Clustering funktionnéiert op der ganzer Dataset / Batch gläichzäiteg, wärend Mini-Batch K-bedeit Clustering brécht den Dataset an Ënnersets erof. Mini-Batches ginn zoufälleg aus dem ganzen Dataset geprobéiert a fir all nei Iteratioun gëtt eng nei zoufälleg Probe ausgewielt a benotzt fir d'Positioun vun den Zentroiden ze aktualiséieren.

Am Mini-Batch K-Means Clustering ginn Cluster aktualiséiert mat enger Kombinatioun vun de Mini-Batch Wäerter an engem Léierrate. De Léierrate fällt iwwer d'Iteratiounen erof, an et ass den Inverse vun der Unzuel vun Datenpunkten an engem spezifesche Cluster. Den Effekt vun der Reduzéierung vum Léierquote ass datt den Impakt vun neien Donnéeën reduzéiert gëtt an d'Konvergenz erreecht gëtt wann et no e puer Iteratiounen keng Ännerungen an de Cluster sinn.

D'Resultater vun Studien iwwer d'Effizienz vu Mini-Batch K-bedeit Clustering suggeréieren datt et d'Berechnungszäit mat engem liichte Trade-off an der Clusterqualitéit erfollegräich reduzéiere kann.

Uwendungen vun K-Means Clustering

K-bedeit Clustering ka sécher an all Situatioun benotzt ginn, wou Datenpunkte kënnen a verschidde Gruppen / Klassen segmentéiert ginn. Hei sinn e puer Beispiller vu gemeinsame Benotzungsfäll fir K-mean Clustering.

K-means Clustering kéint fir Dokumentklassifikatioun applizéiert ginn, Gruppéierungsdokumenter baséiert op Features wéi Themen, Tags, Wuertverbrauch, Metadaten an aner Dokumentfeatures. Et kéint och benotzt ginn fir Benotzer als Bots ze klassifizéieren oder net Bots op Basis vun Aktivitéitsmuster wéi Posts a Kommentarer. K-bedeit Clustering kann och benotzt ginn fir Leit a Gruppen ze setzen op Basis vu Suergenniveauen wann se hir Gesondheet iwwerwaachen, baséiert op Features wéi Komorbiditéiten, Alter, Patientgeschicht, etc.

K-means Clustering kann och fir méi oppe Aufgaben benotzt ginn wéi Empfehlungssystemer erstellen. D'Benotzer vun engem System wéi Netflix kënnen zesumme gruppéiert ginn op Basis vu Gesiichtsmuster a recommandéiert ähnlechen Inhalt. K-bedeit Clustering kéint fir Anomalie Detektiounsaufgaben benotzt ginn, potenziell Fäll vu Bedruch oder defekt Artikelen ervirhiewen.