nearest neighbour analysis

[mimmo]

anybody know of, or had experience using Excel to perform a Nearest Neighbour Analysis? Basically that involves finding the closest distance between an array of points that have x,y coordinates
thanks
nick

 

[yussi1870]

I would go about it like this:

Have one column list the X coordinates and another column list their corresponding Y coordinates. Create a Macro which loops through each Row. For each row: loop through all the other rows. Get the X value of the row and subtract from the current row's X value. Take the absolute value of this and add it to the corresponding value from the Y subtraction. Store this value only if it is the smallest value achieved for the current row and store its row number. Once you have completed looking through all the rows for the current row you will have the smallest value for the current row and it's row number so you can then place the row number in a column next to it. Do this for all the rows.

 

[Jay Petrulis]

On 2002-04-10 11:35, mimmo wrote:
anybody know of, or had experience using Excel to perform a Nearest Neighbour Analysis? Basically that involves finding the closest distance between an array of points that have x,y coordinates
thanks
nick

Hi Nick,

I just wrote this UDF which will handle any number of dimensions, but you get to check it!

Requirements are that the data must be a continuous block on the worksheet. The x,y,z,w...coordinates are in columns and each data point is in a row.

Please test this out against some of your data to check if the minimum distance is correct.

When you are satified with the results, I can add a calclulation to find the nearest neighbor data points.

------------------
Function NEAREST_NEIGHBOR(ValRange)

Dim RangeArray As Variant
Dim i As Long, j As Integer, distance As Double, min_dist As Double

If ValRange.Cells.Count = 0 Then
NEAREST_NEIGHBOR = CVErr(xlErrNum)
Exit Function
End If

RangeArray = ValRange.Value

For i = 1 To ValRange.Rows.Count - 1
distance = 0
For j = 1 To ValRange.Columns.Count
distance = distance + (RangeArray(i + 1, j) - RangeArray(i, j)) ^ 2
Next j
If i = 1 Then
min_dist = distance
Else: min_dist = WorksheetFunction.Min(min_dist, distance)
End If
Next i
NEAREST_NEIGHBOR = Sqr(min_dist)

End Function
---------------------

Called as a regular function
=NEAREST_NEIGHBOR(your range)

HTH,
Jay

 

[Jay Petrulis]

Correction! Need to have an additional loop.

----------------------
Function NEAREST_NEIGHBOR(ValRange)

Dim RangeArray As Variant
Dim i As Long, k As Long
Dim j As Integer, distance As Double, min_dist As Double

If ValRange.Cells.Count = 0 Then
NEAREST_NEIGHBOR = CVErr(xlErrNum)
Exit Function
End If

RangeArray = ValRange.Value

For i = 1 To ValRange.Rows.Count - 1
For k = i + 1 To ValRange.Rows.Count
distance = 0
For j = 1 To ValRange.Columns.Count
distance = distance + (RangeArray(k, j) - RangeArray(i, j)) ^ 2
Next j
If i = 1 And k = 2 Then
min_dist = distance
Else: min_dist = WorksheetFunction.Min(min_dist, distance)
End If
Next k
Next i
NEAREST_NEIGHBOR = Sqr(min_dist)

End Function
-------------------------

Bye,
Jay

Edit: You might want to change the spelling of the function to the British equivalent!
This message was edited by Jay Petrulis on 2002-04-10 18:39
This message was edited by Jay Petrulis on 2002-04-10 22:09

 

[Jay Petrulis]

Hi All,

This was a past posting that has been enhanced with this post. The original UDF took a range of coordinates and returned the minimum distance between any two sets of coordinates.

This one returns the nearest neighbor from from a specified row of coordinates.

For example, if each coordinate point is in B:E and the data table is from B2:E20, then

=nearest_neighbor2(B2:E2,$B$2:$E$20)

will return the minimun distance between B2:E2 and any other B:E set within the range.

Not that there is any specific usefulness for this for anybody, but you may be able to gather something from the code to use in a future project.

Function NEAREST_NEIGHBOR2(TestRange As Range, ValRange As Range)

Dim RangeArray As Variant, TestArray As Variant
Dim i As Long, Counter As Long
Dim j As Integer, distance As Double, min_dist As Double
Dim StartValRangeRow As Long, StartTestRangeRow As Long

If ValRange.Cells.Count = 0 Then
NEAREST_NEIGHBOR2 = CVErr(xlErrNum)
Exit Function
End If

'''Read the values into an array
TestArray = TestRange.Value
RangeArray = ValRange.Value

'''Identify the starting row for each argument
'''to ignore comparing a row against itself.
StartValRangeRow = ValRange.Row
StartTestRangeRow = TestRange.Row


'''Loop through the data and determine the minimum distance.
For i = 1 To ValRange.Rows.Count
    If StartValRangeRow + i - 1 <> StartTestRangeRow Then
        distance = 0 ' reset distance in each pass
        Counter = Counter + 1
        For j = 1 To ValRange.Columns.Count
            distance = distance + (TestArray(1, j) - RangeArray(i, j)) ^ 2
        Next j
        If Counter = 1 Then
            min_dist = distance '''first pass must be the minimum so far
        Else
            min_dist = WorksheetFunction.Min(min_dist, distance)
        End If
    End If
Next i

NEAREST_NEIGHBOR2 = Sqr(min_dist)

End Function

Any comments/enhancements/suggestions welcome.

Thanks,
Jay

 

[leo.caguimbal]

Thanks Jay. that was very helpful.

The macro yields the nearest distance within the range of coordinates. What if I wanted to get the name of that nearest point.

for example

node x y
1a 3 4
2a 5 6

test coordinate
x y
1 1

the nearest point from (1,1) is (3,4). the program should give the string 1a instead of the distance..

would that be possible?

how to hear from you.

thanks,

leo

 

[Sal Paradise]

Here is a formula solution, please check the answers:

Excel Workbook
	A	B	C	D
1	node	x	y	*
2	1a	3	4	8a
3	2a	5	6	8a
4	3a	7	5	4a
5	4a	8	5	3a
6	5a	6	8	6a
7	6a	7	8	5a
8	7a	5	6	8a
9	8a	5	5	2a
10	9a	6	8	6a
11	10a	2	7	1a
12	11a	8	2	4a
13	12a	2	2	1a
Sheet1

If there are two closest points, it picks the first one in the list.

ETA: There is some problem in my logic, as zero values pop up from time to time. I can't seem to figure out why either.

 

[mosstache]

Now this is slick. How could I use the Small function to find the 2nd nearest neighbor, and then the third, fourth, fifth? I envision setting up 5 columns beside a dataset of Name,Xcoordinate,Ycoordinate,1stNN,2ndNN,3rdNN,4thNN,5thNN.

I tried plugging in the small function in place of the min, but I'm coming up with errors. Any thoughts on this?

Here is a formula solution, please check the answers:
Sheet1

*	A	B	C	D
1	node	x	y	*
2	1a	3	4	8a
3	2a	5	6	8a
4	3a	7	5	4a
5	4a	8	5	3a
6	5a	6	8	6a
7	6a	7	8	5a
8	7a	5	6	8a
9	8a	5	5	2a
10	9a	6	8	6a
11	10a	2	7	1a
12	11a	8	2	4a
13	12a	2	2	1a

<colgroup><col style="font-weight:bold; width:30px; "><col style="width:44px;"><col style="width:20px;"><col style="width:20px;"><col style="width:72px;"></colgroup><tbody>
</tbody>

Spreadsheet Formulas

Cell Formula D2 {=INDEX(A$2:A$13,MATCH(MIN(IF(B2&","&C2<>B$2:B$13&","&C$2:C$13,ABS(B2-B$2:B$13)+ABS(C2-C$2:C$13))),IF(B2&","&C2<>B$2:B$13&","&C$2:C$13,ABS(B2-B$2:B$13)+ABS(C2-C$2:C$13)),0))} <tbody> </tbody>

Formula Array: Produce enclosing { } by entering formula with CTRL+SHIFT+ENTER!

<tbody>
</tbody>

Excel tables to the web >> Excel Jeanie HTML 4
If there are two closest points, it picks the first one in the list.

ETA: There is some problem in my logic, as zero values pop up from time to time. I can't seem to figure out why either.