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:
où
(*)
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:
où,
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)(n – nk)/2
t(t) = tk / tT =
2 * tk / nk(nk – 1)(n – nk)
(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 ::.