1. Einführung
Der K-Mean-Clustering-Algorithmus wählt zunächst zufällig K-Objekte als anfängliches Cluster-Zentrum aus. Der Abstand zwischen jedem Objekt und der Mitte jedes Samenclusters wird dann berechnet, und jedes Objekt wird dem Cluster -Zentrum zugeordnet, das ihm am nächsten liegt. Das Cluster -Zentrum und die ihnen zugewiesenen Objekte stellen einen Cluster dar. Sobald alle Objekte zugewiesen sind, wird der Cluster -Zentrum jedes Clusters basierend auf den vorhandenen Objekten im Cluster neu berechnet. Dieser Vorgang wird wiederholt, bis eine bestimmte Beendigung erfüllt ist. Die Kündigungsbedingung kann sein, dass keine (oder minimalen Anzahl) Objekte auf verschiedene Cluster zugewiesen werden, wobei sich keine (oder minimalen Anzahl) der Clusterzentren erneut ändern, und die Summe der quadratischen Fehler ist lokal minimal.
2. Was ist Clustering
Clustering ist ein Prozess der Sortierung und Organisation von Datenmitgliedern, die in bestimmten Aspekten ähnlich sind. Clustering ist eine Technologie, um diese interne Struktur zu entdecken. Die Clustering -Technologie wird oft als unbeaufsichtigtes Lernen bezeichnet.
3. Was ist K-Mean-Clustering?
K-Mean-Clustering ist der berühmteste Partition-Clustering-Algorithmus und aufgrund seiner Einfachheit und Effizienz der am häufigsten verwendete aller Clustering-Algorithmen. Bei einem Datenpunktsatz und der erforderlichen Anzahl von Clustern k wird K vom Benutzer angegeben, und der K-Mean-Algorithmus unterteilt wiederholt Daten in K-Cluster gemäß einer bestimmten Entfernungsfunktion.
4. Implementierung
Der Java -Code lautet wie folgt:
package org.algorithm;import java.util.ArrayList;import java.util.Random;/** * K-mean clustering algorithm*/public class Kmeans {private int k;// How many clusters are divided into private int m;// Number of iterations private int dataSetLength;// Number of elements in dataset, that is, the length of the dataset private ArrayList <float []> Datensatz; // Datensatz verlinkte Liste private ArrayList <float []> Center; // Center Linked List Private ArrayList <ArrayList <float []> cluster; // cluster private ArrayList <float> jc; // Die Summe der quadratischen Fehler, so näher k -datasetlängen, desto kleiner. */public void setDataset (ArrayList <float []> Dataset) {this.dataset = dataset;}/*** Die Ergebnisgruppierung erhalten** @Return Ergebnis Set*/public ArrayList <arrayList <float [] >> getCluster () {return clust cluster;}/*** Konstruktor, die die Anzahl der clustern in der Anzahl der KLUSTERS übergeben. k <= 0, auf 1 gesetzt, wenn k größer als die Länge der Datenquelle ist, auf die Länge der Datenquelle*/public kmeans (int k) {if (k <= 0) {k = 1;} this.k = k;}/***Initialisierung*/private void init () {m = 0) = clyal (); if (); if (); if (); {initdataset ();} dataSetLength = dataSet.size (); if (k> datasetLength) {k = dataSetLength;} center = initCenters (); cluster = initcluster (); jc = new ArrayList <float> ();}/*** Wenn der Caller nicht initialisiert wurde. {dataSet = new ArrayList<float[]>();// where {6,3} is the same, so the error of dividing datasets of length 15 into 14 clusters and 15 clusters is 0 float[][] dataSetArray = new float[][] { { 8, 2 }, { 3, 4 }, { 2, 5 }, { 4, 2 }, { 7, 3 }, { 6, 2}, {4, 7}, {6, 3}, {5, 3}, {6, 3}, {6, 9}, {1, 6}, {3, 9}, {4, 1}, {8, 6}}; für (int i = 0; i <datasetArray; i++)). {DataSet.Add (DataSetArray [i]);}}/*** Initialisieren Sie die zentrale Datenverbindungsliste, und es gibt so viele Mittelpunkte wie die Cluster in** @return center point set*/private arrayList <float []> initcenter () {arraylist <] float [] kentrum = boolraylist <]; temp = random.Nextint (dataSetLength); randoms [0] = temp; für (int i = 1; i <k; i ++) {flag = true; while (flag) {temp = random.nextint (dataSetLength); int j = 0; // Ich bin nicht sicher, dass das für Loop nicht add add add 1 // für (//). if (temp == randoms [j]); // { // brechen; // } // } while (j < i) {if (temp == randoms[j]) {break;}j++;}if (j == i) {flag = false;}}randoms[i] = temp;}// Test the random number generation situation// for(int i=0;i<k;i++) // { // System.out.println ("test1: randoms ["+i+"] ="+randoms [i]); //} // system.out.println (); for (int i = 0; i < k; i++) {center.add(dataSet.get(randoms[i]));// Generate initialization center link}return center;}/** * Initialization cluster set* * @return A cluster of empty data divided into k clusters*/private ArrayList<ArrayList<float[]>> initCluster() {ArrayList<ArrayList<float[]>> cluster = new ArrayList<ArrayList<float[]>>();for (int i = 0; i < k; i++) {cluster.add(new ArrayList<float[]>());}return cluster;}/** * Calculate the distance between two points* * @param element * Point 1 * @param center * Point 2 * @return Distance*/private float distance(float[] element, float[] center) {float distance = 0,0f; float x = Element [0] - Mittel [0]; Float y = Element [1] - Mitte [1]; Float z = x * x + y * y; Abstand = (float) math.sqrt (z); {float minDistance = distance[0];int minLocation = 0;for (int i = 1; i < distance.length; i++) {if (distance[i] < minDistance) {minDistance = distance[i];minLocation = i;} else if (distance[i] == minDistance) // If equal, return a random position{if (random.nextint(10) < 5) {minLocation = i;}}} return minLocation;}/*** Kern, das aktuelle Element in den Cluster in Bezug auf das Mindestabstandszentrum*/private void cluterset () {float [] distanz = neu float [k]; für (int i = 0; i <dataSet; i ++) {für (int j = 0; j <k; j ++) {J] Distanz [J] Distanz [J], (j. Center.get (j)); // system.out.println ("test2:"+"dataset ["+i+"], center ["+j+"], distanz ="+distanz [j]);} int minlocation = mindistance (distanz); // system.out.println ("test3:"+"dataset ["+i+i+i+i+i+i+i+i+i+i+i+ // system.out.println (); cluster.get (minlocation) .Add (dataset.get (i)); // Core, geben Sie das aktuelle Element in den Cluster in Bezug auf die minimale Distanzmitte}}/** * Methode, um das Quadrat des Fehlers von zwei Punkten zu finden Mitte [0]; Float y = Element [1] - Mitte [1]; float errsquare = x * x + y * y; return errsquare;}/** * Die Fehlersumme der Quadrat -Kriterienfunktionsmethode */privat void Country () {float jcf = 0; für (int i = 0; i <cluster.size (); i ++) {für (int j = 0; j <cluster.get (i) .size (); j ++) {jcf+= fehlerquare (cluster.get (i) .get (j), center.get (i);}}}}} jc.add (jcf); setNewCenter () {für (int i = 0; i <k; i ++) {int n = cluster.get (i) .size (); if (n! cluster.get(i).get(j)[1];}// Set an average newCenter[0] = newCenter[0] / n;newCenter[1] = newCenter[1] / n;center.set(i, newCenter);}}}/** * Print data, test* * @param dataArray * Dataset* @param dataArrayName * Dataset name*/public void printDataArray(ArrayList<float[]> dataArray, String dataArrayName) {for (int i = 0; i < dataArray.size(); i++) {System.out.println("print:" + dataArrayName + "[" + i + "]={" + dataArray.get(i)[0] + "," + dataArray.get(i)[1] + "}");} System.out.println ("======================================== ========================================================== ");}/** * Kmeans Algorithmus Kernprozessmethode */private void kmeans () {init (); // printDatArray (Dataset, "initdataset"); // printDatArray (Mitte, "initCenter"); // Schleifengruppierung, bis der Fehler unverändert bleibt, während (true) {clusterset (); // für (int i = 0; i <cluster.size (); i ++) // {// printDatArray (cluster.get (i)), cluster ["+i+"] "); //} Countrule (); // system.out.println ("count:"+"jc ["+m+"] ="+jc.get (m)); // system.out.println (); // Fehler bleibt unverändert, die Gruppierung ist abgeschlossen, wenn (m! = 0) {if (jc.get (m) - jc.get (m - 1) == 0) {break;}} setNewCenter (); // printDatArray (Mitte, "NewCenter"); M ++; cluster.clear (); cluster = initcluster ();} // system.out.println ("Hinweis: Die Zeiten der Wiederholung: m ="+m); // Ausgabe -Iterationen}/*** Ausführungsalgorithmus*/public void execute () {Long Starttime = System.currentTimillis (); System.currentTimemillis (); System.out.println ("Kmeans Laufzeit =" + (Endime - StartTime) + "MS"); System.out.println ("Kmeans endet"); System.out.println ();}}5. Beschreibung:
Der spezifische Code wird online gefunden und Kommentare werden nach Ihrem eigenen Verständnis hinzugefügt und teilweise geändert. Wenn der Kommentar falsch ist, hoffe ich, ihn zu korrigieren.
6. Test
Paket org. float[]{1,2});dataSet.add(new float[]{3,3});dataSet.add(new float[]{3,4});dataSet.add(new float[]{5,6});dataSet.add(new float[]{8,9});dataSet.add(new float[]{4,5});dataSet.add(new float[]{6,4});dataSet.add(new float[]{3,9});dataSet.add(new float[]{5,9});dataSet.add(new float[]{4,2});dataSet.add(new float[]{1,9});dataSet.add(new float[]{1,9});dataSet.add(new float[]{1,9});dataSet.add(new float[]{5,9});dataSet.add(new float[]{4,2});dataSet.add(new float[]{1,9});dataSet.add(new float[]{1,9});dataSet.add(new float[]{1,9});dataSet.add(new float[]{5,9});dataSet.add(new float[]{5,9});dataSet.add(new float [] {4,2}); dataset.add (neuer float [] {1,9}); dataset.add (neuer float [] {7,8}); // Setzen Sie den ursprünglichen Datensatz k.setDataset (dataset); // Executieren des Algorithmus K. execute (); cluster = k.getCluster (); // Zeigen Sie das Ergebnis für (int i = 0; i <cluster.size (); i ++) {k.printDatArray (cluster.get (i), "cluster ["+i+"]");}}}Zusammenfassung: Der Testcode wurde übergeben. Die Clustering -Ergebnisse wurden betrachtet und die Ergebnisse erfüllten die Anforderungen im Grunde genommen. Ob es genauere Algorithmen gibt, bleibt noch zu entdecken. Spezifische Praktiken müssen untersucht werden
Zusammenfassen
Das obige ist der gesamte Inhalt dieses Artikels zum Beispiel für den Java-Versions-Implementierungscode für den K-Mean-Clustering-Algorithmus. Ich hoffe, es wird für alle hilfreich sein. Interessierte Freunde können weiterhin auf andere verwandte Themen auf dieser Website verweisen. Wenn es Mängel gibt, hinterlassen Sie bitte eine Nachricht, um darauf hinzuweisen. Vielen Dank an Freunde für Ihre Unterstützung für diese Seite!