Clustering de données
Détection d'anomalies dans des données à l'aide de clustering k-Means
Réfléchissez un instant au problème de l'identification d'anomalies dans de très grands ensembles de données, par exemple, l'identification de transactions de cartes de crédit potentiellement frauduleuses, les demandes de prêt trop risquées, etc. Une des approches possibles de la détection de données anormales est de grouper les éléments de données en clusters similaires et de rechercher à l'intérieur d'un cluster les éléments de données qui sont, d'une façon ou d'une autre, différents des autres éléments du cluster.
Il existe de nombreux algorithmes différents pour le clustering (c.-à-d., la répartition en clusters). L'un des plus anciens et plus répandus est l'algorithme k-means. Dans cet article, je vous expliquerai comment fonctionne l'algorithme k-means et je vous présenterai un programme de démonstration complet en C#. Il existe de nombreux outils autonomes de clustering de données, alors quel intérêt y-a-t-il à créer entièrement le code pour le clustering k-means ? Les outils de clustering existants peuvent être difficiles, voire impossibles, à intégrer dans un système logiciel. Vous ne pourrez pas forcément les personnaliser pour le traitement de scénarios inhabituels, et ils peuvent être soumis à un copyright ou des droits de propriété intellectuelle. Après avoir lu cet article, vous serez en mesure de tester le clustering k-means et disposerez des notions de base afin d'ajouter une fonctionnalité de clustering à une application .Net.
Pour vous faire une idée de ce qu'est le clustering k-means et pour voir où je veux en venir avec cet article, jetez un coup d'œil à la figure 1. Le programme de démonstration débute par la création d'un ensemble de données factice de 20 éléments. Dans la terminologie du clustering, les éléments de données sont appelés tuples. Chaque tuple représente ici une personne et est doté de deux valeurs d'attributs numériques : une hauteur en pouces et un poids en livres. Une des limitations de l'algorithme k-means est qu'il ne peut être appliqué que lorsque les tuples de données sont exclusivement numériques.
.png)
Figure 1 Clustering à l'aide de k-Means
Les données factices sont chargées en mémoire dans un tableau (array). Ensuite, le nombre de clusters est défini sur trois. Bien qu'il existe des techniques pointues de clustering qui peuvent vous suggérer le nombre optimal de clusters à utiliser, le clustering de données est en général un processus exploratoire, et le nombre idéal de clusters à utiliser est souvent obtenu par une suite de tentatives plus ou moins fructueuses. Comme vous le verrez bientôt, le clustering k-means est un processus itératif. Le programme de démonstration comprend une variable maxCount, utilisée pour limiter le nombre d'exécutions de la boucle de clustering principale. Ici, la valeur est définie, de façon arbitraire, sur 30.
Ensuite, en arrière-plan, le programme de démonstration utilise l'algorithme k-means pour placer chaque tuple de données dans un des trois clusters. Il existe de nombreuses façons d'encoder le clustering. Dans le cas présent, un clustering est défini par un tableau d'entiers dans lequel l'index du tableau représente un tuple, et la valeur associée représente l'ID de base 0 du cluster. Donc, dans la figure 1, le tuple 0 (65, 220) est affecté au cluster 0, le tuple 1 (73, 160) est affecté au cluster 1, le tuple 2 (59, 110) est affecté au cluster 2, le tuple 3 (61, 120) est affecté au cluster 2, etc. Notez qu'il y a huit tuples affectés au cluster 0, cinq tuples au cluster 1 et sept tuples au cluster 2.
Ensuite, le programme de démonstration affiche les données, regroupées par cluster. Si vous examinez les données en cluster, vous constaterez que le cluster 0 correspond aux personnes les plus lourdes, le cluster 1 aux personnes les plus grandes et le cluster 2 aux personnes les plus petites. Le programme de démonstration se termine par l'analyse des tuples affectés au cluster 0 et détermine en fonction d'un critère prédéfini, que le tuple 5 (67, 240) est le plus anormal.
Dans les sections qui suivent, je vous présenterai en détail le code qui a permis d'obtenir les captures d'écran de la figure 1 afin que vous puissiez le modifier de façon à répondre à vos propres besoins. Cet article suppose que vous ayez des compétences de niveau intermédiaire en programmation avec le langage de famille C, mais ne suppose pas que vous ayez des connaissances en matière de clustering. J'ai codé ce programme de démonstration à l'aide de C#, mais j'ai utilisé un style non-OOP. Vous ne devriez donc pas avoir trop de difficultés à transcrire le code dans un autre langage si vous le souhaitez. L'intégralité du code du programme de démonstration est présentée dans cet article. Ce code est également disponible sur archive.msdn.microsoft.com/mag201302kmeans.
L'algorithme k-Means
En principe, tout au moins, l'algorithme k-means est assez simple. Mais comme vous le verrez, certains détails d'implémentation peuvent être un peu plus complexes. Le concept central de l'algorithme k-means est la notion de centroïde. En clustering de données, le centroïde d'un ensemble de tuples de données est le tuple qui est le plus représentatif du groupe. La meilleure façon d'expliquer cette notion est d'étudier un exemple. Imaginons que vous ayez trois tuples de poids-taille similaires à ceux de la figure 1 :
[a] (61.0, 100.0)
[b] (64.0, 150.0)
[c] (70.0, 140.0)
Quel tuple est le plus représentatif ? L'une des approches possibles consiste à calculer mathématiquement une moyenne (mean en anglais), puis de sélectionner comme centroïde le tuple qui est le plus proche du tuple moyen. Donc, dans notre cas d'exemple, le tuple moyen est :
[m] = ((61.0 + 64.0 + 70.0) / 3, (100.0 + 150.0 + 140.0) / 3)
= (195.0 / 3, 390.0 / 3)
= (65.0, 130.0)
Et maintenant, lequel de nos trois tuples est le plus proche de (65, 130) ? Il existe plusieurs façons de concevoir la notion de « plus proche ». L'approche la plus courante, et celle utilisée dans le programme de démonstration, est d'utiliser la distance euclidienne. La définition en est la suivante : la distance euclidienne entre deux tuples est la racine carrée de la somme des différences au carré entre chacun des composants des tuples. Une fois de plus, la meilleure explication est l'exemple. La distance euclidienne entre le tuple (61, 100) et le tuple moyen (65, 130) est :
dist(m,a) = sqrt((65.0 - 61.0)^2 + (130.0 - 100.0)^2)
= sqrt(4.0^2 + 30.0^2)
= sqrt(16.0 + 900.0)
= sqrt(916.0)
= 30.27
Similairement :
dist(m,b) = sqrt((65.0 - 64.0)^2 + (130.0 - 150.0)^2)
= 20.02
dist(m,c) = sqrt((65.0 - 70.0)^2 + (130.0 - 140.0)^2)
= 11.18
Comme la plus petite des trois distances est la distance entre la moyenne mathématique et le tuple [c], le centroïde des trois tuples est le tuple [c]. Vous pouvez peut-être tester le programme de démonstration en utilisant différentes définitions des distances entre deux tuples afin de comparer les différents résultats obtenus pour le clustering final.
Lorsque la notion de centroïde du cluster est bien établie, l'algorithme k-means est relativement simple. En voici le pseudo-code :
assign each tuple to a randomly selected cluster
compute the centroid for each cluster
loop until no improvement or until maxCount
assign each tuple to best cluster
(the cluster with closest centroid to tuple)
update each cluster centroid
(based on new cluster assignments)
end loop
return clustering
Si vous effectuez des recherches sur le Web, vous trouverez plusieurs animations bien réalisées présentant l'algorithme k-means en action. L'image de la figure 2 présente le clustering produit par le programme de démonstration. L'élément de données entouré dans chaque cluster est le centroïde du cluster.
.png)
Figure 2 Données en cluster et centroïdes
Structure générale du programme
La structure générale du programme pour la démonstration présentée dans la figure 1, avec quelques modifications mineures, est répertoriée dans la figure 3. J'ai utilisé Visual Studio 2010 pour créer une nouvelle application de console en C#, appelée ClusteringKMeans. N'importe quelle version récente de Visual Studio devrait également pouvoir être utilisée. Dans la fenêtre de l'explorateur de solutions, j'ai renommé le fichier Program.cs en ClusteringKMeans.cs, ce qui a eu pour effet de renommer automatiquement la classe générée avec le modèle. J'ai supprimé le superflu à l'aide d'arguments au début du fichier.
Figure 3 Structure générale du programme
using System;
namespace ClusteringKMeans
{
class ClusteringKMeansProgram
{
static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin outlier data detection demo\n");
Console.WriteLine("Loading all (height-weight) data into memory");
string[] attributes = new string[] { "Height", "Weight" };
double[][] rawData = new double[20][];
rawData[0] = new double[] { 65.0, 220.0 };
rawData[1] = new double[] { 73.0, 160.0 };
rawData[2] = new double[] { 59.0, 110.0 };
rawData[3] = new double[] { 61.0, 120.0 };
rawData[4] = new double[] { 75.0, 150.0 };
rawData[5] = new double[] { 67.0, 240.0 };
rawData[6] = new double[] { 68.0, 230.0 };
rawData[7] = new double[] { 70.0, 220.0 };
rawData[8] = new double[] { 62.0, 130.0 };
rawData[9] = new double[] { 66.0, 210.0 };
rawData[10] = new double[] { 77.0, 190.0 };
rawData[11] = new double[] { 75.0, 180.0 };
rawData[12] = new double[] { 74.0, 170.0 };
rawData[13] = new double[] { 70.0, 210.0 };
rawData[14] = new double[] { 61.0, 110.0 };
rawData[15] = new double[] { 58.0, 100.0 };
rawData[16] = new double[] { 66.0, 230.0 };
rawData[17] = new double[] { 59.0, 120.0 };
rawData[18] = new double[] { 68.0, 210.0 };
rawData[19] = new double[] { 61.0, 130.0 };
Console.WriteLine("\nRaw data:\n");
ShowMatrix(rawData, rawData.Length, true);
int numAttributes = attributes.Length;
int numClusters = 3;
int maxCount = 30;
Console.WriteLine("\nk = " + numClusters + " and maxCount = " + maxCount);
int[] clustering = Cluster(rawData, numClusters, numAttributes, maxCount);
Console.WriteLine("\nClustering complete");
Console.WriteLine("\nClustering in internal format: \n");
ShowVector(clustering, true);
Console.WriteLine("\nClustered data:");
ShowClustering(rawData, numClusters, clustering, true);
double[] outlier = Outlier(rawData, clustering, numClusters, 0);
Console.WriteLine("Outlier for cluster 0 is:");
ShowVector(outlier, true);
Console.WriteLine("\nEnd demo\n");
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
} // Main
// 14 short static method definitions here
}
}
Pour plus de simplicité, j'ai utilisé une approche de méthode statique et j'ai supprimé la vérification des erreurs. La première partie du code de démonstration organise les données concernant de poids et de taille à mettre en clusters. Comme il n'y a que 20 tuples, j'ai codé en dur les données et je les ai stockées en mémoire dans un tableau intitulé rawData. Le plus souvent, vos données seront stockées dans un fichier texte ou un tableau SQL. Dans ce cas, vous devrez écrire une fonction d'aide afin de charger les données dans la mémoire. Si votre source de données est trop volumineuse pour tenir dans la mémoire de votre ordinateur, vous devrez modifier le code de démonstration pour qu'il passe par une source de données externe au lieu du tableau de données.
Une fois les données brutes configurées, le programme de démonstration appelle la fonction d'aide ShowMatrix afin d'afficher les données. Ensuite, les variables numAttributes, numClusters et maxCount reçoivent les valeurs de 2 (taille et poids), 3 et 30, respectivement. Souvenez-vous que maxCount limite le nombre d'itérations dans la boucle de traitement de l'algorithme principal. L'algorithme k-means tend à converger rapidement, mais vous devrez peut-être tester plusieurs valeurs de maxCount pour trouver la bonne.
Tout le travail clustering est effectué par la méthode Cluster. La méthode retourne un tableau d'entiers qui définit la façon dont chaque tuple est affecté à un cluster. Lorsque cela est terminé, le programme de démonstration affiche le clustering encodé, ainsi que les données brutes, regroupées par cluster.
Le programme de démonstration effectue pour finir l'analyse des données mises en cluster à la recherche de tuples isolés, voire anormaux, à l'aide de la méthode Outliers. Cette méthode accepte un identifiant de cluster et retourne les valeurs du tuple de données qui sont les plus éloignées (selon le calcul de la distance euclidienne) du centroïde du cluster (tuple le plus représentatif). Dans notre cas, dans le cluster 0, celui des personnes les plus lourdes, le tuple isolé est (67, 240), c.-à-d. la personne dont le poids est le plus élevé.
Calcul de centroïdes de cluster
Souvenez-vous : un centroïde de cluster est le tuple le plus représentatif des tuples affectés à un cluster ; une des façons possibles de définir le centroïde est de calculer la moyenne mathématique des tuples et de trouver le tuple qui est le plus proche de cette moyenne. La méthode d'aide UpdateMeans calcule la moyenne mathématique des tuples pour chaque cluster et est présentée dans la figure 4.
Figure 4 Méthode UpdateMeans
static void UpdateMeans(double[][] rawData, int[] clustering,
double[][] means)
{
int numClusters = means.Length;
for (int k = 0; k < means.Length; ++k)
for (int j = 0; j < means[k].Length; ++j)
means[k][j] = 0.0;
int[] clusterCounts = new int[numClusters];
for (int i = 0; i < rawData.Length; ++i)
{
int cluster = clustering[i];
++clusterCounts[cluster];
for (int j = 0; j < rawData[i].Length; ++j)
means[cluster][j] += rawData[i][j];
}
for (int k = 0; k < means.Length; ++k)
for (int j = 0; j < means[k].Length; ++j)
means[k][j] /= clusterCounts[k]; // danger
return;
}
La méthode UpdateMeans part du principe qu'un tableau de tableaux, intitulé moyennes (« means ») existe déjà, plutôt que créer un tableau et d'y retourner les données. Comme le tableau des moyennes (« means ») est supposé exister, il peut être utile d'en faire un paramètre ref. Le tableau des moyennes est créé à l'aide de la méthode d'aide Allocate :
static double[][] Allocate(int numClusters, int numAttributes)
{
double[][] result = new double[numClusters][];
for (int k = 0; k < numClusters; ++k)
result[k] = new double[numAttributes];
return result;
}
Le premier index du tableau des moyennes représente un identifiant de cluster et le second index indique l'attribut. Par exemple, si means[0][1] = 150,33, alors la moyenne des valeurs de poids (1) des tuples du cluster 0 est 150,33.
La méthode UpdateMeans commence par remettre à zéro toutes les valeurs du tableau des moyennes, puis passe par chaque tuple de données et compte les tuples dans chaque cluster, puis cumule les sommes de chaque attribut et la divise par le nombre de cluster approprié. Notez que la méthode renverra une exception si le nombre de clusters est 0. Il peut donc être intéressant d'ajouter une phase de contrôle des erreurs.
La méthode ComputeCentroid (représentée à la figure 5) détermine les valeurs centroïdes (valeurs de celui des tuples qui est le plus proche des valeurs du tuple moyen pour un cluster donné).
Figure 5 Méthode ComputeCentroid
static double[] ComputeCentroid(double[][] rawData, int[] clustering,
int cluster, double[][] means)
{
int numAttributes = means[0].Length;
double[] centroid = new double[numAttributes];
double minDist = double.MaxValue;
for (int i = 0; i < rawData.Length; ++i) // walk thru each data tuple
{
int c = clustering[i];
if (c != cluster) continue;
double currDist = Distance(rawData[i], means[cluster]);
if (currDist < minDist)
{
minDist = currDist;
for (int j = 0; j < centroid.Length; ++j)
centroid[j] = rawData[i][j];
}
}
return centroid;
}
La méthode ComputeCentroid passe par chaque tuple dans le jeu de données, en ignorant les tuples qui ne sont pas dans le cluster spécifié. Pour chaque tuple dans le cluster spécifié, la distance euclidienne entre le tuple et la moyenne du cluster est calculée à l'aide de la méthode d'aide Distance. Les valeurs de tuples qui sont les plus proches (dont la distance est la plus petite) des valeurs moyennes sont stockées et retournées.
La méthode UpdateCentroids appelle ComputeCentroid pour chaque cluster pour obtenir les centroïdes pour tous les clusters :
static void UpdateCentroids(double[][] rawData, int[] clustering,
double[][] means, double[][] centroids)
{
for (int k = 0; k < centroids.Length; ++k)
{
double[] centroid = ComputeCentroid(rawData, clustering, k, means);
centroids[k] = centroid;
}
}
La méthode UpdateCentroids part du principe qu'un tableau de tableaux appelé centroïdes existe. Le tableau des centroïdes est très semblable au tableau des moyennes : le premier index représente un identifiant de cluster et le second index indique l'attribut de données.
Pour récapituler, chaque cluster dispose d'un centroïde, qui est le tuple le plus représentatif du cluster. Les valeurs centroïdes sont calculées en recherchant le tuple de chaque cluster qui est le plus proche du tuple moyen (mean) de chaque cluster. Chaque tuple de données est affecté au cluster dont le centroïde est le plus proche du tuple.
Fonction Distance et normalisation des données
La méthode ComputeCentroid appelle une méthode Distance pour déterminer quel tuple de données est le plus proche de la moyenne du cluster. Comme décrit plus haut, la façon la plus répandue de mesurer la distance entre les tuples et les moyennes est d'utiliser la distance euclidienne :
static double Distance(double[] tuple, double[] vector)
{
double sumSquaredDiffs = 0.0;
for (int j = 0; j < tuple.Length; ++j)
sumSquaredDiffs += Math.Pow((tuple[j] - vector[j]), 2);
return Math.Sqrt(sumSquaredDiffs);
}
Il peut être utile de réfléchir à d'autres façons de définir la distance. Une option très courante est d'utiliser la somme des valeurs absolues des différences entre chaque composant. Comme la distance euclidienne met les différences au carré, les différences les plus grandes sont pondérées beaucoup plus fortement que les différences moins importantes.
Un autre facteur important en relation avec le choix de la fonction de distance dans l'algorithme de clustering k-means est la normalisation des données. Le programme de démonstration utilise des données brutes, non normalisées. Comme les valeurs de poids des tuples sont normalement des valeurs telles que 160, et que les hauteurs des tuples sont normalement des valeurs telles que 67, les différences de poids ont plus d'influence que les différences de taille. Dans de nombreuses situations, en plus d'explorer le clustering dans des données brutes, il est utile de normaliser les données brutes avant le clustering. Il existe de nombreuses façons de normaliser les données. La technique usuelle est de calculer la moyenne (m) et la déviation standard (sd) pour chaque attribut, puis de calculer pour chaque valeur d'attribut (v) une valeur normalisée : nv = (v-m)/sd.
Affectation de chaque tuple à un cluster
Dès lors que vous disposez d'une méthode pour calculer le centroïde de chaque cluster, il est possible d'écrire une méthode pour affecter chaque tuple à un cluster. La méthode Assign est présentée dans la figure 6.
Figure 6 Méthode Assign
static bool Assign(double[][] rawData,
nt[] clustering, double[][] centroids)
{
int numClusters = centroids.Length;
bool changed = false;
double[] distances = new double[numClusters];
for (int i = 0; i < rawData.Length; ++i)
{
for (int k = 0; k < numClusters; ++k)
distances[k] = Distance(rawData[i], centroids[k]);
int newCluster = MinIndex(distances);
if (newCluster != clustering[i])
{
changed = true;
clustering[i] = newCluster;
}
}
return changed;
}
La méthode Assign accepte un tableau de valeurs centroïdes et passe dans chaque tuple de données. La distance entre chaque tuple et chacun des centroïdes de cluster est calculée et stockée dans un tableau local appelé distances, dont l'index représente un identifiant de cluster. La méthode d'aide MinIndex identifie l'index du tableau des distances dont la valeur est la plus petite, ce qui correspond à l'identifiant de cluster du cluster dont le centroïde est le plus proche du tuple.
Voici la méthode d'aide MinIndex :
static int MinIndex(double[] distances)
{
int indexOfMin = 0;
double smallDist = distances[0];
for (int k = 0; k < distances.Length; ++k)
{
if (distances[k] < smallDist)
{
smallDist = distances[k]; indexOfMin = k;
}
}
return indexOfMin;
}
Dans la méthode Assign, si l'identifiant de cluster calculé est différent de l'identifiant de cluster existant stocké dans le tableau de clustering, ce dernier est mis à jour et un indicateur booléen signale qu'au moins un changement est à noter dans le clustering. L'indicateur servira à déterminer quand arrêter la boucle principale de l'algorithme (lorsque que le nombre maximum d'itérations est dépassé ou quand il n'y a plus de modifications du clustering).
Cette implémentation de l'algorithme k-means part du principe qu'il y a toujours au moins un tuple de données affecté à chaque cluster. Telle qu'elle est présentée dans la figure 6, la méthode Assign ne permet pas d'éviter qu'un cluster ne soit associé à aucun tuple. Dans la pratique, ceci n'est pas habituellement problématique. Empêcher cette condition d'erreur est un peu complexe. L'approche que j'utilise généralement consiste à créer un tableau appelé centroidIndexes utilisé en conjonction avec le tableau des centroïdes. Souvenez-vous que le tableau des centroïdes contient les valeurs centroïdes ; par exemple (61, 120) est le centroïde du cluster 2 dans la figure 2. Le tableau centroidIndexes contient l'index de tuple associé, par exemple [3]. Ensuite, dans la méthode Assign, la première étape consiste à affecter à chaque cluster le tuple de données qui contient les valeurs centroïdes, et ensuite seulement, à faire passer la méthode par chacun des tuples restants pour les affecter un par un à un cluster. Cette approche vous permet de vous assurer que chaque cluster est associé à au moins un tuple.
Méthode Cluster
La méthode Cluster, présentée dans la figure 7, est la routine (non détaillée) qui appelle les méthodes d'aide et d'aide de niveau inférieur afin d'effectuer le clustering des données.
Figure 7 Méthode Cluster
static int[] Cluster(double[][] rawData, int numClusters,
int numAttributes, int maxCount)
{
bool changed = true;
int ct = 0;
int numTuples = rawData.Length;
int[] clustering = InitClustering(numTuples, numClusters, 0);
double[][] means = Allocate(numClusters, numAttributes);
double[][] centroids = Allocate(numClusters, numAttributes);
UpdateMeans(rawData, clustering, means);
UpdateCentroids(rawData, clustering, means, centroids);
while (changed == true && ct < maxCount)
{
++ct;
changed = Assign(rawData, clustering, centroids);
UpdateMeans(rawData, clustering, means);
UpdateCentroids(rawData, clustering, means, centroids);
}
return clustering;
}
La boucle while principale affecte chaque tuple de données à un cluster, calcule le nouveau tuple moyen de chaque cluster, puis utilise la nouvelle moyenne pour calculer les nouvelles valeurs centroïdes de chaque cluster. La boucle s'arrête lorsqu'il n'y a plus de changements dans l'affectation des clusters ou si une limite maximale est atteinte. Comme le tableau des moyennes n'est utilisé que pour calculer les centroïdes, il peut être judicieux de refactoriser Cluster en plaçant l'appel de UpdateMeans à l'intérieur de la méthode UpdateCentroids.
Avant de lancer la boucle de traitement, le tableau de clustering est initialisé par la méthode InitClustering :
static int[] InitClustering(int numTuples,
int numClusters, int randomSeed)
{
Random random = new Random(randomSeed);
int[] clustering = new int[numTuples];
for (int i = 0; i < numClusters; ++i)
clustering[i] = i;
for (int i = numClusters; i < clustering.Length; ++i)
clustering[i] = random.Next(0, numClusters);
return clustering;
}
La méthode InitClustering commence par affecter les tuples de 0 à numClusters-1 aux clusters de 0 à numClusters-1 respectivement, afin que chaque cluster débute avec au moins un tuple affecté. Les tuples restants sont affectés à des clusters sélectionnés au hasard.
Un volume déconcertant de recherches a été mené sur l'initialisation du clustering k-means et vous souhaiterez peut-être tester vous-même d'autres approches que celle proposée ici. Dans de nombreux cas, le clustering final produit par l'algorithme k-means dépend de la façon dont le clustering est initialisé.
Rechercher des données anormales
Une façon possible d'utiliser le clustering de données est de simplement explorer différentes mises en cluster et de rechercher les résultats surprenants ou inattendus. Une autre solution est de rechercher des tuples de données inhabituels au sein d'un cluster. Le programme de démonstration vérifie le cluster 0 pour trouver le tuple de ce cluster qui est le plus éloigné du centroïde du cluster à l'aide de la méthode appelée Outlier, présentée dans la figure 8.
Figure 8 Méthode Outlier
static double[] Outlier(double[][] rawData, int[] clustering,
int numClusters, int cluster)
{
int numAttributes = rawData[0].Length;
double[] outlier = new double[numAttributes];
double maxDist = 0.0;
double[][] means = Allocate(numClusters, numAttributes);
double[][] centroids = Allocate(numClusters, numAttributes);
UpdateMeans(rawData, clustering, means);
UpdateCentroids(rawData, clustering, means, centroids);
for (int i = 0; i < rawData.Length; ++i)
{
int c = clustering[i];
if (c != cluster) continue;
double dist = Distance(rawData[i], centroids[cluster]);
if (dist > maxDist)
{
maxDist = dist;
Array.Copy(rawData[i], outlier, rawData[i].Length);
}
}
return outlier;
}
Après l'initialisation des tableaux des moyennes et des centroïdes, la méthode Outlier passe dans chaque tuple du cluster spécifié et calcule la distance euclidienne entre le tuple et le centroïde du cluster, puis retourne les valeurs du tuple les plus éloignées de celles du centroïde. Une alternative moins courante que vous pouvez envisager est de retourner l'index du tuple de données le plus éloigné.
Il y a de nombreuses autres façons d'analyser les données en cluster à la recherche d'anomalies. Par exemple, vous pourriez chercher à déterminer la distance moyenne entre chaque tuple et le centroïde du cluster dont il dépend ; ou encore les distances entre les différents centroïdes de clusters.
Routines d'affichage
Pour que vous ayez tous les éléments, voici des routines d'affichage simplifiées. Le code à télécharger comporte des versions un peu plus sophistiquées. Si vous utilisez ces routines simplifiées, vous devrez modifier leurs appels dans la méthode Main. Pour afficher les données brutes, les moyennes et les centroïdes, vous pouvez utiliser :
static void ShowMatrix(double[][] matrix)
{
for (int i = 0; i < numRows; ++i)
{
Console.Write("[" + i.ToString().PadLeft(2) + "] ");
for (int j = 0; j < matrix[i].Length; ++j)
Console.Write(matrix[i][j].ToString("F1") + " ");
Console.WriteLine("");
}
}
Pour afficher le tableau de clustering, vous pouvez utiliser :
static void ShowVector(int[] vector)
{
for (int i = 0; i < vector.Length; ++i)
Console.Write(vector[i] + " ");
Console.WriteLine("");
}
Pour afficher les valeurs d'un tuple isolé, vous pouvez utiliser :
static void ShowVector(double[] vector)
{
for (int i = 0; i < vector.Length; ++i)
Console.Write(vector[i].ToString("F1") + " ");
Console.WriteLine("");
}
Et pour afficher les données brutes regroupées par cluster, vous pouvez utiliser :
static void ShowClustering(double[][] rawData,
int numClusters, int[] clustering)
{
for (int k = 0; k < numClusters; ++k) // Each cluster
{
for (int i = 0; i < rawData.Length; ++i) // Each tuple
if (clustering[i] == k)
{
for (int j = 0; j < rawData[i].Length; ++j)
Console.Write(rawData[i][j].ToString("F1") + " ");
Console.WriteLine("");
}
Console.WriteLine("");
}
}
Pour résumer
Le clustering de données est étroitement lié à la classification des données. Et les deux sont parfois confondus. Le clustering est une technique sans supervision qui regroupe des éléments de données ensemble sans aucune notion préalable de ce que ces groupes peuvent être. Le clustering est, en général, un processus exploratoire. La classification, à l'inverse, est une technique supervisée qui requiert de spécifier des groupes connus via des données d'apprentissage, à la suite de quoi chaque de tuple de données est placé dans un de ces groupes existants. La classification est, en général, utilisée à des fins de prévision/prédiction.
Le code et les explications présentées dans cet article devraient vous apporter suffisamment d'informations pour commencer à tester le clustering k-means, ou pour créer un outil de clustering autonome, ou pour ajouter des fonctionnalités de clustering à une application .Net sans être dépendant de ressources externes. Il existe de nombreux autres algorithmes de clustering en dehors du k-means et je vous en présenterai quelques-uns dans des articles ultérieurs du magazine MSDN, y compris la réduction d'entropie des données, l'utilitaire de catégorie et l'inférence naïve bayésienne.
Le Dr. James McCaffrey travaille pour Volt Information Sciences Inc., où il gère la formation technique d'ingénieurs logiciels travaillant sur le Campus Microsoft à Redmond (État de Washington). Il a collaboré à plusieurs produits Microsoft, comme Internet Explorer et MSN Search. Il est l'auteur de « NET Test Automation Recipes » (Apress, 2006) et vous pouvez le contacter à l'adresse jammc@microsoft.com.
Merci à l'expert technique suivant d'avoir relu cet article : Darren Gehring