Weighted kernel k-means et normalized cut

Bonjour,

J'aimerais attirer votre attention sur les sections 4.1 et 4.2 (normalized cut) de ce document : http://www.cse.ohio-state.edu/~kulis...techreport.pdf

Les parties que je tiens à souligner sont celles qui définissent l'objectif de weighted kernel k-means comme étant : \max_Ytrace(Y^TW^{1/2}KW^{1/2}Y)
et la définition d'un kernel K = D^{-1}AD^{-1} puis d'un kernel K' = \sigmaD^{-1}+D^{-1}AD^{-1}

où W est une matrice diagonale de poids, D la matrice diagonale des degrés d'un graphe dont A est la matrice d'adjacence.

La section 4.4 du document est intéressante également, c'est là que se situe mon problème.

Tout semble correct, mais je suis incapable de reproduire ses expériences : soit weighted kernel k-means ne converge pas, soit il converge vers une solution vraiment pas satisfaisante du tout.


Globalement, pour résumer tout ça, Kulis démontre que :
- la fonction objectif de weighted kernel k-means correspond à la maximisation de la trace donnée plus haut
- on peut définir un "kernel" K (tel que définit plus haut) qui correspond à l'objectif du normalized cut. Mais ce "kernel" n'en est pas un, car il n'est pas semi-défini positif.
Il propose alors de modifier K en ajoutant des choses dans la diagonale (K') de façon à rendre la matrice semi-définie positive. On a donc un kernel (condition nécessaire pour la convergence de k-means).

Il expérimente alors là-dessus, et constate qu'ajouter des valeurs positives dans la diagonale a un effet pervers : n'importe quel partitionnement des points devient un minimum local, donc on "converge" immédiatement. Les résultats sont donc très aléatoires (et très vilains).

Il propose alors de "voir ce que ça donne" quand on réduit les valeurs dans la diagonale (un \sigma négatif, il propose -1). Cela transforme le "kernel" K' en une matrice indéfinie, donc ce n'est plus un kernel et k-means n'est plus garanti de converger.
Il refait ses tests et annonce qu'il a de très bons résultats (très surprenant, je trouve).
Pour ma part, j'ai des résultats très médiocres, parfois k-means ne converge même pas (pas surprenant).

Merci