reprogrammer le k-means en LUA

[bello john]

Salut les gens,

Est ce que quelqu'un pourrait m'aider à reprogrammer et améliorer cet algorithme en LUA. Cet algorithme, dont le nom est le kmeans, se présente ainsi: http://fr.wikipedia.org/wiki/Algorithme_des_k-moyennes
http://www.memoireonline.com/10/08/1603 ... ion17.html


En BASIC, pour des individus appartenant à R, cela donne:

Ne pouvant pas définir une liste de listes à tailles différentes, j'ai utilisé des matrices que j'ai complétées avec des 0 pour égaliser les tailles. Par conséquent, j'ai du redéfinir la moyenne pour qu'elle prenne en compte ce rajout de zéros.

La nouvelle moyenne: m0

Code: Select all

Define m0(a)=
Func
Local n
n:=countif(a,? =/= 0)
Return 1/n*sum(a)
EndFunc

Le début de l'algorithme: debutk, avec l: la liste des individus et c: ma liste de centres. Comme les individus sont des nombres réels, j'ai utilisé la distance euclidienne sur R, i.e. la distance entre deux individus = la valeur absolue de la différence des deux individus

Code: Select all

Define debutk(l,c)=
Func
Local d,r,i,j
d:=seq( seq( abs(l[i]-c[j]),i,1,dim(l)) ,j,1,dim(c) )
r:=NewMat(dim(c),dim(l))
For i,1,dim(c)
   For j,1,dim(l)
      If abs(l[j]-c[i])=min(mat>list(d^T[j])) Then
         r[i,j]:=l[j]
      EndIf
   EndFor
EndFor
Return r
EndFunc

et le kmeans

Code: Select all

Define kmeans(l,c)=
Func
Local r,i,d
i:=1
d:=c
r:=debutk(l,d)
Disp "Etape :",i;" :",r,d
While r=/= debutk(l,d)
   d:=seq(m0(mat>list(r[i])),i,1,rowDim(r))
   r:=debut(l,d)
   i:=i+1
   Disp "Etape :",i," :",r,d
EndWhile
Disp "kmeans fini en ",i," étape(s)"
Return debutk(l,d)
EndFunc

En gros j'aimerais pouvoir utiliser cet algorithme avec des n-uplets (n€N) (d'où la nécessité d'utiliser le lua, que je ne maitrise pas ). Aussi, dans le cas où les individus appartiennent à R, j'aimerais pouvoir les visualiser sur une droite graduée avant qu'ils ne subissent le kmeans (d'où la nécessité d'utiliser le lua encore )
Merci à celui qui pourra éclairer ma lanterne.

[AnToX98]

Salut à toi. Pour être sincère, je n'ai vraiment pas compris ton algorithme.
Sinon, pour éviter que tu ais à m'expliquer concrètement son fonctionnement, je t'invite à me dire ce que tu voudrais programmer en lua.

Merci de ta compréhension,
AnToX98

[Bisam]

Je n'ai pas encore bien compris ce que fait ton algorithme... mais je vois déjà comment tu peux simplifier son écriture...

Code: Select all

Define m0(a)=
Func
Return sum(a)/countif(a,? =/= 0)
EndFunc

Code: Select all

Define debutk(l,c)=
Func
Local d
d:=seq(abs(l-c[j]),j,1,dim(c))
Return seq(seq(when(d[i,j]=min(mat>list(d^T[j])),l[j],0),i,1,dim(c)),j,1,dim(l))
EndFunc

et

Code: Select all

Define kmeans(l,c)=
Func
Local r,i,d
i:=1
d:=c
r:=debutk(l,d)
Disp "Etape :",i;" :",r,d
While r=/= debutk(l,d)
   d:=seq(m0(mat>list(r[i])),i,1,rowDim(r))
   r:=debutk(l,d)
   i:=i+1
   Disp "Etape :",i," :",r,d
EndWhile
Disp "kmeans fini en ",i," étape(s)"
Return debutk(l,d)
EndFunc

Ensuite, je n'ai pas bien compris ce que tu voulais faire avec des n-uplets... mais je pense que c'est faisable en Basic, à condition de modifier la façon de stocker tes données et de faire ton algorithme.