Partitionnement  

 

 

Pour un ensemble, X = {x1, x2, …xn}, on a une n ´ n matrice des dissimilarité, A = [aij]. Ici, on présume que A est symétrique, soit pour ignorer soit pour mettre à zéro la diagonale. On remarque que le partitionnement peut être éxécuté sur ces objets se rapportant à une matrice assymétrique, bien que la méthode est quelque peu différente. La supposition de symétrie est raisonable si les dissimilarités sont des distances qui requérient D(x, y) = D(y, x). L’ensemble des toutes les partitions possibles de X se séparés en K classes est défini comme PK. Classe Ck contienit nk objects.On distingue les dissimilarités internes (intra-classes) des dissimilarités externes (inter-classes).

 

Le diamétre d’une classe, Ck, est égal à la plus grande dissimilarité intra-classe.

d( Ck) = max(aij: xi, xj Î Ck)

Le diamétre d’une partition, p, est égal au plus grand des diamétres de ses classes.

D(p) =

 

Les conditions pour une partition d’un ensemble:

(i)                  Ci ¹ Æ ou, tout la même, ni ¹ 0, " 1 £ i £ K (non-vide classes)

(ii)                Ci Ç Cj =  Æ, " 1 £ i < j £ K (l’une classe ne chevauche pas l’autre)

(iii)                (les classes couvrent l’ensemble)

 

Pendant on contruit une partition, on cherche à vérifier les critéres de classification. Il y a trois familles de classification:

(i)                 Séparation      (écarts inter-classes)

On propose B = {aij: xi Î Ck, xj Î X/Ck} comme l’ensemble des dissimilarités inter-classes. Appelons-le Cocycle. (Remarque: Pour mieux utilises lq symétrie, ici et partout dans les critéres de séparation, i = 1,…n - 1 et j = i + 1, …n.)

(*)  Pour maximiser la dissimilarité minimum inter-classes

(*) Pour maximiser la somme des dissimilarité inter-classes

On peut mettre (élever) au carré les valeurs des dissimilarités.

(*) Pour maximiser la moyenne des dissimilarité inter-classes

On peut mettre (élever) au carré les valeurs des dissimilarités. Ce critére tend à séparer les objets loins de tous les autres objets reculés devienent des singletons et produisent souvent des classes très déséquilibrées.

 (*)Pour maximiser la somme des plus petites dissimilarité aux autres classes

Remarque: Si xi Î Ck, alors min(aij: xj Î Ck) = 0. Puis, si B exploite la symétrie dans A, alors l’équation finale devient .


 

(ii)               Homogénéité

Quand on minimise le maximum des dissimilarités [pairwise] intra-classes, on crée généralement des classes aux objets similaires ou proches des autres, c’est-à-dire on tend à créer des classes homogénés

 (*) Pour mimiser le maximum des diamétres intra-classes, c’est-à-dire pour minimiser le diamétre de la partition: .

(*)  Pour minimiser la somme des disimilarités intra-classes:

.

(*)  Pour minimiser la somme des sommes standardisées des disimilarités intra-classes:

.

(*)  Pour minimiser la somme des sommes standardisées des disimilarités intra-classes (méthode alternée):
.

D’autres méthodes pour standardiser des sommes se trouvent dans Hubert, Arabie, et Meulman (2001).

 

(iii)             Dispersion

Ici, on minimise une fonction d’inertie, les “distances” de chaque objet au centre (réel ou virtuel) de sa classe. Le centre réel est un objet dans la classe, d’habitude déterminé par sa médiane (l’objet dont la somme des distances aux autres est minimum). Un centre virtuel n’est nécessairement pas un objet dans sa classe (assigné à sa classe).

(*) Pour minimiser la somme des inerties par rapport  au centre réel de chaque classe:

 

(*) Pour minimiser la somme des inerties par rapport  au centre virtuel de chaque clasee:

     (distances d’arbre; moindre carrés)

(*) Pour minimiser la somme des inerties moyennes par rapport  au centre virtuel de chaque classe:

 , pour chaque classe, Ck (k = 1,…K), on calcule

 

Maintenant, nous avons le choix entre onze critéres; nous devons donc avoir des indices de qualité pour évaluer les classes et des indices de qualité pour évaluer la partition. Guénoche (2003) a recommandé la somme des carrés (séparation) et l’inertie par la moyenne.

 

(i)                  Indices de qualité des classes

Une classe, Ck, est d’autant meilluere qu’elle a:

(*) un seuil de connexité petit

Chaque objet, xi Î Ck, a un voisin plus proche, xj Î Ck, à dissimilarité aij. Ce seuil est

(*) un diamétre (dk) faible par rapport à D(p) et pas trop grand comparé à sk:

(*) un taux des dissimilarités intra-classe £ sk élevé, voisin de 50%

lk = |{ aij £ sk : xi, xj Î Ck, i < j}|

lT = |{ aij : xi, xj Î Ck, i < j}| = nk(nk – 1)/2

t(l) = lk / lT  = 2 * lk / nk(nk – 1)

(*) une clique qui contient une forte proportion des objets de la classe

(??? See other paper?)

(*) un taux des triplets bien représentés supérieur à 50%

tk = |{ aij £ min(aiu, auj ) : xi, xj Î Ck, xu Î X/Ck}|

tT = |{( xi, xj, xu) : xi, xj Î Ck, xu Î X/Ck} = nk(nk – 1)(nnk)/2

t(t) = tk / tT  = 2 * tk / nk(nk – 1)(nnk)

(ii)                Indices de qualité de la partition

Il est désirable d’avoir quelque mesure de la maniére dont une partition maximise la séparation (écart entre) des classes. D’abord, on calcule le nombre des dissmilarités externes, ; et le nombre des dissimilarités internes, . Puis, on fait la liste des toutes des dissimilarités dans le triangle supérieur de la matrice, A, en ordre-décroissant. On définit le seuil, s; comme le neth valeur en ligne. L’idée est que les dissimilarités externes (Le = {aij :  $ Ck ' xi Î Ck, xj Ï Ck}) sont les ne valeurs (Gd) supérieures ou égales au seuil. Pareillement, les dissimilarités internes (Li = {aij : $  Ck  ' xi, xj Î Ck}) sont les ni valeurs (Pd) inférieures du seuil. On propose s’ égal à la plus grande valeur strictement inférieure à s.

(*) Taux de concordance

C’est le pourcentage de paires concordantes, c’est-à-dire des grandes (petites) distances qui sont des dissimilarités externes (internes).

Haute = {aij ³ s : $ Ck ' xi Î Ck, xj Ï Ck}

Bas = {aij £ s’: $  Ck  ' xi, xj Î Ck}

t(c) = 1 – 2*|Haute È Bas|/n(n – 1)

(*) Le taux des poids

(*) Quotient des longueurs moyennes

(*) Taux des triplets bien représentés

,

t(t) = t / T.

.:: Français, S'il Vous Plait : Objets en Suite ::.