Sélection des modes initiaux pour la méthode Belief K-modes

Résumé du document

[...] Bien que la méthode K-Modes est considérée parmi les techniques de Clustering les plus répandues, cette méthode présente des limites majeures dans le cadre de l'incertain

[...] donner le nombre de clusters K à former.
2- choisir aléatoirement les K modes initiaux.
3- allouer chaque objet à son cluster approprié ayant le minimum de mesure de dissimilarité .
4- après que tous les objets ont été classifiés on calcule les modes des clusters formés .
5- recalculer la distance entre les objets et les modes obtenus.
6- réitérer les étapes 4 et 5 jusqu'à ce qu'aucun objet ne change plus de cluster. (...)

Extraits

[...] Simple matching comme mesure de dissimilarité. La fréquence pour mettre à jour le cluster mode. < number > < number > Cluster Mode: Chaque cluster est représenté par un mode. Le mode contient les attributs les plus fréquents des objets du cluster. Soit C={x1,x2,x3} X1=(c1,b1,d1) X2=(c1,b2,d1) X3=(c2,b2,d2) Le mode=(c1,b2,d1) < number > < number > La mesure de dissimilarité: Elle est définie comme étant la somme des distances entre les attributs de deux objets. Avec xi,j: la valeur de l'attribut j de l'objet i si x1j=x2j; 1 si x1j ≠x2j δ = < number > < number > L'algorithme(1) : séléctionner K modes initiaux aléatoirement. [...]

[...] On considère dans la suite l'attribut : Département = {finance(F), marketing(m), comptabilité(C)} Θ = représente l'ensemble des évènements élémentaires 2 Θ = représente tous les sous ensembles possibles dérivés de Θ(power set) < number > < number > Principe: Si une évidence sur des éléments du power set se présente alors on leur attribut des masses relatifs appartenant à 0.5 0.3 m{Θ}= 0.2 L'ignorance totale: M(Θ)=1 Avec A un singleton Dans le cas certain: M(Θ)=0 < number > < number > Bien que la méthode K-Modes est considérée parmi les techniques de Clustering les plus répandues, cette méthode présente des limites majeures dans le cadre de l'incertain. La solution est la méthode Belief K-Modes. Belief K-Modes Method < number > < number > Belief K-Modes Method Théorie des fonctions de croyance + K-Modes Method < number > < number > Cluster Mode: Soit un cluster X1 . [...]

[...] Plusieurs techniques ont été développés parmi les plus connues, la méthode K-mode. Est ce qu' on a toujours des informations aussi parfaites dans l'ensemble d'apprentissage? < number > < number > Introduction(2) Objets Qualification Salaire Département X1 A H F ou M ou C X2 B L F X3 C Av M ou C Exemple d'un ensemble d'apprentissage contenent des valeurs incertaines: < number > < number > Pour résoudre ce problème, une méthode de Clustering basée sur la théorie des fonctions de croyance est présentée. < number > < number > la principale contribution de cette méthode est de trouver une approche permettant : La construction des clusters quand les attributs de l'ensemble d'apprentissage peuvent être incertains. [...]

[...] à la fin on va obtenir: X1,X3,X4,X6 C1: X2,X5,X7 et C2: xi 0.4 0.3 ,mi(Θ)= 0.3 d(Xi,Q1)= 1.355 et d(Xi,Q2)= 0.3 X2,X5,X7,Xi Exemple < number > < number > Méthode de séléction des modes initiaux: Principe: cette méthode consiste à choisir des objets de l'ensemble d'apprentissage les plus distincts possibles afin d'aboutir à des meilleurs résultats. Maximiser la similarité intra-classes et minimiser la similarité inter-classes. < number > < number > Algorithme et exemple On choisit K=3. < number > < number > 1-Calculer la matrice de dissimilarité avec Di,j est la distance entre Xi et Xj. Allouer les deux objets fournissant la distance maximale aux deux premiers clusters. X2 X4 Algorithme < number > < number > Pour les autres objets calculer la somme de leur distances par rapport aux modes obtenus. [...]

[...] choisir aléatoirement les K modes initiaux. allouer chaque objet à son cluster approprié ayant le minimum de mesure de dissimilarité . après que tous les objets ont été classifiés on calcule les modes des clusters formés . recalculer la distance entre les objets et les modes obtenus. réitérer les étapes 4 et 5 jusqu'à ce qu'aucun objet ne change plus de cluster . < number > < number > Exemple choisir K=2 choisir aléatoirement les K modes initiaux : X1 } et X2 } < number > < number > on doit calculer les distances entre les objets {X3,X4,X5,X6,X7} et les 2 modes initiaux . [...]