nearest neighbour analysis
Thanks Thanks:  0
Likes Likes:  0
Results 1 to 8 of 8

Thread: nearest neighbour analysis

  1. #1
    New Member
    Join Date
    Apr 2002
    Posts
    9
    Post Thanks / Like
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Default

     
    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

  2. #2
    Board Regular
    Join Date
    Mar 2002
    Posts
    134
    Post Thanks / Like
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Default

    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.

  3. #3
    MrExcel MVP Jay Petrulis's Avatar
    Join Date
    Mar 2002
    Location
    Chicago, IL USA
    Posts
    2,040
    Post Thanks / Like
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Default

    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

  4. #4
    MrExcel MVP Jay Petrulis's Avatar
    Join Date
    Mar 2002
    Location
    Chicago, IL USA
    Posts
    2,040
    Post Thanks / Like
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Default

    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 ]

  5. #5
    MrExcel MVP Jay Petrulis's Avatar
    Join Date
    Mar 2002
    Location
    Chicago, IL USA
    Posts
    2,040
    Post Thanks / Like
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Default

    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.

    Code:
    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

  6. #6
    New Member
    Join Date
    Mar 2009
    Posts
    1
    Post Thanks / Like
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Default Re: nearest neighbour analysis

    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

  7. #7
    Board Regular
    Join Date
    Oct 2006
    Location
    日本
    Posts
    2,457
    Post Thanks / Like
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Default Re: nearest neighbour analysis

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

    *ABCD
    1nodexy*
    21a348a
    32a568a
    43a754a
    54a853a
    65a686a
    76a785a
    87a568a
    98a552a
    109a686a
    1110a271a
    1211a824a
    1312a221a

    Spreadsheet Formulas
    CellFormula
    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))}
    Formula Array:
    Produce enclosing
    { } by entering
    formula with CTRL+SHIFT+ENTER!


    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.
    Last edited by Sal Paradise; Mar 17th, 2009 at 10:47 PM.
    Download an HTML Maker to show your data, and please wrap all code in [code][/code] tags so we can read it. My mind-reading add-in is on my other computer.

  8. #8
    New Member
    Join Date
    Feb 2015
    Posts
    1
    Post Thanks / Like
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Default Re: nearest neighbour analysis

      
    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?


    Quote Originally Posted by Sal Paradise View Post
    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

    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))}
    Formula Array:
    Produce enclosing
    { } by entering
    formula with CTRL+SHIFT+ENTER!


    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.

User Tag List

Like this thread? Share it with others

Like this thread? Share it with others

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

 

 
DMCA.com