En fait, la philosophie de base est bien Divide & ConquerCitation:
Envoyé par pseudocode
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 ?
Version imprimable
En fait, la philosophie de base est bien Divide & ConquerCitation:
Envoyé par pseudocode
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 ?
Mais tu ne détectes donc que les contours d'un nuage de points qui provient d'un cluster unique, donc sans overlaps, exact ?Citation:
Envoyé par souviron34
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..Citation:
Envoyé par davcha
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..Citation:
Envoyé par davcha
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é):Citation:
Envoyé par souviron34
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,Citation:
Envoyé par souviron34
:arrow: f() linéaire par rapport a NCitation:
Je suppose que diviser N par le segment de l'enveloppe est donc en N / (m/2)
:arrow: a = b = 2.Citation:
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.Citation:
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)). :PCitation:
m est le nombre de pts de l'enveloppeCode:
2
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 :arrow: 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 ?
;)Citation:
Envoyé par pseudocode
C'est bien ce qu'on avait l'air de conclure plus haut :)Citation:
Envoyé par pseudocode
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..Citation:
Envoyé par pseudocode
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.Citation:
Envoyé par souviron34
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" ?Citation:
Envoyé par souviron34
Et j'ai pas saisi quand tu dis "ces deux projections".
Ok, donc une bonne piste de recherche ;)Citation:
Envoyé par davcha
Je suis en 2D.Citation:
Envoyé par davcha
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..Citation:
Envoyé par davcha
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 :
http://www.developpez.net/forums/att...1&d=1337434013
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 :
http://www.developpez.net/forums/att...1&d=1337434203
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.Citation:
Envoyé par souviron34
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...Citation:
Envoyé par pseudocode
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 ?
Non
Le m de départ est l'enveloppe convexe plus un certain nombre déterminés par une première approximation.
Et ce m croît au fur et à mesure que des points répondant aux citères sont trouvés entre 2 sommets, dans une phase de rafinnement qui est celle qui me préoccupe ici.
Dans l'idéal la boucle serait assez simple. Dans la réalité il faut considérer qu'il faut être "fair" dans le traitement, pour ne pas privilégier un côté par rapport à un autre..
Ok, j'ai zappé un détail. Ton algo cherche quoi en définitive ? L'enveloppe convexe ou concave d'un nuage de points ?
tu veux dire b=m ?Citation:
Envoyé par souviron34
s'il y a des éléments en commun dans les sous problèmes, alors "b" est plus petit que "a". Et la conclusion est que la complexité est en O(N^Log_b(a)).Citation:
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.
Tout ca sous réserve que tu puisses modéliser les opérations de ton algo sous la forme T(N)=a.T(N/b) + c.N
concaveCitation:
Envoyé par davcha
oui :)Citation:
Envoyé par pseudocode
OK, ça correspond à la courbe expérimentale, non ?? (enfin, j'y comprend plus grand chose : O (m N^...) , non ?) (l'expression d'après la courbe de l'algo total, la double boucle, était O ( m (N 10^(1-logN)) ) )Citation:
Envoyé par pseudocode
Ce sont des opérations relativement simples (tests), plus quelques complexes (calcul du numérateur et dénominateur d'une intersection possible, calcul d'un angle entre 3 points), mais dont le flux est linéaire...Citation:
Envoyé par pseudocode
On ne pacoure plus de tableaux ou de listes. Pour chaque point examiné on utilise 3 points et on teste divers éléments.
On peut donc dire que les opérations sont en O(1) pour chaque point examiné (un nombre constant par point)
C'est ça que tu appelles "modéliser" ??
Je m'y perd avec le vocabulaire spécialisé...
Donc, en fait, ton algo fait ça : http://youtu.be/EpTgOC_XLRo
Oui. Je ne me suis intéressé qu'a la deuxième boucle (ce qui revient a traiter m comme une constante, et pas comme un paramètre d'entrée). Bref on appelle "m" fois une fonction (2nde boucle) qui fait "F(N)" opérations.Citation:
Envoyé par souviron34
On considère que chaque opération se fait en temps constant O(1).
Le nombre d'opérations est estimé en considérant le problème comme du D&C. Le problème est décomposé en "a" sous-problèmes, chacun s'occupant d'une partie de la population (taille N). Les parties (chacune de taille N/b) ne sont pas disjointe, il y a des individus en commun.
D'où la complexité en nombre d'opération F(N) = O(N^Log_b(a))
La complexité totale de l'algo, 1ère bouche comprise est donc O(m.N^Log_b(a))
Log_b , c'est log en base b ou le log itéré b fois ?
Vu que là b = a = m, alors on aurait une expression...
OK. là je cromprend mieux :)
C'est donc du "fractional power" ?
N^Log_b a est équivalent à N 10^(1-a LogN) ??? (pas le même a, bien sûr)
Par contre, la "modélisation" de m en fonction de N est ... ?????? A part expérimentalement (pour l'algo le plus précis, on va de N quand N faible à N/10 par exemple pour N ~ 50 000, pour l'algo le moins précis de N à N/100 sur le même range) je ne sais absolument pas ce que je pourrais faire...
Mais enfin, là on a déjà bien avancé... :)
@Davcha : en un sens oui, mais beaucoup plus précis, visuellement correspondant à ce que l'oeil voit, et sans presque de consommation mémoire et de maths complexes (même pas de k-nearest neighbors, pas de tree, pas Delaunay ou Voronoi)... Aucune hypothèse sur les points, coordonnées en réel.
Log en base b.Citation:
Envoyé par souviron34
oui.Citation:
C'est donc du "fractional power" ?
et bien, ca m'en a tout l'air. Si je ne me goure pas N.10^(1-a.LogN) = 10.N^(1-a)Citation:
N^Log_b a est équivalent à N 10^(1-a LogN) ??? (pas le même a, bien sûr)
Ok..Citation:
Envoyé par pseudocode
Super : log en base m de m, ça fait assez peu :)
Donc, en fractional power, est-ce que les best average et worst correspondent à :
best case : O(m) N quasi infini
worst case : O(mN) N petit
average case : O ( m N^c) avec la notation
?
Oui mes neurones et circuits divers ne se sont reconnctés que (encore une fois) ce matin en prenant mon café :cry:Citation:
Envoyé par pseudocode
Un très gros merci à toi :)
En fait, là ça n'est qu'une partie, mais il y en a 2 autres qui ont le même type de complexité, mais avec m à la place de N (donc beaucoup plus faibles), et du coup, le total de l'algo est avec cette complexité "fractional power"...
En dernier point, penses-tu que je puisse / doive appuyer la démonstration par un graphique comme le 2 ou le 4 , par exemple du temps total de l'algo en fonction de N, comme conclusion du paragraphe sur la complexité ?
Est-ce que je peux / dois conclure par :
"It behaves in O ( n log(n) ) (the exact equation is O (n n^c))"
ou
"It behaves in O ( n n^c ) (which in average behaves like O ( n log(n) )"
ou est-ce que je laisse juste "fractional power", en donnant la valeur numérique de l'exposant trouvée d'après le graphique ?
PS: vu l'aspect "sensible" de certains de mes posts ici, je vais juste en "éditer" un ou 2 pour les rendre un peu moins précis, maintenant que vous les avez lus et répondus.. Ce sera public d'ici peu, mais en attendant... (et je me ferais un plaisir de mettre les pointeurs soit ur Contribuez soit dans les FAQ)
PPS: un gros merci à vous, et en particulier à toi, Xavier, et toutes mes excuses pour être un peu dur à la comprenette avec ces notions et notations, qui me sont pas mal étrangères... :oops:
Pour moi, ce sont deux choses différentes.Citation:
Envoyé par souviron34
La complexité en O(...) mesure le "comportement" de l'algorithme par rapport à la taille des données d'entrée (linéaire, logarithmique, linearithmique, exponentiel, ... ).
Les graphes mesurent la "performance" de l'algorithme pour des sets usuels/spécifiques de données d'entrée (nuage éparse, points d'attraction, cas dégénérés, ....)
... Ils sont pourtant révélateurs du comportement en fonction de la taille de l'entrée, non ?? (en tous cas pour le nombre de points pour l'étape dont je parlais ici. Mais également pour le temps en fonction de N, si on prend le temps comme relatif et non absolu)Citation:
Envoyé par pseudocode
Mais OK, donc je ne les inclue pas...
Il faudra cependant que j'en inclue pour "définir" le m attendu en fonction de N et des 2 autres paramètres d'entrée, car je n'ai absolument aucune théorie pour supporter un tel calcul...
Je ne sais même pas si il y a une théorie donnant le nombre de points d'une enveloppe convexe par rapport au nombre de points d'un nuage (je n'y crois guère, vu qu'on peut avoir le même nombre de points dans l'enveloppe avec un nuage de 10 points qu'avec un nuage de 500 000)
Là, pour un contour concave, il doit cependant y avoir une "certaine" relation entre les 2, en fonction des paramètres ... Puisque au pire on passerait par tous les points...
Ca dépend de tes données.Citation:
Envoyé par souviron34
A priori, j'aurais tendance à dire que si tu fais une PCA, le 2nd plus grand axe te donne une information sur le nombre de points que tu vas devoir explorer par segment projeté sur le 1er plus grand axe.
Sinon... Le cas dont tu parles : 10 points sur l'enveloppe pour 500k dans le nuage, c'est un cas dégénéré où tu as plusieurs outliers, clairement.
Je ne sais pas ce qu'est une PCA..Citation:
Envoyé par davcha
Là je ne parlais de toutes façons pas du nbe de points utilisés, mais du nombre de points final dans l'enveloppe...
euh.....Citation:
Envoyé par davcha
1) je parlais de contour convexe
2) prend n'importe quel nuage de points et cherche son enveloppe convexe : quelque soit le nombre de point dans le nuage, tu auras sans doute dans les 20-30 points au grand max dans l'enveloppe... (bien sûr, ça peut être plus grand, mais c'est sans aucune commune mesure avec le nombre de points du nuage : et c'est ce que je dis : je ne voyais pas comment on peut trouver une théorie donnant le nombre de points ATTENDUS d'une enveloppe convexe en fonction du nombre de points du nuage)
PCA : principal component analysis.
Un ensemble de points étant donné, ça te permet de récupérer les axes (ou dimensions) qui présentent la variance la plus importante.
Sinon, tu prends ce nuage de points :
http://www.developpez.net/forums/att...1&d=1337520060
Tu as 200 points dans le nuage et 200 points dans l'enveloppe convexe. (Je parlais de l'enveloppe convexe aussi).
Et tu as un axe à angle, ce qui te demande de faire des calculs d'angles pour le tri, plus des calculs pour la PCA..Citation:
Envoyé par davcha
Pas terrible ;)
ok, c'est le seul cas particulier pour une enveloppe convexeCitation:
Envoyé par davcha
(et ça n'existe pas trop dans la nature)
de toutes façons dans ce cas mon algo s'est arrêté au stade convexe, qui est en O(Nm), et donc en dans ce cas en O(N^2), comme la plupart des autres (j'utilise un algo connu) :)
Ce que je voulais dire c'est que EN DEHORS DE CE CAS, je ne connais aucune règle permettant de prédire le nombre de sommets de l'enveloppe convexe...
Sur l'image ci-dessous, tu dois en gros avoir le même nombre de sommets convexes, et pourtant les nombres varient grandement.. (et je peux te sortir des nuages avec 50 000 ou 100 000 points, même avec des clusters dedans, pour lesquels ce sera strictement identique)
On s'est mal compris. Pour moi les 2 informations sont importantes: la complexité et la mesure de performance. C'est simplement que l'une et l'autre ne montrent pas la même chose.Citation:
Envoyé par souviron34
La complexité représente "la forme" de la courbe, mais comme on masque le facteur d'échelle ca ne donne pas du tout d'indication sur la performance.
Par exemple, tu peux avoir un algo qui fait 9874*N*Log(N) opérations, et un autre algo qui fait 3*N² opérations. Pour 1000 data en entrée, il y a un facteur 10 en faveur du second algo. :D
d'accord avec ça :)
Mais c'est la comparaison entre 2 algos..
Mais si tu dis que tu as une complexité en N log(N), et que tu traces une courbe donnant le temps d'éxécution de CET algo en fonction de N, avec des N couvrant des domaines logarithmiques, tu dois bien avoir la même forme, non ?
Sans comparer entre 2 algos différents.
Juste pour confirmer le calcul de la complexité par un graphe du temps, non ?
Si j'ai une compleixté en N^2, si je trace une corube avec le temps d'exécution pour 10,20, 30, ... 100, ..1000, je dois bien avoir une courbe de puissance (les opérations sont les mêmes pour chaque essai, il n'y a que le N qui change), sur laquelle je peux superposer une courbe "exacte" de puissance carrée mise à l'échelle, non ??
C'est ce que je voulais dire...
Enfin, en physique c'est comme ça qu'on procède pour vérifier une théorie..
Le graphe ne peut pas vraiment servir de preuve, mais plutot d'indication sur le comportement (et donc sur la complexité). Les résultats obtenus dépendent grandement des données d'entrées : on peut, sans le vouloir, utiliser un cas particulier (best ou worst) et en déduire des choses fausses.Citation:
Envoyé par souviron34
Généralement, le graphe est plutôt une confirmation du "bon" comportement de l'algo sur des sets de données usuels/spécifiques.
OK. Bon. En physique on le voit à l'envers : à part les cas particuliers, si ça marche en moyenne, et que les écarts sont symétriques, c'est que c'est bon..
(n'avoir que des cas particuliers sur 30, 50, ou 100 "nuages" non synthétiques mais naturels(au sens propre, c'est à dire tirés de la nature et pas d'un programme qui les fabrique) , ça paraît hautement improbable)
Maintenant, il y a encore une chose qui me chiffone :
Si l'algo suit une loi de "fractional power", logiquement la puissance (comme d'ailleurs iniqué dans le lien) devrait être fixe.
Or là, on se rend compte que pour 10 c'est 1/2 N, pour 50 c'est 0.2 N, pour 30 000 c'est 0.01 N...
J'ai essayé cette après-midi de reproduire la formule N^(1-a) avec un "a" mesuré sur la courbe, et ça donne des trucs aberrants...
:roll: je ré-essaierais demain...
Je m'y perd.. Snifffffff...
Faut pas oublier que la notation O(...) donne seulement l'allure générale sous forme d'une courbe "dominante" (=un majorant). On cherche généralement a indiquer le "plus petit dominant" parmi la liste usuelle : O(1), O(log n), O(n^c) c<1, O(n), O(n log n), O(n^c) c>1, ...Citation:
Envoyé par souviron34
Personne ne s'attend a ce que la formule donnée reflète exactement le nombre d'opération de l'algo.
Par contre, il est possible que ton algo soit dominé par une courbe plus basse ( comme (log n)^c ou log*(n) ), mais si on ne peut pas le prouver ca reste une conjecture. Vaut mieux dire qu'on est "O(n^c) c<1" parce qu'on peut le prouver, et indiquer que les mesures de perfs semblent indiquer qu'on est dessous.