topic Re: shortest distance in SAS Programming

shortest distance

deega — Tue, 24 Jan 2017 03:05:12 GMT

Hi All,

I have a dataset with around 100000 records. I want to know only those three records that have shortest distance with a particular record. If I run the distance procedure then the program generates the output of matrix of 100000 variables giving distance of a variable with all other variables. It is actually not required and unecessarily it eats up my system time and sometimes evenhangs my system. If there is any other procedure that gives me the variables with just the shortest distance, please share.

Thanks in advance.....

Re: shortest distance

stat_sas — Tue, 24 Jan 2017 04:17:44 GMT

Hi,

What do you mean by a particular record?

Re: shortest distance

Reeza — Tue, 24 Jan 2017 04:49:07 GMT

Is there any other way besides calculating all distances to identify the shortest 3 distances?

Re: shortest distance

deega — Tue, 24 Jan 2017 05:02:13 GMT

@Reeza This is what my question is... Few days back I used SPSS Modeler, using its KNN Node, we can quickly find the nearest record ...

Re: shortest distance

deega — Tue, 24 Jan 2017 05:09:30 GMT

@stat_sas
by particular record, i mean for each record, something like below
Record No. Nearest Record 1 Nearest Record 2 Nearest Record 3
1 5 6 7
2 1 2 3
3 2 1 6
4 5 1 6
5 : : :
6 : : :
7 : : :
8 : : :
9 : : :
10 : : :
:
:

Re: shortest distance

stat_sas — Tue, 24 Jan 2017 05:42:31 GMT

Not sure but one way to get that is using k means clustering. Make a reference value and use that in proc fastclus in instat option to get the distances with regard to reference value. Then sort the output data set to flag the top 3 closest values.

Re: shortest distance

KachiM — Tue, 24 Jan 2017 10:43:21 GMT

Deega:

1 5 6 7
2 1 2 3
3 2 1 6
4 5 1 6

In this sample data set, you say 5, 6, 7 are the records that are closer to Record 1. You show a small example as how you got 5, 6, and 7?

What variable(s) (not shown here) are used for this decision?

Provide an example and illustrate how you find them. Finding algorithm to do fast is simpler once your your example is clear.

Re: shortest distance

Rick_SAS — Tue, 24 Jan 2017 13:25:07 GMT

I assume you want the Euclidean distance.

If you know the "particular record", then this is an easy problem that you can complete in the DATA step.

1. Put the particular record first in the data set (or hard-code it into an array).

2. Use the EUCLID function to compute the Euclidean distance between the particular record and the others.

3. Sort the data by distance and use the first 3 records.

For example, the following DATA step computes the Euclidean distances between the numerical measurements for the first observation ("Alfred") and the other observations. The result shows that Mary, William, and Janet are the students whose numerical measurements are closest to Alfred, as measured by the Euclidean distance function:

data Dist(drop=i);
array refPt [3] _temporary_; /* automatically RETAINed */
array diff  [3] _temporary_;
set sashelp.class;
array Pt [*] Height Weight Age;

/* initialize refPt, or use 
   array refPt[3] (val1 val2 val3); */
if _N_ = 1 then
   do i = 1 to dim(Pt);
      refPt[i] = Pt[i];
   end;

/* compute difference between Pt and refPt */
do i = 1 to dim(pt);
   diff[i] = refPt[i] - Pt[i];
end;
dist = euclid(of diff[*]);
if _N_>1;
run;

proc sort data=Dist; 
by dist;
run;

proc print data=Dist(obs=3);
run;

You can generalize this problem. Instead of finding the points nearest to a single reference point, you can find the points in one group that are nearest to points in another group. See the article "Distances between observations in two groups."

Re: shortest distance

Reeza — Tue, 24 Jan 2017 20:32:04 GMT

It was a logical question. You can't find the nearest neighbour without calculating all values first. Perhaps the KNN process in SPSS precalculates the distance and then obtains the nearest neighbour when you request it. This means it isn't calculating the distance matrix every time.

You need to provide more details regarding what is the issue in your current process. Ideally, you can provide sample input, your code and a message with which step is inefficient. Then we'll be able to suggest alternatives for your.

PROC DISTANCE is relatively fast, but if you don't need it run each time and can cache the results somehow that's a better process.

Re: shortest distance

deega — Wed, 25 Jan 2017 03:09:00 GMT

@Rick_SAS
Thanks for the reply. I have not used arrays much and trying to understand your program. Could you please tell what is _N_ here ???

Re: shortest distance

Reeza — Wed, 25 Jan 2017 03:36:20 GMT

_n_ is an automatic variable that counts the number of boundary steps. It is typically used as a pseudo row counter.

http://support.sas.com/documentation/cdl/en/lrcon/69852/HTML/default/viewer.htm#p0e0mk25gs9binn1s9jiu4otau29.htm

Re: shortest distance

deega — Wed, 25 Jan 2017 05:07:52 GMT

@Rick_SAS If I have around 1000000 records and for each record I need at least three nearest records,( means KNN with K=3) will this work? The Distance proc is not working because the output is 1000000 * 1000000 matrix.

Re: shortest distance

Rick_SAS — Wed, 25 Jan 2017 10:47:48 GMT

Please clarify two issue:

1. How many variables in this problem?

2. Do you have ONE reference point, and you want the three closest from among 1M observations? Or do you have 1M points and for each of those you want to find the three nearest neighbors? The first case requires computing 1M distances, The second case requires computing 1E12 distances.

Re: shortest distance

deega — Thu, 26 Jan 2017 01:21:26 GMT

@Rick_SAS

The shape of my dataset is as follows:

S. No.	Var1	Var2	Var3	Var4	Var5::	Var30
A1	1	2	1	3	1	5
A2	2	1	1	3	1	2
A3	1	1	2	1	2	1
A4	2	3	3	1	2	1
A5	1	2	1	2	1	2
A6	3	1	3	3	1	1
A7	2	1	2	1	2	1
A8	1	2	1	2	2	1
A9	1	1	3	5	2	2
A10::	2	2	1	0	0	0
A1000000	1	5	2	0	3	4

I want KNN (K=3) for each observation from A1 to A1000000. Actually I had 200M observations, first I made clusters using fastclus and thought of using distance procedure for calculating distance and sort and take the top 3 records. Some clusters have less records but some still have high number of records. I was able to use distance procedure till 100,000 records but it is not responding above this limit. When I tried KNN Node in SPSS it responded to higher number of records too, so I thought of customising program for distance instead of using Distance proc.

Please advise me something for this situation.

Re: shortest distance

Reeza — Thu, 26 Jan 2017 01:45:57 GMT

Customizing only makes sense if you have some other manner of filtering your calculations. For example, if this was spatial you might limit it to neighbouring provinces/states.

Re: shortest distance

mkeintz — Thu, 26 Jan 2017 03:58:04 GMT

@deega

Are your VARS really integers from 0 to 5 as in your sample?

If so, then instead of an algorithm to select points and determine which have the closest locations to a given point, you could systematically steps through the nearest possible locations to see which are occupined by a data point.

Re: shortest distance

deega — Thu, 26 Jan 2017 04:49:46 GMT

@mkeintz

No, the variables are not integers they are real numbers like 1.23, 0.28.....etc. but actually they were integers in different ranges like some variables were binary, some were in the range of 1 to 10, some were in the range of 30 to 70 etc and for creating clusters and finding distances I standardized the data and as a result data turned into decimal points.

Re: shortest distance

Rick_SAS — Thu, 26 Jan 2017 14:41:55 GMT

What is the business problem that you are trying to solve? Why do you think you need to compute nearest neighbors of 1M points? Will an approximate solution suffice?

I think you are asking for a very lengthy computation. This computation requires computing (1E6)**2 = 1E12 distances.

I suggest that you read my articles on computing NN neighbor distances. In one I show how to compute the k nearest neighbors by using PROC MODECLUS. For your data example, the syntax is

ods select none;
ods output neighbor=Neighbor;
proc modeclus data=Have method=1 k=4 Neighbor;
   var Var:;
   ID S_No;
run;
ods select all;

I ran some tests on your 30-dimensional data. I estimate that you can compute the three nearest neighbors for

30,000 obs in 1 minute

50,000 obs in 4.5 minutes

75,000 obs in 11.3minutes.

From these kinds of experiments and the fact that the computation is quadratic in the number of observations, you can predict that 1M observations would require about 40 hours to run in PROC MODECLUS, assuming adequate resources such as RAM.

Personally, I would ask whether it is possible to reformulate the problem. Work smarter, not harder.

Re: shortest distance

deega — Mon, 06 Feb 2017 08:52:49 GMT

Actually as per my business problem Jaccard Distance suits the best.

How practical is it to use the method of bubble sort while calculating Jaccard Distance, something like below:

Suppose there are 1M observations and I need three NN from these 1 M observations. If I calculate JD for obs1 & 2, then compare them, take the shortest and discard the other one. Then again compare the shortest of (1,2) with JD of 3, then again take the shortest.. and so on...