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) )...
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
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.
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 ?
D'après ce que je comprend, en considérant "m" comme une constante pour l'instant,
f() linéaire par rapport a NJe suppose que diviser N par le segment de l'enveloppe est donc en N / (m/2)
a = b = 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.
T(N) = 2*T(N/2) + N = O(N.log(N))
Si tu dois refaire l'étape de division à chaque appel récursif, c'est du D&C.En fait, c'est pas plutôt une dichotomie ?
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 ..
hum... bon visiblement ce n'est donc pas du D&C.
Reprenons du début.
L'algo est donc en O(m.f(N)).m est le nombre de pts de l'enveloppe
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++ )
f est le nbe de pts explorés pour 1 pt i
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 ?
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...
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...
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.
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".
Ok, donc une bonne piste de recherche
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
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.
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 ?
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)
@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.
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.
Et tu en fais quoi de ces f(N) points, après ?
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.
Et, en fait, les m points sont définis comment ? Ils proviennent de ta projection sur l'axe principal, non ?
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager