Cet article a fait l'objet d'une traduction automatique.
Clustering de données
Données de Clustering utilisant l'inférence de Bayes Naive
Télécharger l'exemple de code
Regroupement de données sont une technique d'apprentissage automatique qui possède de nombreuses importantes applications pratiques, telles que le regroupement des données de ventes pour révéler le comportement de consommateur-achat ou regroupement de données sur le réseau pour donner un aperçu des profils de communication.Regroupement de données estégalement également utiles pour l'identification des points de données anormales.Dans cet article, je présenterai un programme c# complet que vous pouvez utiliser comme base pour l'ajout de fonctionnalités de gestion de clusters à un système logiciel ou pour créer un utilitaire de gestion de clusters autonome puissant.
Il y a plusieurs différents algorithmes de regroupement, en partie parce que l'efficacité d'un algorithme de clustering dépend dans une certaine mesure les caractéristiques des données étant groupées.L'algorithme plus commun est appelé clustering k-means.Malheureusement, cet algorithme est applicable uniquement pour les éléments de données numériques.En revanche, l'algorithme de clustering que dans cet article, je vais présenter est issu d'une technique appelée inférence Naive Bayes, qui fonctionne avec les données numériques ou catégoriques.Bien que toutes les idées utilisées dans l'algorithme de clustering présentée ici sont bien connues, l'algorithme global et la mise en œuvre spécifique ont pas, au meilleur de ma connaissance, été publiés auparavant.J'appelle cet algorithme et son implémentation itérative Naive Bayesian inférence classification ascendante Clustering (INBIAC) pour le distinguer des autres techniques de clusters.Naïve Bayes inférence est une technique très courante pour effectuer la classification des données, mais on ne sait généralement pas que Naive Bayes peut également être utilisé pour le regroupement de données.
La meilleure façon de comprendre où je veux en venir dans cet article est de jeter un oeil à Figure 1.Le programme de démonstration commence par générer huit tuples de données aléatoires qui décrivent l'emplacement (urbaine, suburbaine ou rurale), revenu (faible, moyen, élevé ou très élevé) et politique (libéraux ou conservateurs) de huit personnes hypothétiques.Le programme, puis charge les données brutes de chaîne dans la mémoire et convertit les données en valeurs int pour permettre un traitement efficace.Par exemple, le dernier tuple de (« Rural », «Low», « conservateur ») est stocké comme (2, 0, 1).
.png)
Figure 1 données Clustering utilisant l'inférence de Bayes Naive
De nombreux algorithmes de regroupement, y compris INBIAC, exigent le nombre de clusters à préciser.Ici, la variable numClusters est définie sur 3.Le programme de démonstration de clusters les données et affiche ensuite le regroupement final de [2, 0, 2, 1, 1, 2, 1, 0].Dans les coulisses, l'algorithme de graines groupes 0, 1 et 2 avec tuples 1, 6 et 0, respectivement.Puis chacun des cinq tuples restants est assignée, un à la fois, à un cluster.Ce type d'algorithme est appelé classification ascendante.
Parce qu'aucune intervention utilisateur ou des données de formation n'est nécessaire, le clustering est quelquefois appelée « apprentissage non supervisé ». Chaque index dans le tableau de clustering représente un tuple et la valeur du tableau est un ID de cluster.Tuple 2 ("Banlieue", « VeryHigh », "conservateur") est donc assignée à 0, tuple 1 de cluster (« Rural », « moyen, » « Conservateur ») est assigné au groupe 2 et ainsi de suite.
Le programme de démonstration se termine en affichant le fichier RAW original sous forme de cluster.Comme vous pouvez le voir, le regroupement final semble raisonnable.Et si vous regardez les données d'origine, je pense que vous serez d'accord qu'il serait extrêmement difficile d'essayer de regrouper les données manuellement, même pour les très petits ensembles de données.
Cet article suppose que vous avancent des compétences en programmation avec un langage C-famille, mais n'assume pas que vous avez une expérience avec inférence Naive Bayes ou algorithmes de clustering.Le programme de démonstration montré Figure 1 est une application de console c# simple.J'ai codé il sans utiliser des techniques de programmation orientée objet, donc vous pouvez plus facilement Refactoriser aux langages qui ne supportent pas complètement poo.
J'ai enlevé tous les erreur vérification pour garder les idées aussi claires que possible.Le code pour le programme de démonstration est trop long pour présenter dans son intégralité dans cet article, donc je vais me concentrer sur expliquant les éléments clés de l'algorithme.Le code source complet pour le programme de démonstration est disponible à archive.msdn.microsoft.com/mag201303INBIAC.
Structure du programme
La structure globale du programme, avec quelques commentaires et instructions de WriteLine enlevées, est répertoriée dans Figure 2.
Figure 2 Structure de programme Clustering
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
J'ai utilisé Visual Studio 2010 pour créer une application de console Visual c# nommée ClusteringBayesian. Dans la fenêtre de l'Explorateur de solutions, j'ai renommé le fichier Program.cs à la ClusteringBayesian plus descriptifProgram.cs, renommé automatiquement la classe unique. J'ai supprimé inutiles générés par modèle de références aux espaces de noms .NET ; vous remarquez le programme comporte quelques dépendances et nécessite seulement l'espace de noms Systems.Collections.Generic.
Je déclare un objet Random de portée de la classe nommé aléatoire. Cet objet est utilisé pour générer des données brutes semi-aléatoire et de déterminer quels tuples à utiliser pour chaque grappe de graines. Dans la méthode Main, j'instancie aléatoire à l'aide d'une valeur de départ de 6, seulement parce que cela génère une démo de belle apparence.
Les quelques lignes du programme démo utilisent des méthodes d'assistance MakeData et ShowData pour générer et afficher les huit lignes de données factices. MakeData appelle sub-helper MakeParty, MakeLocation, MakeIncome et MakePolitics. Si vous voulez expérimenter avec tuples de données spécifique en dur, vous pouvez remplacer ce code avec, par exemple :
int numTuples = 4;
string[] rawData = new string[] { "Urban,VeryHigh,Liberal",
"Rural,Medium,Conservative", "Urban,Low,Liberal",
"Suburban,Medium,Liberal" };
Ensuite, la démo programme hardcodes l'attribut nomme emplacement, revenu et la politique. Dans certains scénarios, par exemple, si vos données brutes dans un fichier texte avec un en-tête ou d'une table SQL avec des noms de colonnes, vous pouvez analyser vos données et de déterminer par programme le nom de l'attribut.
La démo de programme aussi hardcodes les valeurs d'attribut urbain, suburbain et Rural pour l'emplacement ; Low, moyenne, haute et VeryHigh pour le revenu ; et libéraux et les conservateurs pour la politique. Encore une fois, dans certains scénarios, vous pouvez numériser vos données brutes pour déterminer par programme les valeurs d'attribut.
Le programme de démonstration appelle helper méthode LoadData pour charger les données brutes de chaîne dans un tableau de tableaux dans la mémoire. Pour les très grands ensembles de données, ce ne serait pas possible. Dans de telles situations, vous devrez charger des blocs de données à un moment ou parcourir les données brutes stockées à l'extérieur une ligne ou une ligne à la fois.
Bien qu'il soit possible de travailler directement avec les données de type chaîne brute, c'est beaucoup plus efficace de travailler avec les données codées en tant que type int. Donc, ensuite, méthode d'assistance TuplesToInts accepte le tableau de tableaux de chaînes, ce tableau ne parcoure, convertit chaque chaîne à un index de base zéro et stocke toutes les données dans un tableau de tableaux de type int. Encore une fois, pour très grands ensembles de données vous devrez lire données brutes une ligne à la fois et de convertir des valeurs d'attribut d'entiers (ints) à la volée.
Le programme de démonstration prépare la routine de gestion de clusters en deux valeurs de paramètre de réglage. Paramètre numClusters indique le nombre de clusters à générer. En général, les données de clustering sont un processus exploratoire et vous devez expérimenter avec différentes valeurs de numClusters (bien qu'il y a quelques techniques fascinants pour déterminer par programme un nombre optimal de grappes). Paramètre numTrials est utilisé par la routine de gestion de clusters lors de la génération le regroupement initial, comme je l'expliquerai bientôt.
La méthode de clustering requiert deux tableaux de tenir les comtes de tuples assignée à un moment donné dans l'algorithme INBIAC. Tableau jointCounts contient le nombre de tuples en cluster qui ont une valeur d'attribut particulier et un cluster spécifique. Le tableau de jointCounts est un peu délicat, et je vais vous expliquer plus en détail prochainement. Mais chaque valeur de jointCounts est initialisé à 1 dans le cadre d'une étape importante dans la technique de bayésien appelée laplacien lissage. Le second tableau, clusterCounts, contient le nombre de tuples assignées à chaque faisceau à un moment donné. L'indice de clusterCounts représente un cluster, et la valeur est le nombre d'associés.
Le regroupement est effectué par la méthode Cluster. Cluster de la méthode retourne un tableau qui encode quel cluster est attribuée à chaque tuple. Le programme de démonstration conclut en affichant le tableau clustering et en affichant les données brutes regroupées en cluster à l'aide de la méthode d'assistance DisplayClustered.
Naïve Bayes inférence
La clé pour comprendre l'algorithme INBIAC afin que vous serez en mesure de modifier le code de démo pour vos propres besoins est la compréhension inférence Naive Bayes. Naive Bayes est mieux expliquée par exemple. Supposons que vous avez les huit tuples montre Figure 1 et que vous voulez placer chaque tuple dans un des trois groupes :
[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
Supposons d'abord que chaque groupe reçoit un tuple unique graine (d'une manière qui sera expliqué plus tard) afin que le tuple 1 est affecté à la grappe de 0, tuple 6 est attribué au groupe 1 et tuple 0 est affecté au groupe 2. Il existe plusieurs façons de représenter ce regroupement, mais l'algorithme INBIAC stockerait les informations sous forme de tableau :
[ 2, 0, -1, -1, -1, -1, 1, -1 ]
Dans ce tableau, les index de tableau sont des tuples, les valeurs du tableau sont des grappes et une valeur de -1 indique le tuple associé n'ont pas encore été inscrits à un cluster. Donc, du point de vue conceptuel, le regroupement à ce stade est :
c0 : Rural Medium Conservative (tuple 1)
c1 : Urban Low Liberal (tuple 6)
c2 : Suburban VeryHigh Liberal (tuple 0)
Maintenant l'objectif est d'attribuer le premier tuple non attribué, tuple 2 (Suburban, VeryHigh, conservateur), à l'un des trois pôles. Naive Bayes calcule les probabilités ce tuple 2 appartient aux clusters de 0, 1 et 2 et puis assigne le tuple pour le cluster qui a le plus de chance. Exprimée symboliquement, si X = (Suburban, VeryHigh, conservateur) et c0 est synonyme de cluster 0, nous voulons :
P(c0 | X)
P(c1 | X)
P(c2 | X)
La première probabilité peut être lu comme, « la probabilité du cluster 0 étant donnée les valeurs de X. » Maintenant, la garder avec moi pour un moment. Pour calculer ces probabilités conditionnelles, il faut calculer les termes j'appelle probabilités partielles (PP). Après que les partiels pour chacune des conditions sont calculés, la probabilité pour chaque cluster est égale à la partielle pour le cluster divisée par la somme de tous les partiels. Symboliquement :
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)]
La probabilité partielle pour P(c0 | X) est :
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)
Ces équations proviennent de la théorie de Bayes et ne sont pas du tout évidentes. Le terme « naïf » dans Naive Bayes signifie que chacun des termes probabilité dans les probabilités partielles sont supposés pour être mathématiquement indépendants, ce qui conduit à des calculs beaucoup plus simples que si les conditions de probabilité dépendaient mathématiquement.
Le dernier terme, P(c0), est la « probabilité de cluster 0 ». Ce terme est parfois appelé un avant et peut être calculé de deux façons différentes. Une façon consiste à supposer égal a priori, auquel cas le P(c0) = P(c1) = P(c2) = 1/3. L'autre façon est pas supposer a priori égales et utiliser des comtes actuels de tuples assigné, dans quels cas P(c0) = count(c0) / (count(c0) + count(c1) + count(c2)). Pour l'algorithme INBIAC, il est préférable de supposer a priori égales.
Notez que l'équation a besoin de ce qu'on appelle les chefs d'accusation conjointes. Par exemple, count(Suburban & C0) est le nombre de tuples assignée, où le cluster est c0 et l'emplacement de tuple est Suburban.
Si on regarde vers le regroupement actuel, vous verrez qu'il y a un problème : à ce stade, avec seulement les trois premiers tuples assignés aux clusters, la count(Suburban & des graines C0) est 0, ce qui rend son terme 0, zéro, la toute probabilité partielle. Pour éviter cela, les chefs d'accusation conjointes sont tous initialisés avec une valeur de 1. Cela s'appelle le laplacien de lissage. Laplacien lissage aussi ajoute 3, le nombre de clusters, les dénominateurs des probabilités conditionnelles (mais pas la notion de probabilité inconditionnelle). Mis à jour le calcul pour le partiel de c0 est donc :
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
De même, les probabilités partielles pour c1 et c2 sont :
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
Après que les partiels pour chaque cluster ont été calculées, il est facile de calculer les probabilités pour chaque cluster qui sont nécessaires pour attribuer le tuple 1 à un cluster. Voici les calculs :
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
Le tuple est assigné au cluster avec le plus de chance, qui est en l'occurrence cluster c2.
Pour résumer, pour assigner un tuple à un cluster, les probabilités partielles pour chaque cluster sont calculées à l'aide de comtes conjointes de tuples qui ont déjà été attribués. Partiels sont utilisés pour calculer la probabilité que le tuple appartienne à chaque cluster. Le tuple est assigné au cluster qui a le plus de chance.
Structures de données clés
Il y a plusieurs façons de stocker les données différentes utilisées par l'algorithme de clustering de INBIAC. La figure 3 montre la plupart des structures de données utilisées par le programme de démonstration. Tableau jointCounts est utilisée pour calculer les probabilités partielles qui à leur tour, servent à calculer les probabilités de clusters qui à leur tour servent à attribuer un tuple à un cluster. Il y a un chef d'accusation conjointe pour toutes les combinaisons de valeur d'attribut et de cluster. Donc, pour la démo, parce qu'il y a des valeurs d'attribut neuf (urbain, suburbain,... Conservateur) et trois groupes, il y a 9 * 3 = 27 mixte compte. Le premier index de jointCounts indique l'attribut, le second indice indique la valeur de l'attribut et le troisième index cluster. Par exemple, jointCounts [1], [3] [2] contient le nombre de tuples affectées où le revenu (1) est VeryHigh (3) et cluster (2).
.png)
Figure 3 Structures de données clés
Tableau de clustering encode comment tuples sont assignés aux clusters. L'index de tableau de clustering représente un tuple, et la valeur de la cellule représente un cluster. Par exemple, si le regroupement [0] = 2, tuple 0 est assignée au groupe 2. Les valeurs de cellule-1 indiquent que le tuple associé n'ont pas encore été inscrits à un cluster.
Mise en œuvre de la méthode de Clustering
Méthode Cluster est répertorié dans Figure 4. La méthode accepte en entrée le tableau tuplesAsInt (les données à être mis en cluster), numClusters (le nombre de clusters à utiliser), numTrials (qui attribue les tuples initiales aux clusters), jointCounts (comme expliqué plus haut), clusterCounts (le nombre de tuples assignées à chaque faisceau, nécessaire si informatique avec a priori inégal) et equalPriors (une valeur booléenne qui indique comment calculer les probabilités de chaque cluster lors du calcul des probabilités partielles).
Figure 4 méthode 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 de la méthode commence par allocation de mémoire pour le tableau de clustering et attribuant des valeurs de -1 dans chaque cellule, pour indiquer sans cluster a été assignée au tuple associé. Ensuite, la méthode d'assistance GetGoodIndexes est appelée pour obtenir les indices de la n-uplets qui diffèrent au maximum les uns des autres. Je reviendrai bientôt méthode GetGoodIndexes. Méthode Cluster utilise ensuite les bons indices pour initialiser le tableau clustering et puis met à jour les tableaux jointCounts et clusterCounts.
La boucle de traitement principale parcourt chaque tuple de données dans l'ordre et calcule les probabilités que l'objet tuple appartienne à chaque cluster à l'aide de la méthode AllProbabilities. L'indice de la plus grande probabilité est déterminée à l'aide d'assistance IndexOfLargestProbability. Parce que les grappes sont de base zéro, cet index représente également le regroupement de meilleur, et il est utilisé pour assigner l'objet tuple à un cluster (dans la baie de clustering) et mettre à jour les tableaux jointCounts et clusterCounts.
Parce que la boucle de traitement commence toujours au tuple [0], cela donne effectivement plus de poids aux tuples avec des index de numéros inférieurs. Une alternative consiste à parcourir les tuples dans un ordre aléatoire. Remarquez que l'algorithme INBIAC assigne des tuples basé sur la plus grande probabilité de membres des classes. Vous pouvez également calculer et retourner la moyenne de ces plus grandes probabilités. Ce serait une mesure de confiance dans les attributions de cluster. Puis vous pouvez appeler la méthode Cluster plusieurs fois et retour le regroupement qui a été produit par l'appel qui a abouti à la plus haute confiance.
Une autre option, que j'ai souvent recours est à post-traiter le résultat groupement produit par méthode Cluster pour essayer de générer une meilleure concentration. L'idée en pseudo-code est :
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
Rappelons que INBIAC s'accumule cluster cession un tuple à un moment en trouvant le cluster l'objet tuple appartient à avec une probabilité plus grande. Les probabilités sont calculées à l'aide des Prieurs égales, ce qui signifie que la probabilité de chaque cluster est supposée pour correspondre. Mais après la mise en cluster, il y a maintenant plus d'informations sur comment probablement chaque cluster, et que des informations peuvent être utilisées pour peut-être améliorer le résultat du regroupement. Le téléchargement de code implémente cette option en utilisant une méthode nommée affiner.
Obtenir la bonne semence Initial Tuples
L'algorithme INBIAC graines de chaque cluster avec un tuple unique. Il est important que les tuples de ces semences soient aussi différents les uns des autres que possible. Il existe de nombreuses mesures de dissimilitude utilisé par les algorithmes de clustering. Méthode GetGoodIndexes génère un ensemble des index candidats au hasard, puis calcule le nombre total de tuple des attributs différents, une mesure appelée la distance de Hamming. Ce processus est répété numTrials fois, et les indices des tuples ayant la plus grande dissemblance sont retournés.
Par exemple, considérons les données dans Figure 1. Supposons que l'index candidats sont 0, 1, 2. Les tuples de données correspondantes sont :
[0] Suburban VeryHigh Liberal
[1] Rural Medium Conservative
[2] Suburban VeryHigh Conservative
Tuples [0] et [1] se distinguent en trois positions ; tuples [0] et [2] sont différentes dans la même position ; et n-uplets [1] et [2] se distinguent en deux positions, pour un total delta de 3 + 1 + 2 = 6. En pseudo-code, la méthode GetGoodIndexes est :
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
Vous pouvez envisager d'autres approches. Une option avancée est d'observer cet attribut revenu — avec des valeurs de Low, moyenne, haute et VeryHigh — est intrinsèquement numérique. Donc vous pourriez modifier la méthode GetGoodIndexes afin que la différence entre Low et VeryHigh est supérieure à la différence entre la Low et moyenne.
Générer les index de tuple de semences candidat distincts est un sous-problème peu intéressant. Ceci est effectué par la méthode d'assistance GetRandomIndexes. En pseudo-code, cette méthode fonctionne de la manière suivante :
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
Cette technique est une approche assez la force brute, mais il a bien fonctionné pour moi dans la pratique.
Synthèse
Cet article, ainsi que le code pour le programme de démonstration, devrait vous donner une base solide pour expérimenter avec bayésien naïf de clustering et l'ajout de fonctionnalités de clustering à un système logiciel. J'ai développé le INBIAC algorithme de clustering alors qu'il travaillait sur un projet qui avait un très grand ensemble de données contenait des données numériques tant catégoriques. J'ai trouvé que les outils existants de gestion de clusters étaient trop lent, n'a pas fonctionné du tout ou a donné des résultats médiocres. L'algorithme présenté ici peut traiter des données catégorielles et de numériques (si les données numériques sont mis en cellule en catégories), peut gérer des jeux de données énormes et est très rapide.
Comme je l'ai mentionné dans l'introduction, la recherche suggère qu'il n'y a aucun meilleur seul algorithme, mais plutôt que vous devez expérimenter avec différents algorithmes pour obtenir les meilleurs résultats. La capacité d'explorer les ensembles de données avec le clustering basé sur l'inférence Naive Bayes peut être un ajout précieux à votre ensemble de compétences techniques.
Dr. James McCaffrey travaille pour Volt Information Sciences Inc., où il gère la formation technique d'ingénieurs logiciels travaillant à la Microsoft Redmond, Wash., campus de. Il a collaboré à plusieurs produits Microsoft, comme Internet Explorer et MSN Search. Il est l’auteur de « NET Test Automation Recipes » (Apress, 2006). Vous pouvez le contacter à l’adresse jammc@microsoft.com.
Merci à l'expert technique suivant d'avoir relu cet article : Dan Liebling