Discussion :

[souviron34]

Si ce n'est de manière directe, peut-être par analogie avec un autre algorithme: divide & conquer, dichotomie, ... ?

En fait, la philosophie de base est bien Divide & Conquer

Est-ce que je pourrais m'appuyer sur d'un côté ça, et de l'autre les 2 graphiques fN)-log(N) et log ( f(N)/N)- log(N) , pour être affirmatif ?

[davcha]

Ni l'un ni l'autre.. Il fait du "contouring", mais le plus réaliste possible, c'est à dire correspondant à la perception visuelle qu'on a du nuage..

Si je posais ces questions, c'est que vu la vitesse, simplicité du code, et expression de la complexité, j'aimerais terminer en conclusion par le fait que cela pourrrait facilement être appliqué dans ces domaines.

Mais tu ne détectes donc que les contours d'un nuage de points qui provient d'un cluster unique, donc sans overlaps, exact ?

[souviron34]

Mais tu ne détectes donc que les contours d'un nuage de points qui provient d'un cluster unique, donc sans overlaps, exact ?

non pas forcément d'un cluster unique.. (les grands nombres de points de tests dans les graphiques ci-dessus sont justement sur l'ensemble des points pris en totalité, mais ces points étant répartis en clusters différents). Disons que cet algo les considère comme un cluster unique. Maintenant, on pourrait s'en servir de base..

D'ailleurs, c'est aussi justement une des applis qui pourrait se faire.. J'ai pensé à quelques critères (longueur relative des segments voisins par exemple, ou "paralélisme" + longueurl).. Je n'ai ni le courage ni le temps de me pencher dessus, mais c'est une piste de recherche que je compte mentionner à la fin..

Si obtenir le contour global visuellement précis d'un amas de clusters peut se faire en O(m log(N)) (facteur dominant), alors par exemple le test des longueurs relatives, ou tout autre critère déterministe de séparation, peut se faire en O(m)...

Ce qui ramènerait une clusterisation en O ( m log(N) )...

[davcha]

Je suis bien curieux de voir ton algo, souviron.

(Je fais de la recherche dans clustering)

[souviron34]

Je suis bien curieux de voir ton algo, souviron.

(Je fais de la recherche dans clustering)

ces points de calcul de complexité sont les derniers points à régler avant le dépôt de l'article.. J'espère d'ici 2 semaines..

Puisque tu fais de la recherche dans le clutering, quels sont les meilleurs algos ( je veux dire complexité - simplicité - mémoire ) ?


Note : par contre, c'est un algo empirique, avec des valeurs numériques, ce qui risque de choquer les puristes et théoriciens. Mais qui moi, en tant que physicien, ne me choque pas du tout

[pseudocode]

En fait, la philosophie de base est bien Divide & Conquer

Est-ce que je pourrais m'appuyer sur d'un côté ça, et de l'autre les 2 graphiques fN)-log(N) et log ( f(N)/N)- log(N) , pour être affirmatif ?

La stratégie "divide and conquer" transforme un problème de taille N en "a" problèmes de taille N/b. Ce qui permet d'écrire une relation de récurrence sur la taille du problème (et donc sa complexité):

T(N) = a.T(N/b) + f(N)
T(1) = 1

f(N) représente le coût du "divide" et a.T(N/b) représente le coût du "conquer" sur les problèmes restants.

Lorsque "a" et "b" sont sensiblement égaux (le problème se divise en parties égales non couvrantes) et d(N) est linéaire, alors on a une complexité de type O(n.log(n)). C'est le cas habituel du "divide and conquer".

Si tes hypothèses sur a,b,f() sont différentes, il faut calculer la complexité. Les démonstrations sont dispo sur le net.

[souviron34]

Je ne comprend pas trop... je n'ai pas d'hypothèses sur a et b.. Juste des constatations et intuitions..

Soit un ensemble de N points

Soit une enveloppe de ces points, comprenant m points.

Je suppose que diviser N par le segment de l'enveloppe est donc en N / (m/2).
(une enveloppe est par définition enveloppante, donc à chaque point j'ai "à peu près" son symétrique)

Mon b serait donc m/2

Maintenant, si j'ajoute 1 point entre 2 sommets, je divise en moyenne l'intervalle par 2. Donc pour un segment pour lequel j'explore N/(m/2) points, je crée 2 segments pour lesquels récursivement je vais explorer 1/2 (N/(m/2)) points.

Qu''est-ce que je dois en déduire ??

En fait, c'est pas plutôt une dichotomie ?

[pseudocode]

Qu''est-ce que je dois en déduire ??

D'après ce que je comprend, en considérant "m" comme une constante pour l'instant,

Je suppose que diviser N par le segment de l'enveloppe est donc en N / (m/2)

f() linéaire par rapport a N

Maintenant, si j'ajoute 1 point entre 2 sommets, je divise en moyenne l'intervalle par 2. Donc pour un segment pour lequel j'explore N/(m/2) points, je crée 2 segments pour lesquels récursivement je vais explorer 1/2 (N/(m/2)) points.

a = b = 2.

T(N) = 2*T(N/2) + N = O(N.log(N))

En fait, c'est pas plutôt une dichotomie ?

Si tu dois refaire l'étape de division à chaque appel récursif, c'est du D&C.

[souviron34]

qu'est-ce que tu appelles "étape de division" ??

Je me contente d'utiliser les bornes du segment... O(1).

Puis j'explore entre ces bornes.. le nombre exploré est le fameux facteur N/m ..

[pseudocode]

hum... bon visiblement ce n'est donc pas du D&C.

Reprenons du début.

Code :

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

1
2
for ( i = 0 ; i < m ; i++ )
  for ( j = 0 ; j < f(N) ; j++ )

m est le nombre de pts de l'enveloppe
f est le nbe de pts explorés pour 1 pt i

L'algo est donc en O(m.f(N)).

Tout le problème est de caractériser f(N), qui dépend donc de N.

Les graphes de mesure de f(N) font penser que Log(f(N)) = a*Log(N) + b f(N) = k.N^a

Pour être plus rigoureux sur cette formulation, il faut soit arriver a formaliser les opérations effectuées par f() (formule directe ou récurrente), soit montrer que f() est équivalent à un algo connu.

Si on part sur du "f(N) = N^a + cste", ca voudrait dire que c'est équivalent à la recherche dans un kd-tree. Est-ce le cas ?

[souviron34]

L'algo est donc en O(m.f(N)).

Tout le problème est de caractériser f(N), qui dépend donc de N.

Les graphes de mesure de f(N) font penser que Log(f(N)) = a*Log(N) + b f(N) = k.N^a

C'est bien ce qu'on avait l'air de conclure plus haut


Je ne sais pas comment on pourrait relier ça au plus proche voisin dans un kd-tree, qui, d'après le lien, serait en O (k N^1-1/k) , ce qui ressemble fortement à l'expression déterminée...

Pour être plus rigoureux sur cette formulation, il faut soit arriver a formaliser les opérations effectuées par f() (formule directe ou récurrente), soit montrer que f() est équivalent à un algo connu.

Si on part sur du "f(N) = N^a + cste", ca voudrait dire que c'est équivalent à la recherche dans un kd-tree. Est-ce le cas ?

J'avoue être trop loin des maths de haut niveau pour percevoir ce qu'est un kd-tree..

Pour résumer, en simplifiant un peu (les projections ne sont pas vraiment les projections (en fait un intrvalle basé sur les projections), mais on peut approximer à ça) :

• le nuage N est trié en ordre croissant sur la coordonnée principale
• Un segment i <-> i+1 de l'enveloppe se projette sur cet axe en 2 points
• f(N) est le nombre de points de N se situant entre ces 2 projections

Est-ce un kd-tree ?????


Je ne sais pas comment on pourrait relier ça au plus proche voisin dns un kd-tree, qui, d'après le lien, serait en O (k N^(1-1/k)), ce qui ressemble fortement à l'expression trouvée plus haut...

[davcha]

ces points de calcul de complexité sont les derniers points à régler avant le dépôt de l'article.. J'espère d'ici 2 semaines..

Puisque tu fais de la recherche dans le clutering, quels sont les meilleurs algos ( je veux dire complexité - simplicité - mémoire ) ?

Note : par contre, c'est un algo empirique, avec des valeurs numériques, ce qui risque de choquer les puristes et théoriciens. Mais qui moi, en tant que physicien, ne me choque pas du tout

Un algo très connu (certainement le plus utilisé) de clustering est k-means. Et sa complexité est O(n^{dk+1} log(n)), avec n le nombre de points, d le nombre de dimensions de l'espace dans lequel tes points sont plongés et k le nombre (prédéterminé) de clusters.

Après, tu as des algos qui sont plus intéressants que k-means... Je veux dire dont la fonction objectif est plus intéressante. Mais à priori, tu n'auras pas mieux qu'une complexité quadratique.

Y'a certaines personnes qui s'amusent à calculer des prior pour améliorer les perfs et la qualité de leur clusters, ça reste quadratique au mieux, il me semble.

Pour résumer, en simplifiant un peu (les projections ne sont pas vraiment les projections (en fait un intrvalle basé sur les projections), mais on peut approximer à ça) :

• le nuage N est trié en ordre croissant sur la coordonnée principale
• Un segment i <-> i+1 de l'enveloppe se projette sur cet axe
• f(N) est le nombre de points de N se situant entre ces 2 projections

Quand tu dis que tes N points sont triés sur la coordonnée principale. Comment tu la connais cette "coordonnée principale" ?

Et j'ai pas saisi quand tu dis "ces deux projections".

[souviron34]

. Mais à priori, tu n'auras pas mieux qu'une complexité quadratique.

Ok, donc une bonne piste de recherche

.Quand tu dis que tes N points sont triés sur la coordonnée principale. Comment tu la connais cette "coordonnée principale" ?

Je suis en 2D.

au moment du transfert initial, je calcule xmin,xmax,ymin,ymax, et j'en déduis la principale par quel delta est > à l'autre

.Et j'ai pas saisi quand tu dis "ces deux projections".

Ben 2 points quelcqonque de l'enveloppe se retrouvent forcément sur l'axe entre coordonnée min et coordonnée max du nuage..

Si je trie en Y, par exemple... Mes 2 points délimitant un segment ont tous les 2 des Y. Ces Y définissent un domaine sur l'axe.. Et en général il y en a 2 (ils ne sont confondus que quand le segment est horizontal). Alors comme j'ai dit c'est pas tout à fait aussi simple, mais c'est l'idée.

[davcha]

Ok, donc, imaginons qu'on ait ces données :


Tu remarques que sur le graphique l'axe des abscisses varie entre -10 et 20 et l'axe des ordonnées entre -3 et 4.
Donc, l'axe principal, pour toi, dans ce schéma est l'axe des abscisses ?

Autre exemple :

Quel est l'axe principal dans ce cas ?

Ensuite, si je comprends bien, dans le 1er exemple, si je dénote par x_i le point dont l'abscisse est environ -5 et x_j le point dont l'abscisse est environ 4, alors f(N) contient quasiment tout le nuage. C'est exact ?

[pseudocode]

Je ne sais pas comment on pourrait relier ça au plus proche voisin dns un kd-tree, qui, d'après le lien, serait en O (k N^(1-1/k)), ce qui ressemble fortement à l'expression trouvée plus haut...

En fait, on arrive a cette expression pour tout algorithme de type D&C lorsque "a" (le nombre de sous-problèmes) est plus grand que "b" (la réduction de la population). C'est à dire qu'il y a des individus en commun dans les sous-problèmes.

T(N) = a.T(N/b) + c.N
T(1) = 1

a<b --> T(N) = O(N)
a=b --> T(N) = O(N.Log(N))
a>b --> T(N) = O(N^k), avec k= Log_b(a)

[souviron34]

@Davcha :

sans doute

De toutes façons, cette dorection est juste un critère de tri

On peut la choisir suivant divers critères (je n'ai jamais de cas comme ça : je traitais des orages et des éclairs)

Mais quand tu fais par exemple le contour convexe, tu as forcément un grand axe et un petit axe... C'est tout. Tu peux te baser là-dessus..

On peut utliser une norme (ramener à 1), ou ce qu'on veut. C'est un principe.

[souviron34]

En fait, on arrive a cette expression pour tout algorithme de type D&C lorsque "a" (le nombre de sous-problèmes) est plus grand que "b" (la réduction de la population). C'est à dire qu'il y a des individus en commun dans les sous-problèmes.

T(N) = a.T(N/b) + c.N
T(1) = 1

a<b --> T(N) = O(N)
a=b --> T(N) = O(N.Log(N))
a>b --> T(N) = O(N^k), avec k= Log_b(a)

Je ne comprend pas l'application (ou non) pour mon problème...

Si m est le nomre de "sous-problèmes", et que b est N/m, que peut-on en déduire ???

Maintenant, il est à peu près sûr qu'il y a des points en commun entre 2 "sous-problèmes". (et heureusement, sinon ce ne serait pas ni progressif, ni équitable) . Le but de cet algo est justement de le réduire au minimum.. en utilisant des maths et un code simple.

[davcha]

Et tu en fais quoi de ces f(N) points, après ?

[souviron34]

pour chacun je regarde divers critères.. Si un point rempli tous les critères, alors, je le stocke, et je cherche parmi les suivants si un autre rempli encore mieux les critères. Ensuite,j'inclue le meilleur entre les 2 points définissant le segment, et j'itère.

[davcha]

Et, en fait, les m points sont définis comment ? Ils proviennent de ta projection sur l'axe principal, non ?