J'ai pensé à écrire un article de blog sur cette intéressante analyse de Kleinberg (2002) qui explore la difficulté du clustering. Kleinberg décrit trois desiderata apparemment intuitifs pour une fonction de clustering et prouve ensuite qu'aucune fonction de ce type n'existe. Il existe de nombreux algorithmes de clustering qui satisfont deux des trois critères; cependant, aucune fonction ne peut satisfaire les trois simultanément.

Brièvement et officieusement, les trois desiderata qu'il décrit sont:

• Scale-Invariance : Si nous transformons les données de manière à ce que tout soit étalé de manière égale dans toutes les directions, le résultat du clustering ne devrait pas changer.
• Cohérence : si nous étirons les données de sorte que les distances entre les clusters augmentent et / ou les distances au sein des clusters diminuent, le résultat du clustering ne devrait pas changer.
• Richesse : La fonction de clustering devrait théoriquement être capable de produire n'importe quelle partition / clustering arbitraire de points de données (en l'absence de connaître la distance par paire entre deux points quelconques)

Des questions:

(1) Y a-t-il une bonne intuition, une image géométrique qui peut montrer l'incohérence entre ces trois critères?

(2) Il s'agit des détails techniques du document. Vous devrez lire le lien ci-dessus pour comprendre cette partie de la question.

Dans l'article, la preuve du théorème 3.1 est un peu difficile à suivre pour moi. Je suis coincé: "Soit une fonction de clustering qui satisfait la cohérence. Nous affirmons que pour toute partition Γ ∈ Range ( f ) , il existe des nombres réels positifs a < b tels que la paire ( a , b ) est Γ - forçant. "$f$$\Gamma \in \text{Range}(f)$$a < b$$(a, b)$$\Gamma$

Je ne vois pas comment cela peut être le cas ... La partition ci-dessous n'est-elle pas un contre-exemple où (c'est-à-dire que la distance minimale entre les clusters est supérieure à la distance maximale au sein des clusters)?$a > b$

Edit: ce n'est clairement pas un contre-exemple, je m'embrouillais (voir réponses).

• Ackerman et Ben-David (2009). Mesures de la qualité du clustering: un ensemble de travail d'axiomes pour le clustering
  • Souligne quelques problèmes avec l'axiome de "cohérence"

D'une manière ou d'une autre, chaque algorithme de clustering repose sur une certaine notion de «proximité» des points. Il semble intuitivement clair que vous pouvez utiliser une notion relative (invariante d'échelle) ou une notion absolue (cohérente) de proximité, mais pas les deux .

Je vais d'abord essayer d'illustrer cela avec un exemple, puis je dirai comment cette intuition correspond au théorème de Kleinberg.

Un exemple illustratif

Supposons que nous ayons deux ensembles et S 2 de 270 points chacun, disposés dans le plan comme ceci:$S_1$$S_2$$270$

$\hskip{6em}$

Vous ne verrez peut-être pas points dans l'une de ces images, mais c'est simplement parce que beaucoup de points sont très proches les uns des autres. Nous voyons plus de points lorsque nous zoomons:$270$

$\hskip{3em}$

Vous serez probablement spontanément d'accord pour dire que, dans les deux ensembles de données, les points sont disposés en trois groupes. Cependant, il s'avère que si vous zoomez sur l'un des trois groupes de , vous voyez ce qui suit:$S_2$

$\hskip{3em}$

Si vous croyez à une notion absolue de proximité, ou à la cohérence, vous maintiendrez toujours que, indépendamment de ce que vous venez de voir au microscope, compose de seulement trois grappes. En effet, la seule différence entre S 1 et S 2 est que, au sein de chaque cluster, certains points sont désormais plus rapprochés. Si, par contre, vous croyez à une notion relative de proximité, ou à l'invariance d'échelle, vous aurez tendance à soutenir que S 2 n'est pas composé de 3 mais de 3 × 3 = 9 clusters. Aucun de ces points de vue n'est faux, mais vous devez faire un choix dans un sens ou dans l'autre.$S_2$$S_1$$S_2$$S_2$$3$$3×3 = 9$

Un cas pour l'invariance isométrique

Si vous comparez l'intuition ci-dessus avec le théorème de Kleinberg, vous constaterez qu'ils sont légèrement en désaccord. En effet, le théorème de Kleinberg semble dire que vous pouvez obtenir simultanément l'invariance et la cohérence d'échelle tant que vous ne vous souciez pas d'une troisième propriété appelée richesse. Cependant, la richesse n'est pas la seule propriété que vous perdez si vous insistez simultanément sur l'invariance et la cohérence de l'échelle. Vous perdez également une autre propriété, plus fondamentale: l'isométrie-invariance. C'est une propriété que je ne serais pas prêt à sacrifier. Comme il n'apparaît pas dans l'article de Kleinberg, je m'y attarderai un instant.

En bref, un algorithme de clustering est invariant en isométrie si sa sortie ne dépend que des distances entre les points, et non de certaines informations supplémentaires comme des étiquettes que vous attachez à vos points, ou d'un ordre que vous imposez à vos points. J'espère que cela ressemble à une condition très douce et très naturelle. Tous les algorithmes discutés dans l'article de Kleinberg sont invariants en isométrie, à l'exception de l'algorithme de liaison unique avec la condition d'arrêt cluster. Selon la description de Kleinberg, cet algorithme utilise un ordre lexicographique des points, donc sa sortie peut en effet dépendre de la façon dont vous les étiquetez. Par exemple, pour un ensemble de trois points équidistants, la sortie de l'algorithme de liaison unique avec le $k$$2$-la condition d'arrêt de la grappe donnera des réponses différentes selon que vous étiquetez vos trois points comme "chat", "chien", "souris" (c <d <m) ou comme "Tom", "Spike", "Jerry" (J <S <T):

$\hskip{6em}$

Ce comportement contre nature peut bien sûr être facilement réparé en remplaçant la condition d'arrêt de la grappe par une «condition d'arrêt de la grappe ( ≤ k ) ». L'idée est simplement de ne pas rompre les liens entre les points équidistants et d'arrêter de fusionner les clusters dès que nous avons atteint au plus k clusters. Cet algorithme réparé produira toujours $k$$(≤ k)$ $k$$k$ grappes la plupart du temps, et il sera invariant en isométrie et invariant en échelle. En accord avec l'intuition donnée ci-dessus, elle ne sera cependant plus cohérente.

$S$$S$$S$

$Γ$$d$$d'$$i$$i(x)$$i(y)$$Γ(d')$$x$$y$$Γ(d)$

$S$$S$$S$

$\hskip{6em}$

Une variante du théorème de Kleinberg

L'intuition donnée ci-dessus est capturée par la variante suivante du théorème de Kleinberg.

Théorème: Il n'y a pas d'algorithme de regroupement non trivial à invariance isométrique qui soit à la fois cohérent et invariant à l'échelle.

Ici, par un algorithme de clustering trivial , je veux dire l'un des deux algorithmes suivants:

1. $S$

2. $S$

L'affirmation est que ces algorithmes stupides sont les deux seuls algorithmes invariants d'isométrie qui sont à la fois cohérents et invariants à l'échelle.

$S$$Γ$$d₁$$S$$d₁(x,y) = 1$$x ≠ y$$S$$Γ$$Γ(d₁)$$Γ(d₁)$$Γ(d₁)$$Γ(d₁)$$d$$S$$≥ 1$$d$$Γ(d) = Γ(d₁)$$Γ$$Γ(d₁)$$d$$S$$≤ 1$$Γ(d)=Γ(d₁)$$Γ$

Bien sûr, cette preuve est très proche dans l'esprit de la preuve de Margareta Ackerman du théorème original de Kleinberg, discutée dans la réponse d'Alex Williams.

C'est l'intuition que j'ai trouvée (un extrait de mon blog ici ).

$d_1$$d_2$$d_3$$d_2$$d_3$$d_1$$d_1 \rightarrow d_3$$d_2 \rightarrow d_3$