Discussion :

[davcha]

Bonjour,

Une partition est l'assignation d'un ensemble de points x_1,...,x_n à un ensemble de cluster c_1,...,c_k.
On peut représenter cette partition de diverses manières.
Comme un vecteur : [1,1,2,2,3,3]^t
Comme une matrice :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
1,0,0
1,0,0
0,1,0
0,1,0
0,0,1
0,0,1

Deux partitions A et B sont égales si pour chaque paire de points i et j appartenant au même cluster dans A appartiennent au même cluster dans B.

Si on représente A et B sous forme de matrice, on a donc : |AA^t - BB^t|=0 iff A=B

Ce qui m'intéresse est le nombre de points classés différemment entre A et B. Je définis ça comme étant le nombre minimal de transformations à appliquer à B pour obtenir A.

Des idées ? J'aimerais bien si possible quelque chose d'assez "simple"... Pas d'opti combinatoire par exemple.
J'ai l'intuition que c'est vraiment tout con, mais je sèche.

Merci

[souviron34]

J'ai comme l'impression que tes 2 représentations sont fausses..

Si un point peut appartenir à A et B (ce que j'ai l'impression de comprendre dans ton texte), alors d'une part on ne peut pas le représenter comme un vecteur, et d''autre part ta matrice ne peut pas avoir jutse un seul 1 par ligne..

Me trompe-je ?


OK. Je comprend : là tu présentes UNE partition...

Tu as donc soit 2 vecteurs soit 2 matrices...

A priori j'aurais tendance à penser que la réprésentation vectorielle sera plus aisée à manipuler..

Dans ce cas, le nombre de points classés différemment est assez immédiat, non ??


EDIT :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
N = 0
T1 = taille(Vecteur1)
T2 = taille(Vecteur2)
 
pour i = 0 jusqu'à min(T1,T2) 
    si Vecteur1(i) différent de Vecteur2(i)
        N = N + 1
    fin si
fin pour
 
N = N +  (max(T1,T2) -  min(T1,T2)

[davcha]

Je ne représentais qu'une partition, en effet. Par contre, ce n'est pas si immédiat que ça :

Ces deux partitions sont équivalentes :
A=[1,1,2,2,3,3]
B=[2,2,3,3,1,1]

La distance entre ces deux partitions est de 1 :
C=[1,1,2,2,3,3]
D=[2,2,3,3,3,1]

A noter que le nombre de points d'une partition à une autre reste le même.

[souviron34]

ok, donc ça se précise.. Tu veux la distance...

C'était plas clair :

Ce qui m'intéresse est le nombre de points classés différemment entre A et B. i

Avec ça, A et B de ton exemple sont différents...

Mais alors, la solution (si j'ai compris) est assez simple : il faut comparer le nombre de points attribués à chaque cluster...

Dans ton exemple (A,B), on a le même nombre, donc A=B

Dans le second, (C,D), il y a 1 point de plus pour 3, donc dist=1



Me trompe-je ?

Il suffit alors de faire une liste (ou un tableau) du nbe de points par cluster.. (un histogramme)

A : 1 -> 2, 2 -> 2, 3 -> 2
B : 1 -> 2, 2 -> 2, 3 -> 2

nbe min A,B = 2, nbe max A,B = 2, => delta = 0


C ; 1 -> 2, 2 -> 2, 3 -> 2
D : 1 -> 1, 2 -> 2, 3 -> 3

nbe min C = 2, nbe max C = 2
nbe min D = 1, nbe max D = 3

delta = nb max D - nb max C = 1

[davcha]

Me trompe-je ?

En effet, tu te trompes.

A=[1,1,2,2,3,3]
B=[1,2,2,3,1,3]

Le cardinal de chaque cluster est le même dans les deux cas, pourtant A et B sont des partitions différentes. Et la distance entre A et B est 3.

[souviron34]

Et la distance entre A et B est 3.

moi je trouve 1...

mais ce serait mieux si on savait ce que tu appelles une distance

[davcha]

Tu considères deux vecteurs A et B.

Par exemple :

A=[1,1,2,2,3,3]
B=[1,2,2,3,1,3]

La distance entre A et B est le nombre d'entrées que tu dois supprimer des deux vecteurs de façon à ce qu'ils soient identiques. Sachant évidemment que si tu supprimes la ième entrée de A tu supprimes la ième entrée de B.

Si tu préfères, tu peux voir A et B comme une matrice 2x6.
La distance entre A et B est le nombre de colonnes de cette matrice que tu dois supprimer de façon à ce que A et B soient identiques.

On peut permuter les numéros, cela reste identique. Par exemple [1,1,2,3] est identique à [2,2,3,1].

[souviron34]

La distance entre A et B est le nombre d'entrées que tu dois supprimer des deux vecteurs de façon à ce qu'ils soient identiques.

Tu fais bien de préciser, parce que ce n'est pas la notion généralement admise de "distance"

Mais avec cette hypothèse :

On peut permuter les numéros, cela reste identique

Cela me semble insoluble...