k-modes est utilisé pour regrouper les variables catégorielles. Il définit les clusters en fonction du nombre de catégories correspondantes entre les points de données. (Ceci contraste avec l'algorithme k-means plus connu, qui regroupe des données numériques basées sur des mesures distantes comme la distance euclidienne, etc.) L'algorithme k-prototypes combine les k-modes et les k-means et est capable de regrouper des / données catégorielles.
Les fonctions objectives typiques du clustering formalisent l'objectif d'atteindre une similarité intra-cluster élevée (les documents au sein d'un cluster sont similaires) et une faible similitude inter-cluster (les documents provenant de différents clusters sont différents). Il s'agit d'un critère interne de qualité d'un clustering. Mais de bons scores sur un critère interne ne se traduisent pas nécessairement par une bonne efficacité dans une application. Une alternative aux critères internes est l'évaluation directe dans l'application de l'intérêt. Pour le clustering des résultats de recherche, nous souhaitons peut-être mesurer le temps nécessaire aux utilisateurs pour trouver une réponse avec différents algorithmes de clustering. Il s'agit de l'évaluation la plus directe, mais elle est coûteuse, surtout si de grandes études sur les utilisateurs sont nécessaires.
Types de technique de clustering catégorique
- Algorithme en mode k.
- k-prototypes
Pourquoi avons-nous besoin d'un algorithme en mode k?
Ralambondrainy (1995) a présenté une approche d'utilisation de l' algorithme k -means pour regrouper les données catégorielles. L'approche de Ralambondrainy est de convertir plusieurs attributs de catégorie en attributs binaires (en utilisant 0 et 1 pour représenter une catégorie absente ou présente) et de traiter les attributs binaires comme numériques dans l' algorithme k -means. Si elle est utilisée dans l'exploration de données, cette approche doit gérer un grand nombre d'attributs binaires car les ensembles de données dans l'exploration de données ont souvent des attributs catégoriels avec des centaines ou des milliers de catégories. Cela augmentera inévitablement les coûts de calcul et d'espace de l' algorithme k -means. L'autre inconvénient est que les moyennes de cluster, données par des valeurs réelles comprises entre 0 et 1, n'indiquent pas les caractéristiques des clusters.
Les données catégorielles ont une structure différente de celle des données numériques. Les fonctions de distance dans les données numériques peuvent ne pas être applicables aux données catégorielles. Les algorithmes de regroupement des données numériques ne peuvent pas être appliqués aux données catégorielles.
L'algorithme k-means est bien connu pour son efficacité dans le regroupement de grands ensembles de données. Cependant, travailler uniquement sur des valeurs numériques l'empêche d'être utilisé pour regrouper des données du monde réel contenant des valeurs catégorielles.
La raison pour laquelle l'algorithme k-means ne peut pas regrouper les objets catégoriels est sa mesure de dissimilarité. Ces barrières peuvent être supprimées en apportant les modifications suivantes à l'algorithme k-means:
- Utilisation d'une simple mesure de dissimilarité correspondante pour les objets catégoriels.
- Remplacement des moyens des clusters par des modes
- Utilisation d'une méthode basée sur la fréquence pour trouver les modes de résolution du problème.
A. Mesure de dissimilarité
L'algorithme de clustering est libre de choisir n'importe quel score de métrique / similarité de distance. Euclidienne est la plus populaire. Mais n'importe quelle autre métrique peut être utilisée qui évolue en fonction de la distribution des données dans chaque dimension / attribut, par exemple la métrique Mahalanobis.
Soit X , Y deux objets catégoriels décrits par m attributs catégoriels. La mesure de dissimilarité entre X et Y peut être définie par les non-concordances totales des catégories d'attributs correspondantes des deux objets. Plus le nombre de discordances est petit, plus les deux objets sont similaires. Cette mesure est souvent appelée appariement simple (Kaufman et Rousseeuw, 1990). Officiellement,
B. Mode d'un ensemble
Soit X un ensemble d'objets catégoriels décrits par des attributs catégoriels, A 1, A 2,. . . , Suis - je . Définition 1 . Un mode de X = { X 1, X 2,…, Xn } est un vecteur Q = [ q 1, q 2,…, qm ] qui minimise
C. Trouver un mode pour un ensemble
Le théorème 1 définit une manière de trouver Q à partir d'un X donné , et est donc important car il permet d' utiliser le paradigme k -means pour regrouper des données catégorielles. Le théorème implique que le mode d'un ensemble de données X n'est pas unique. Par exemple, le mode de l'ensemble {[a, b], [a, c], [c, b], [b, c]} peut être [a, b] ou [a, c].
D. L'algorithme k-modes
Lorsque (5) est utilisé comme mesure de dissimilarité pour les objets catégoriels, la fonction de coût (1) devient
Pour minimiser la fonction de coût, l' algorithme de base k -means peut être modifié en utilisant la simple mesure de dissimilarité de correspondance pour résoudre P 1, en utilisant des modes pour les clusters au lieu des moyennes et en sélectionnant des modes selon le théorème 1 pour résoudre P 2.
Dans l'algorithme de base, nous besoin de calculer le coût total P par rapport à l'ensemble de données à chaque fois qu'un nouveau Q ou W est obtenu. Pour rendre le calcul plus efficace, nous utilisons plutôt l'algorithme suivant dans la pratique.
1. Sélectionnez k modes initiaux, un pour chaque cluster.
2. Allouez un objet au cluster dont le mode est le plus proche selon (5). Mettre à jour le mode du cluster après chaque allocation selon le théorème 1.
3. Une fois que tous les objets ont été attribués aux clusters, testez à nouveau la dissemblance des objets par rapport aux modes actuels. Si un objet est trouvé de telle sorte que son mode le plus proche appartient à un autre cluster plutôt que son mode actuel, réattribuez l'objet à ce cluster et mettez à jour les modes des deux clusters.
4. Répétez 3 jusqu'à ce qu'aucun objet n'ait changé de clusters après un test de cycle complet de l'ensemble de données.
La preuve de convergence de cet algorithme n'est pas encore disponible (Anderberg, 1973). Cependant, son utilisation pratique a montré qu'elle converge toujours.
Comme l' algorithme k -means, l'algorithme k -modes produit également des solutions localement optimales qui dépendent des modes initiaux et de l'ordre des objets dans l'ensemble de données. Dans notre implémentation actuelle de l' algorithme k -modes, nous incluons deux méthodes de sélection de mode initial. La première méthode sélectionne les k premiers enregistrements distincts de l'ensemble de données en tant que k modes initiaux .
La deuxième méthode est mise en œuvre avec les étapes suivantes.
- Calculez les fréquences de toutes les catégories pour tous les attributs et stockez-les dans un tableau de catégories par ordre décroissant de fréquence comme indiqué sur la figure 1. Ici, ci , j désigne la catégorie i de l'attribut j et f ( ci , j ) ≥ f ( ci + 1, j ) où f ( ci , j ) est la fréquence de la catégorie ci , j .
- Attribuez les catégories les plus fréquentes de manière égale aux k modes initiaux . Par exemple dans la figure 1, supposons k = 3. Nous affectons Q 1 = [ q 1,1 = c 1,1, q 1,2 = c 2,2, q 1,3 = c 3,3, q 1, 4 = c 1,4],
L'étape 3 est prise pour éviter l'apparition de clusters vides. Le but de cette méthode de sélection est de rendre les modes initiaux diversifiés, ce qui peut conduire à de meilleurs résultats de clustering
Il est simple d'intégrer les algorithmes k -means et k -modes dans l' algorithme k -prototypes qui est utilisé pour regrouper les objets de type mixte. L' algorithme k -prototypes est pratiquement plus utile car les objets fréquemment rencontrés dans les bases de données du monde réel sont des objets de type mixte.
où le premier terme est la mesure de distance euclidienne au carré sur les attributs numériques et le second terme est la mesure de dissimilarité de correspondance simple sur les attributs catégoriels. Le poids γ est utilisé pour éviter de privilégier l'un ou l'autre type d'attribut. L'influence de γ dans le processus de clustering est discutée dans (Huang, 1997a)
Implémentation du mode k
Les implémentations Python des algorithmes de clustering k-modes et k-prototypes reposent sur Numpy pour une grande partie du travail lourd et il existe une bibliothèque python pour faire exactement la même chose.
https://github.com/nicodv/kmodes
Conclusion
Les deux algorithmes sont efficaces lors du regroupement de très grands ensembles de données complexes en termes à la fois du nombre d'enregistrements et du nombre de clusters.
En général, l' algorithme k -modes est beaucoup plus rapide que l' algorithme k -prototypes. La raison principale est que l' algorithme k- modes a besoin de beaucoup moins d'itérations pour converger que l' algorithme k- prototypes en raison de sa nature discrète.
Choses à explorer:
Il existe un certain nombre d'algorithmes de clustering qui peuvent gérer de manière appropriée des types de données mixtes. Certaines possibilités comprennent les suivantes:
- Algorithmes basés sur le partitionnement: k-Prototypes, Squeezer.
- Algorithmes hiérarchiques: ROCK, liaison agglomérative simple, moyenne et complète.
- Algorithmes basés sur la densité: HIERDENC, MULIC , CLIQUE.
- Algorithmes basés sur des modèles: clustering SVM, cartes auto-organisées.
Références
[1] https://www.ijert.org/research/review-paper-on-data-clustering-of-categorical-data-IJERTV1IS10372.pdf
[2] http://www.cs.ust.hk/~qyang/Teaching/537/Papers/huang98extensions.pdf
[3] https://arxiv.org/ftp/cs/papers/0603/0603120.pdf
[4] https://www.ee.columbia.edu/~wa2171/MULIC/AndreopoulosPAKDD2007.pdf
[5] https://datascience.stackexchange.com/questions/22/k-means-clustering-for-mixed-numeric-and-categorical-data
