Datenclustering
Daten Clusterbildung mit Naive Bayes-Inferenz
Daten-Cluster ist ein maschinelles Lernen-Technik, die viele wichtige praktische Anwendungen, z. B. Gruppieren Verkaufsdaten zu Verbraucher-Kauf Verhalten zeigen oder Gruppieren von Netzwerkdaten, Einblicke in Kommunikationsmuster zu geben hat. Daten-Cluster eignet sich auch zur Identifizierung von anomalen Datenpunkte. In diesem Artikel stelle ich ein komplettes c#-Programm können, das Sie als Grundlage für ein Softwaresystem Clusterfeatures hinzufügen oder erstellen eine leistungsstarke Standalone-Cluster-Dienstprogramm verwenden.
Es gibt viele verschiedene clustering-Algorithmen, teilweise, weil die Wirksamkeit der clustering-Algorithmus zu einem gewissen Grad die Merkmale der Daten wird clustered abhängt. Der am häufigsten verwendete Algorithmus nennt man k-Means-Algorithmus. Leider ist dieser Algorithmus nur für numerische Daten. Im Gegensatz dazu basiert die clustering-Algorithmus, die ich in diesem Artikel präsentieren werde auf eine Technik namens Naive Bayes Inference, die mit entweder kategorische oder numerische Daten arbeitet. Obwohl all die Ideen, die in der hier vorgestellten clustering-Algorithmus verwendet bekannt sind, wurden die gesamten Algorithmus und spezifischen Implementierung nicht zum besten meines Wissens vor veröffentlicht. Ich nenne diesen Algorithmus und seine Umsetzung Iterative Naive Bayes Inference Agglomeratives Clustering (INBIAC) zur Unterscheidung von anderen clustering-Techniken. Naive Bayes Folgerung ist ein sehr gebräuchliches Verfahren für die Klassifizierung von Daten durchführen, aber es ist nicht allgemein bekannt, dass Naive Bayes auch für Daten Cluster verwendet werden können.
Der beste Weg zu verstehen, wohin ich bin in diesem Artikel ist es, einen Blick auf Abbildung 1. Das Demoprogramm beginnt mit der Generierung von acht Zufallsdaten-Tupel, die beschreiben, die Location (Stadt-, Vorort- oder ländlichen), Einkommen (niedrig, Mittel, hoch oder sehr hoch) und Politik (Liberale oder konservative) acht hypothetische Menschen. Das Programm dann die unformatierte Zeichenfolgendaten in den Arbeitsspeicher geladen, und konvertiert die Daten in Int-Werten um effiziente Bearbeitung zu ermöglichen. Beispielsweise werden das letzte Tupel von ("Rural", "Low", "konservative") als (2, 0, 1) gespeichert.
.png)
Abbildung 1 Daten-Clustering mit Naive Bayes-Inferenz
Viele clustering-Algorithmen, einschließlich INBIAC, erfordern die Anzahl der Cluster angegeben werden. Hier wird die Variable NumClusters auf 3 festgelegt. Das Demoprogramm Cluster die Daten und zeigt dann das endgültige clustering [2, 0, 2, 1, 1, 2, 1, 0]. Hinter den Kulissen Samen der Algorithmus Cluster 0, 1 und 2 mit Tupeln 1, 6 und 0, beziehungsweise. Dann ist jeweils verbleibenden fünf Tupel zugeordnet, ein zu einer Zeit, zu einem Cluster. Dieser Algorithmus wird Agglomeratives bezeichnet.
Da kein Training Daten oder Benutzer-Eingriff erforderlich ist, ist Clusterbildung gelegentlich als "Unüberwachtes lernen." bezeichnet Jeder Index im Cluster Array stellt ein Tupel und der Wert im Array ist eine Cluster-ID. Also Tupel 2 ("S", "Erzeugnissen", "konservative"), 0, Tupel 1 cluster zugeordnet ist ("Rural", "Medium," "des Konservativen") zugewiesen ist Cluster 2 und so weiter.
Das Demoprogramm beendet sich durch die Anzeige der originalen-raw-Daten in gruppierter Form. Wie Sie sehen können, scheint es vernünftig, das endgültige clustering. Und wenn Sie die ursprünglichen Daten betrachten, ich denke, dass Sie zustimmen, dass versuchen, Daten manuell, sogar für sehr kleine Datenmengen, cluster extrem schwierig sein würde.
Dieser Artikel setzt voraus, Sie haben fortgeschrittene Programmierkenntnisse mit einer C-Familie-Sprache, aber werden nicht vorausgesetzt, dass Sie Erfahrung mit Naive Bayes Inferenz oder clustering-Algorithmen. Das Demoprogramm unter Abbildung 1 ist eine einzelne c#-Konsolenanwendung. Ich codiert es ohne Verwendung von OOP-Techniken, so dass Sie leichter zu Sprachen, die nicht vollständig OOP unterstützen umgestalten können.
Ich entfernte alle Fehlerüberprüfung die Ideen so klar wie möglich zu halten. Der Code für den Demo-Programm ist zu lang, in seiner Gesamtheit in diesem Artikel zu präsentieren, so dass ich werde Erläuterung der wichtigsten Teile des Algorithmus im Vordergrund. Der vollständige Quellcode für das Demoprogramm ist abrufbar unter archive.msdn.microsoft.com/mag201303INBIAC.
Programmstruktur
Die gesamte Programmstruktur, mit einigen Kommentaren und WriteLine-Anweisungen entfernt, notiert Abbildung 2.
Abbildung 2-Clusterunterstützung Programmstruktur
using System;
using System.Collections.Generic;
namespace ClusteringBayesian
{
class ClusteringBayesianProgram
{
static Random random = null;
static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin data clustering using Naive Bayes demo\n");
random = new Random(6); // Seed of 6 gives a nice demo
int numTuples = 8;
Console.WriteLine("Generating " + numTuples +
"tuples of location-income-politics data");
string[] rawData = MakeData(numTuples);
Console.WriteLine("\nRaw data in string form is:\n");
ShowData(rawData, numTuples);
string[] attNames = new string[] { "Location", "Income", "Politics" };
string[][] attValues = new string[attNames.Length][];
attValues[0] = new string[] { "Urban", "Suburban", "Rural" };
// Location
attValues[1] = new string[] { "Low", "Medium", "High", "VeryHigh" };
// Income
attValues[2] = new string[] { "Liberal", "Conservative" };
// Politics
Console.WriteLine("Loading raw data into memory\n");
string[][] tuples = LoadData(rawData, attValues);
Console.WriteLine("Converting raw data to int form and" +
"storing in memory\n");
int[][] tuplesAsInt = TuplesToInts(tuples, attValues);
Console.WriteLine("Data in int form is:\n");
ShowData(tuplesAsInt, numTuples);
int numClusters = 3;
int numTrials = 10; // Times to get good seed indexes (different tuples)
Console.WriteLine("\nSetting numClusters to " + numClusters);
Console.WriteLine("\nInitializing Naive Bayes joint counts with " +
"Laplacian smoothing");
int[][][] jointCounts = InitJointCounts(tuplesAsInt, attValues,
numClusters);
int[] clusterCounts = new int[numClusters];
Console.WriteLine("\nBegin clustering data using Naive Bayes " +
"(with equal priors) ");
int[] clustering = Cluster(tuplesAsInt, numClusters, numTrials,
jointCounts, clusterCounts, true);
Console.WriteLine("Clustering complete");
Console.WriteLine("\nClustering in internal form is:\n");
for (int i = 0; i < clustering.Length; ++i)
Console.Write(clustering[i] + " ");
Console.WriteLine("Raw data displayed in clusters is:\n");
DisplayClustered(tuplesAsInt, numClusters, clustering, attValues);
Console.WriteLine("\nEnd demo\n");
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
} // Main
// Other methods go here
} // class
} // ns
Ich habe Visual Studio 2010 erstellen Sie eine c#-Konsolenanwendung mit dem Namen ClusteringBayesian. Im Fenster Projektmappen-Explorer in Datei Program.cs umbenannt, um den aussagekräftigeren ClusteringBayesianProgram.cs, die automatisch die einzelne Klasse umbenannt. Ich entfernt nicht benötigte Vorlage generierte Verweise auf die .NET Namespaces; Beachten Sie, das Programm hat einige Abhängigkeiten und braucht nur den Systems.Collections.Generic-Namespace.
Ich erkläre ein Gültigkeitsbereich der Klasse Random-Objekt mit dem Namen zufällig. Dieses Objekt wird verwendet, um halbzufälliger raw-Daten zu generieren und zu bestimmen, welche Tupel zu jedem Cluster ausführen. In der Main-Methode instanziiert zufällige mit einen Ausgangswert von 6, nur, weil dies eine hübsche Demo generiert.
Die nächsten paar Zeilen von der Demo-Programm verwenden Sie Hilfsmethoden MakeData und ShowData zu generieren und acht Zeilen Dummy-Daten angezeigt. MakeData Ruft Sub-helper Methoden MakeParty, MakeLocation, MakeIncome und MakePolitics. Wenn Sie mit bestimmten Hardcoded Daten Tupeln experimentieren möchten, können Sie diesen Code mit, zum Beispiel ersetzen:
int numTuples = 4;
string[] rawData = new string[] { "Urban,VeryHigh,Liberal",
"Rural,Medium,Conservative", "Urban,Low,Liberal",
"Suburban,Medium,Liberal" };
Anschließend benennt die Demo Programm Hardcodes das Attribut Lage, Einkommen und Politik. In einigen Szenarien, zum Beispiel wenn Ihre raw-Daten in eine Textdatei mit einem Header oder in einer SQL-Tabelle mit Spaltennamen, Sie sollten Ihre Daten zu scannen und programmgesteuert bestimmen die Attributnamen.
Die Demo Programm auch Hardcodes die Attributwerte Urban, Suburban und Rural für Lage; Low, Medium, High und Erzeugnissen für Einkommen; und liberale und konservative Politik. In einigen Szenarios sollten Sie wieder Ihre raw-Daten um programmgesteuert zu bestimmen, die Attributwerte zu scannen.
Das Demoprogramm Ruft Hilfsmethode LoadData die unformatierte Zeichenfolge-Daten in ein Array von Arrays im Speicher geladen. Für sehr große Datenmengen könnte dies nicht möglich sein. In solchen Situationen müssen Sie entweder Datenblöcke zu einem Zeitpunkt zu laden oder extern gespeicherten Rohdaten einer Linie oder Zeile zu einem Zeitpunkt durchlaufen.
Es ist, zwar möglich, mit unformatierte Zeichenfolgendaten direkt zu arbeiten ist es wesentlich effizienter arbeiten mit den Daten codiert als Typ int. Also, als nächstes Hilfsmethode TuplesToInts akzeptiert das Array von Arrays von Zeichenfolgen, scannt durch dieses Array konvertiert jede Zeichenfolge in einem nullbasierten Index und speichert alle Daten in ein Array von Arrays vom Typ int. Auch für sehr große Datenmengen müssen Sie Rohdaten eine Zeile zu einem Zeitpunkt gelesen und Attributwerte in Ints schnell umwandeln.
Das Demoprogramm bereitet die Cluster-Routine mit zwei Parameterwerte festlegen. Der Parameter NumClusters ist die Anzahl der Cluster zu generieren. Im allgemeinen Daten-Cluster ist ein Sondierungsprozess und Sie müssen experimentieren mit unterschiedlichen Werten von NumClusters (obwohl es einige faszinierenden Techniken gibt für eine optimale Anzahl von Clustern programmgesteuert zu bestimmen). Parameter NumTrials wird von der Cluster-Routine verwendet, beim Generieren der anfänglichen Clusterbildung, wie ich kurz erläutern werde.
Die Clustermethode erfordert zwei Arrays, die Grafen von zugewiesenen Tupel zu einem bestimmten Zeitpunkt in der INBIAC-Algorithmus zu halten. Array JointCounts hält die Anzahl der gruppierten Tupel, die ein bestimmtes Attribut-Wert und einen bestimmten Cluster haben. Das JointCounts-Array ist ein bisschen schwierig, und ich werde es in Kürze ausführlicher erklären. Aber jeden Wert in JointCounts als Teil der einen wichtigen Schritt in der Bayes-Technik namens Laplacian Glättung mit 1 initialisiert wird. Das zweite Array, ClusterCounts, hält die Anzahl der Tupel zugewiesen jedem Cluster zu einem bestimmten Zeitpunkt. Der Index des ClusterCounts stellt einen Cluster und der Wert ist die Anzahl der zugeordneten.
Das clustering erfolgt durch Methode Cluster. Cluster-Methode gibt ein Array, die kodiert, welche Cluster auf jedes Tupel zugewiesen ist. Das Demoprogramm endet indem das Cluster Array anzeigen, und zeige die Rohdaten, gruppiert nach Cluster mit Hilfsmethode DisplayClustered.
Naive Bayes-Inferenz
Der Schlüssel zum Verständnis des INBIAC-Algorithmus, so dass Sie den Demo-Code für Ihre eigenen Bedürfnisse ändern können ist das Naive Bayes Inferenz Verständnis. Naive Bayes wird am besten durch Beispiel erklärt. Angenommen, Sie haben die acht Tupel dargestellt Abbildung 1 und jedes Tupel in einer der drei Cluster platziert werden sollen:
[0] Suburban VeryHigh Liberal
[1] Rural Medium Conservative
[2] Suburban VeryHigh Conservative
[3] Suburban Low Liberal
[4] Suburban High Liberal
[5] Suburban Low Conservative
[6] Urban Low Liberal
[7] Rural Low Conservative
Zunächst davon ausgehen, dass jede Gruppe erhält einen einzelnen Samen-Tupel (in einer Weise, die später erläutert wird) so dass Tupel 1 0 cluster zugewiesen ist, Tupel 6 1 cluster zugewiesen ist und Tupel 0 Cluster 2 zugeordnet ist. Es gibt mehrere Möglichkeiten zur Darstellung dieser Clusterbildung, aber der INBIAC-Algorithmus würde die Informationen als Array speichern:
[ 2, 0, -1, -1, -1, -1, 1, -1 ]
In diesem Array die Arrayindizes sind Tupel, die Arraywerte sind Cluster und ein Wert von-1 gibt an, dass das zugehörige Tupel noch nicht zu einem Cluster zugewiesen wurde. So ist im Prinzip das clustering an dieser Stelle:
c0 : Rural Medium Conservative (tuple 1)
c1 : Urban Low Liberal (tuple 6)
c2 : Suburban VeryHigh Liberal (tuple 0)
Jetzt soll das erste nicht zugewiesene Tupel weisen, Cluster Tupel 2 (Suburban, Erzeugnissen, konservativ), zu einer der drei. Naive Bayes berechnet die Wahrscheinlichkeit, dass Tupel 2 gehört zu Clustern 0, 1 und 2 und des Clusters, der die größte Wahrscheinlichkeit hat dann das Tupel zugewiesen. Symbolisch ausgedrückt, wenn X = (Suburban, Erzeugnissen, konservative) und c0 steht für Cluster 0, wollen wir:
P(c0 | X)
P(c1 | X)
P(c2 | X)
Die erste Wahrscheinlichkeit kann als, gelesen werden "die Wahrscheinlichkeit des Clusters 0 anhand der X-Werte." Tragen Sie nun mit mir für einen Moment. Um diese bedingte Wahrscheinlichkeiten zu berechnen, musst du die Begriffe berechnen ich rufe teilweise Wahrscheinlichkeiten (PP). Nachdem die Teiltöne aller Bedingungen berechnet werden sollen, ist die Wahrscheinlichkeit für jeden Cluster gleich die teilweise für den Cluster geteilt durch die Summe aller Teiltöne. In Symbolen:
P(c0 | X) = PP(c0 | X) / [PP(c0 | X) + PP(c1 | X) + PP(c2 | X)]
P(c1 | X) = PP(c1 | X) / [PP(c0 | X) + PP(c1 | X) + PP(c2 | X)]
P(c2 | X) = PP(c2 | X) / [PP(c0 | X) + PP(c1 | X) + PP(c2 | X)]
Die partielle Wahrscheinlichkeit für P(c0 | X) ist:
PP(c0 | X) = P(Suburban | c0) *
P(VeryHigh | c0) *
P(Conservative | c0) *
P(c0)
= count(Suburban & co) / count c0 *
count(VeryHigh & co) / count c0 *
count(Conservative & c0) / count c0 *
P(c0)
Diese Gleichungen kommen von Bayes-Theorie und sind nicht bei allen klar. Der Begriff "naiv" in Naive Bayes bedeutet, dass die Wahrscheinlichkeit Begriffe in die teilweisen Wahrscheinlichkeiten werden als angenommen mathematisch unabhängig, was zu viel einfacheren Berechnungen als wenn die Begriffe Wahrscheinlichkeit mathematisch abhängigen führt.
Der letzte Begriff, P(c0), ist die "Wahrscheinlichkeit des Clusters 0." Dieser Begriff wird manchmal genannt einen vor und kann auf zwei Arten berechnet werden. Eine Möglichkeit ist, gleiche Prioren, in diesem Fall übernehmen die P(c0) = P(c1) = P(c2) = 1/3. Der andere Weg ist nicht gleiche Prioren zu übernehmen und verwenden die aktuellen Grafen von zugewiesenen Tupel, in welchem Fall P(c0) = count(c0) / (count(c0) + count(c1) + count(c2)). Für den INBIAC-Algorithmus ist es vorzuziehen, gleiche Prioren zu übernehmen.
Beachten Sie, dass die Gleichung muss was gemeinsame Grafen genannt werden. Z. B. count(Suburban & C0) ist die Anzahl der zugewiesenen Tupel, wobei der Cluster c0 und die Tupel-Location ist.
Wenn Sie auf das aktuelle clustering zurückblicken, sehen Sie, dass es ein Problem: an diesem Punkt, wobei nur die ersten drei seed Tupel zugewiesen Clustern, die Count(Suburban & C0) ist 0, wodurch seine Amtszeit 0, die heraus die gesamte partielle Wahrscheinlichkeit Nullen. Um dies zu vermeiden, sind alle die gemeinsamen Grafen mit dem Wert 1 initialisiert. Dies nennt man Laplacian glätten. Laplacian smoothing hinzugefügt auch 3, die Anzahl der Cluster, die Nenner die bedingte Wahrscheinlichkeiten (aber nicht die unbedingte Wahrscheinlichkeit-Begriff). So ist die modifizierte Berechnung für die teilweise für c0:
PP(c0 | X) = P(Suburban | c0) *
P(VeryHigh | c0) *
P(Conservative | c0) *
P(c0)
= count(Suburban & co) / (count c0 + 3) *
count(VeryHigh & co) / (count c0 + 3) *
count(Conservative & c0) / (count c0 + 3) *
1 / numClusters
= (1 / 4) * (1 / 4) * (2 / 4) * (1 / 3)
= 0.0104
Ebenso sind die teilweisen Wahrscheinlichkeiten für c1 und c2:
PP(c1 | X) = count(Suburban & c1) / (count c1 + 3) *
count(VeryHigh & c1) / (count c1 + 3) *
count(Conservative & c1) / (count c1 + 3) *
1 / numClusters
= (1 / 4) * (1 / 4) * (1 / 4) * (1 / 3)
= 0.0052
PP(c2 | X) = count(Suburban & c2) / (count c2 + 3) *
count(VeryHigh & c2) / (count c2 + 3) *
count(Conservative & c2) / (count c2 + 3) *
1 / numClusters
= (2 / 4) * (2 / 4) * (1 / 4) * (1 / 3)
= 0.0208
Nachdem die Teiltöne für jeden Cluster berechnet worden sind, ist es einfach die Wahrscheinlichkeiten für jeden Cluster berechnet werden, die erforderlich sind, um einen Cluster Tupel 1 zuweisen. Hier sind die Berechnungen:
P(c0 | X) = PP(X | c0) / [PP(X | c0) + PP(X | c1) + PP(X | c2)]
= 0.0104 / (0.0104 + 0.0052 + 0.0208)
= 0.2857
P(c1 | X) = PP(X | c1) / [PP(X | c0) + PP(X | c1) + PP(X | c2)]
= 0.0052 / (0.0104 + 0.0052 + 0.0208)
= 0.1429
P(c2 | X) = PP(X | c0) / [PP(X | c0) + PP(X | c1) + PP(X | c2)]
= 0.0208 / (0.0104 + 0.0052 + 0.0208)
= 0.5714
Tupel wird der Cluster mit der größten Wahrscheinlichkeit zugewiesen, in diesem Fall Cluster c2.
Um zusammenzufassen, um ein Tupel zu einem Cluster zuzuweisen, werden die teilweisen Wahrscheinlichkeiten für jeden Cluster berechnet die gemeinsamen Grafen von Tupeln, die bereits zugewiesen wurden. Die Teiltöne werden verwendet, um die Wahrscheinlichkeit zu berechnen, dass das Tupel zu jedem Cluster gehört. Das Tupel wird zum Cluster zugewiesen, die größte Wahrscheinlichkeit hat.
Wichtigsten Datenstrukturen
Es gibt mehrere Möglichkeiten zum Speichern der verschiedenen Daten, die von der INBIAC-clustering-Algorithmus verwendet. Abbildung 3 zeigt die meisten der vom Demoprogramm verwendeten Datenstrukturen. Array-JointCounts wird verwendet, um die teilweisen Wahrscheinlichkeiten zu berechnen, die wiederum verwendet werden, um Cluster-Wahrscheinlichkeiten zu berechnen, die wiederum ein Tupel Zuweisen eines Clusters verwendet werden. Es gibt ein gemeinsames Anklagepunkt für jede Kombination der Attributwert und Cluster. Also, für die Demo, denn es gibt neun Attributwerte (Urban, Suburban,... Konservative) und drei Cluster, es gibt 9 * 3 = 27 gemeinsame zählt. Der erste Index im JointCounts gibt das Attribut, der zweite Index gibt den Attributwert und der dritte Index gibt den Cluster. Beispielsweise enthält die JointCounts [1] [3] [2] die Anzahl der zugewiesenen Tupel, wobei das Einkommen (1) Erzeugnissen (3) und Cluster ist (2).
.png)
Abbildung 3 wichtigsten Datenstrukturen
Array-Clusterunterstützung codiert wie Tupel Clustern zugeordnet sind. Der Index des Arrays clustering ein Tupel und der Wert der Zelle darstellt einen Cluster. Beispielsweise wenn Cluster [0] = 2, dann Tupel 0 Cluster 2 zugeordnet ist. Zellwerte-1 anzugeben, dass das zugehörige Tupel noch nicht zu einem Cluster zugewiesen wurde.
Umsetzung der Clustermethode
Methode-Cluster in aufgeführt ist Abbildung 4. Die Methode akzeptiert als Eingabe TuplesAsInt Array (die Daten gruppiert werden), NumClusters (die Anzahl der Cluster verwenden), NumTrials (das erste Tupel zu Clustern weist), JointCounts (wie weiter oben beschrieben), ClusterCounts (die Anzahl der Tupel, die jedem Cluster zugewiesen, wenn mit nicht-gleich Prioren computing) und EqualPriors (ein boolescher Wert, der angibt, wie die Wahrscheinlichkeiten für jedes Cluster Berechnung beim partielle Wahrscheinlichkeiten berechnen).
Abbildung 4-Methode Cluster
static int[] Cluster(int[][] tuplesAsInt, int numClusters,
int numTrials, int[][][] jointCounts, int[] clusterCounts,
bool equalPriors)
{
int numRows = tuplesAsInt.Length;
int[] clustering = new int[numRows];
for (int i = 0; i < clustering.Length; ++i)
clustering[i] = -1;
int[] goodIndexes = GetGoodIndexes(tuplesAsInt, numClusters, numTrials);
for (int i = 0; i < goodIndexes.Length; ++i)
{
int idx = goodIndexes[i];
clustering[idx] = i;
}
for (int i = 0; i < goodIndexes.Length; ++i)
{
int idx= goodIndexes[i];
for (int j = 0; j < tuplesAsInt[idx].Length; ++j)
{
int v = tuplesAsInt[idx][j];
++jointCounts[j][v][i]; // Very tricky indexing
}
}
for (int i = 0; i < clusterCounts.Length; ++i)
++clusterCounts[i];
for (int i = 0; i < tuplesAsInt.Length; ++i)
{
if (clustering[i] != -1) continue; // Tuple already clustered
double[] allProbabilities = AllProbabilities(tuplesAsInt[i],
jointCounts, clusterCounts, equalPriors);
int c = IndexOfLargestProbability(allProbabilities);
clustering[i] = c; // Assign tuple i to cluster c
for (int j = 0; j < tuplesAsInt[i].Length; ++j)
{
int v = tuplesAsInt[i][j];
++jointCounts[j][v][c];
}
++clusterCounts[c];
} // Main loop
return clustering;
}
Cluster-Methode beginnt mit der Speicherzuweisung für das Cluster-Array und Zuweisen von Werten von-1 in jeder Zelle, kein Cluster angegeben auf die zugehörigen Tupel zugewiesen wurde. Anschließend wird Hilfsmethode GetGoodIndexes aufgerufen, um die Indizes Tupel zu erhalten, die maximal von einander abweichen. Ich erkläre kurz die Methode GetGoodIndexes. Methode Cluster weiter die gute Indizes verwendet, das clustering Array initialisiert und aktualisiert dann die JointCounts und ClusterCounts-Arrays.
Die Hauptverarbeitungsschleife durchläuft jedes Daten-Tupel in Ordnung und berechnet die Wahrscheinlichkeit, dass das aktuelle Tupel zu jedem Cluster mithilfe der Methode AllProbabilities gehört. Dann wird der Index der größten Wahrscheinlichkeit mit Helfer IndexOfLargestProbability bestimmt. Da Clustern nullbasiert sind, diesen Index stellt auch den besten Cluster, und es wird verwendet, um einen Cluster (im Cluster Array) aktuelle Tuple zuweisen, und aktualisieren Sie die Arrays, JointCounts und ClusterCounts.
Da die Verarbeitungsschleife immer auf Tupel [0] beginnt, das effektiv mehr Gewicht auf Tupel mit niedrigeren Indizes gibt. Eine Alternative ist die Tupel in zufälliger Reihenfolge durchlaufen. Beachten Sie, dass der INBIAC-Algorithmus Tupel, die basierend auf der größten Wahrscheinlichkeit der Clustermitgliedschaft zuweist. Sie könnten auch berechnen und den Durchschnitt der diese größten Wahrscheinlichkeiten zurück. Dies wäre ein gewisses Maß an Vertrauen in die Cluster-Zuweisungen. Dann könnte rufen Sie Methode Cluster mehrere Male und Rückkehr der Clusterbildung, die durch den Aufruf, der das höchste Vertrauen ergab produziert wurde.
Eine weitere Option verwende ich oft ist Nachbearbeitung von Methode Cluster zu versuchen und generieren eine bessere Cluster Cluster Ergebnis. Die Idee in Pseudocode ist:
loop n times
select a random tuple index
unassign the tuple from its curr cluster
assign the tuple using non-equal priors computation
end loop
Erinnern Sie, dass INBIAC Cluster Zuordnung, die ein Tupel zu einem Zeitpunkt aufbaut durch das finden des Clusters des aktuellen Tupels mit größter Wahrscheinlichkeit gehört. Die Wahrscheinlichkeiten sind gleiche Prioren, was bedeutet, dass die Wahrscheinlichkeiten für jedes Cluster angenommen werden gleich berechnet. Aber nach Clusterbildung, gibt es nun weitere Informationen über wie wahrscheinlich jedes Cluster ist, und dass Informationen verwendet werden können, möglicherweise das Clusterbildung Ergebnis zu verbessern. Codedownload implementiert diese Option verwenden eine Methode namens zu verfeinern.
Immer gute Startwert Tupel
Der INBIAC-Algorithmus Samen jeder Cluster mit einem einzigen Tupel. Es ist wichtig, dass diese Samen-Tupel so unterschiedlich von einander wie möglich sein. Es gibt viele Maßnahmen der Verschiedenheit von clustering-Algorithmen verwendet. Methode GetGoodIndexes erzeugt eine Reihe von zufälligen Kandidaten Indizes, dann berechnet die Gesamtzahl der Tupel-Attribute, die verschieden sind, eine Metrik, genannt den Hamming-Abstand. Dieser Prozess ist wiederholte NumTrials Mal, und die Indizes, die die größte Verschiedenheit haben Tupel zurückgegeben.
Betrachten Sie beispielsweise die Daten in Abbildung 1. Genommen Sie an, die Kandidaten-Indizes sind 0, 1, 2. Die entsprechenden Daten-Tupel sind:
[0] Suburban VeryHigh Liberal
[1] Rural Medium Conservative
[2] Suburban VeryHigh Conservative
Tupel [0] und [1] unterscheiden sich in drei Positionen; Tupel [0] und [2] unterscheiden sich in einer Position; und Tupel [1] und [2] unterscheiden sich in zwei Positionen, für eine total Delta 3 + 1 + 2 = 6. In Pseudocode ist Methode GetGoodIndexes:
init a result array
loop numTrials times
generate numClusters distinct random tuple indexes
compute their dissimilarity
if curr dissimilarity > greatest dissimilarity
greatest dissimilarity = curr dissimilarity
store curr indexes into result array
end if
end loop
return result array
Vielleicht möchten alternative Ansätze zu berücksichtigen. Eine erweiterte Option ist zu beobachten, dieses Attribut Einkommen — mit Werten Low, Medium, High und Erzeugnissen — ist von Natur aus numerisch. Also könnten Sie die Methode GetGoodIndexes ändern, so dass der Unterschied zwischen Low und Erzeugnissen größer als der Unterschied zwischen Low und Medium ist.
Die unterschiedliche Kandidaten Saatgut Tupel Indizes generieren, ist eine interessante kleine Teilproblem. Dies erfolgt durch Hilfsmethode GetRandomIndexes. Im Pseudocode funktioniert die Methode so:
init a dictionary to store result indexes
init a result array
set count = 0
while count < numClusters
generate a random tuple index
if index not in dictionary
add index to result set
add index to dictionary
increment count
end if
end while
return result
Diese Technik ist ein ziemlich Brute-Force-Ansatz, aber es hat funktioniert gut für mich in der Praxis.
Zusammenfassung
Dieser Artikel, zusammen mit dem Code für den Demo-Programm, sollte Ihnen eine solide Basis für das Experimentieren mit Naive Bayes clustering und ein Softwaresystem Cluster-Funktionalität hinzufügen. Ich entwickelte die INBIAC clustering-Algorithmus während der Arbeit an einem Projekt, das ein extrem großes Dataset hatte, das numerische und kategorische Daten enthalten. Ich fand, dass vorhandene Cluster Tools waren entweder zu langsam funktionierte nicht bei allen oder schlechte Ergebnisse gab. Der hier vorgestellte Algorithmus kann sowohl kategorische und numerische Daten bewältigen, (wenn numerische Daten in Kategorien klassifiziert werden), kann große Datenmengen verarbeiten und ist sehr schnell.
Wie in der Einleitung erwähnt, Forschung legt nahe, dass es keine einzelne beste clustering-Algorithmus, aber eher das Sie müssen experimentieren mit verschiedenen Algorithmen, um die besten Ergebnisse zu erzielen. Die Möglichkeit, Datensätze zu erkunden, mit clustering basierend auf Naive Bayes Inferenz kann eine wertvolle Ergänzung für Ihre technischen Fertigkeiten sein.
Dr. James McCaffrey arbeitet für Volt Information Sciences Inc., wo er technische Schulungen für Softwareentwickler bei der Microsoft in Redmond, Washington Campus. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem an Internet Explorer und MSN Search. Dr. McCaffrey ist der Autor von ".NET Test Automation Recipes" (Rezepte für die .NET-Testautomatisierung, Apress 2006) und kann unter jammc@microsoft.com erreicht werden.
Unser Dank gilt dem folgenden technischen Experten für die Durchsicht dieses Artikels: Dan Liebling