Trouver la liste des K plus proches voisins [Résolu]

[hoccha]

Hello,
Je cherche une p’tit fonction sas afin de trouver les K plus proches voisins dans un exemple de points.
Le data-step suivant génère un ensemble de 100 observations.

Code :

1
2
3
4
5
6
7
8
DATA observations;
	do ID=1 TO 100;	 
		x1 			= RAND('NORMAL',0,1); 
		x2 			= RAND('NORMAL',0,1);
		x3 			= RAND('NORMAL',0,1);
	output;
	end;
run;

Par exemple dans cet ensemble de 100 observations, si je veux trouver les K plus proches voisins du points [0.5,0.5,0.5] ; existe-t-il une procédure pour faire cela ?
J’ai bien trouvé la fonction proc discrim pour appliquer une calssif via KNN. Mais ce que je cherche ce n’est pas de réaliser une classification mais vraiment obtenir la liste des K plus proches voisins.
Merci!

[z6c3po]

avec un peu de data, un proc sort et un proc print, on s'en sort...

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
DATA obs;
  SET observations;
  dist1=(x1-0.5)**2;
  dist2=(x2-0.5)**2;
  dist3=(x3-0.5)**2;
  ddist=sum(of dist:);
run;
 
proc sort DATA=obs;
BY ddist;
run;
** et pour obtenir les 10 plus proches ;
proc print DATA=obs(obs=10);
run;

et hop

a+

Sébastien Ringuedé

[olivier.decourt]

Si les calculs de distance à la main comme propose Sébastien te rebutent (pourtant ils peuvent bien s'automatiser avec un Array), il reste la proc FASTCLUS.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
DATA observations;
	do ID=1 TO 100;	 
		x1 			= RAND('NORMAL',0,1); 
		x2 			= RAND('NORMAL',0,1);
		x3 			= RAND('NORMAL',0,1);
	output;
	end;
run;
DATA centre ;
   x1 = .5 ;
   x2 = .5 ;
   x3 = .5 ;
   id = 0 ;
RUN ;
PROC FASTCLUS DATA=observations 
			  SEED=centre 
	   MAXCLUSTERS=1
			NOPRINT 
			   OUT=distances ;
RUN ;
PROC SQL OUTOBS=5 ;
  CREATE TABLE KplusProches AS
    SELECT *
	FROM distances
	ORDER BY distance
  ;
QUIT ;

Olivier

[z6c3po]

Olivier, y'a un os...

ton programme donne les observations suivantes comme les plus proches :

Code :

1
2
3
4
5
6
7
8
 
Obs    ID       x1          x2          x3       CLUSTER    DISTANCE
 
 1     50    -0.02450     0.25015    -0.62610       1        0.94302
 2     49     0.11065    -0.52033     1.35914       1        2.03568
 3     51     0.26062     0.52107    -2.08021       1        2.27839
 4     53    -0.65540    -0.03759     0.58027       1        2.68694
 5     52    -1.39290     1.12551     1.02708       1        2.70617

si je prends la sommes des carrés de l'écart à la cible, j'obtiens :

Code :

1
2
3
4
5
6
7
8
 
Obs    ID       x1         x2         x3       dist1      dist2      dist3      ddist
 
  1    60    0.69875    0.48859    0.38262    0.03950    0.00013    0.01378    0.05341
  2    56    0.34971    0.71917    0.05890    0.02259    0.04803    0.19457    0.26519
  3    59    0.47044    0.04501    0.22602    0.00087    0.20702    0.07507    0.28296
  4    24    0.11331    0.06229    0.64597    0.14953    0.19159    0.02131    0.36243
  5    42    0.19256    0.25528    0.03003    0.09452    0.05989    0.22088    0.37528

on pourrait aussi utiliser une valeur absolue de l'écart rapporté à la cible...(inutile ici)

si je prends la somme des valeur absolue de l'écart à la cible, j'obtiens :

Code :

1
2
3
4
5
6
7
8
 
Obs    ID       x1         x2          x3       dist1      dist2      dist3      ddist
 
  1    60    0.69875     0.48859    0.38262    0.19875    0.01141    0.11738    0.32754
  2    59    0.47044     0.04501    0.22602    0.02956    0.45499    0.27398    0.75853
  3    56    0.34971     0.71917    0.05890    0.15029    0.21917    0.44110    0.81055
  4    24    0.11331     0.06229    0.64597    0.38669    0.43771    0.14597    0.97037
  5    85    0.56119    -0.44607    0.51288    0.06119    0.94607    0.01288    1.02014

et j'ai quand même l'idée que le point 60 (0.69875, 0.48859, 0.38262) est plus proche de .5 .5 .5 que le point 50 (-0.02450, 0.25015, -0.62610)

c'est le fait que tu cites la variable ID dans la table seed qui crée le merdier...obs 50, 49, 51, 52, 53...

a+

Sébastien Ringuedé

[hoccha]

Hello,
Merci à vous trois pour votre aide
Sur base du code de z6c3po, j’ai produit cette petite macro listOfKNN:

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
DATA observations;
  do ID=1 TO 10000; 
    x1 = RAND('NORMAL',0,1);
    x2 = RAND('NORMAL',0,1); 
    x3 = RAND('NORMAL',0,1);
    output;
  end;
run;
 
 
%macro listOfKNN (obser , target, K, nameOutput);
	%Let dim = %eval(%SYSFUNC(count(&target,%NRSTR( )))+1) ;
 
	%let ttt =;
	%DO ii = 1 %TO &dim; 
		%let ttt = &ttt.(x&ii.-(%scan(&target,&ii," ")))**2;
		%IF &ii NE &dim %THEN 
			%let ttt = &ttt.+; 
	%END;
 
	proc sql noprint ;
  		CREATE TABLE &nameOutput AS 
    	SELECT DISTINCT *, sqrt(&ttt)AS distance
    	FROM &obser
    	ORDER BY distance;
	quit;
 
	DATA &nameOutput;
  		SET &nameOutput (obs=&K);
		DROP distance;
	run;
%mend listOfKNN;
 
 
%listOfKNN(	obser 		=	observations, 
		target		=	0.5 1 1, 
		K		= 	5, 
		nameOutput	=	out
		  );

A++

[olivier.decourt]

Tu as raison Sébastien, j'ai voulu aller trop vite.
Dans la proc FASTCLUS, il manquait l'explicitation du rôle des variables (ID et les X1, X2, X3) ainsi que l'indispensable option MAXITER=0 pour qu'il n'essaye pas de déplacer le centre mais qu'il se contente de calculer la distance à celui qu'on fournit.
La proc ci-dessous annule et remplace la précédente.

Code :

1
2
3
4
5
6
7
8
9
10
 
PROC FASTCLUS DATA=observations 
			  SEED=centre 
	   MAXCLUSTERS=1
	       MAXITER=0
			NOPRINT 
			   OUT=distances ;
   ID id ;
   VAR x1 x2 x3 ;
RUN ;