Main Content

knnsearch

Find nearest neighbors by edit distance

Description

example

idx = knnsearch(eds,words) finds the indices of the nearest neighbors in the edit distance searcher eds to each element in words.

example

[idx,d] = knnsearch(eds,words) also returns the edit distances between the elements of words and the nearest neighbors.

example

[idx,d] = knnsearch(eds,words,Name,Value) specifies additional options using one or more name-value pair arguments.

Examples

collapse all

Create an edit distance searcher.

vocabulary = ["Text" "Analytics" "Toolbox"];
eds = editDistanceSearcher(vocabulary,2);

Find the nearest words to "Test" and "Analysis".

words = ["Test" "Analysis"];
idx = knnsearch(eds,words)
idx = 2×1

     1
     2

Get the words from the vocabulary using the returned indices.

nearestWords = eds.Vocabulary(idx)
nearestWords = 1x2 string
    "Text"    "Analytics"

Create an edit distance searcher.

vocabulary = ["MATLAB" "Text" "Analytics" "Toolbox"];
eds = editDistanceSearcher(vocabulary,2);

Find the nearest words and their edit distances to "Test" and "Analysis".

words = ["Test" "Analysis"];
[idx,d] = knnsearch(eds,words)
idx = 2×1

     2
     3

d = 2×1

     1
     2

Get the words from the vocabulary using the returned indices.

nearestWords = eds.Vocabulary(idx)
nearestWords = 1x2 string
    "Text"    "Analytics"

Changing the word "Test" to "Text" requires one edit: a substitution. Changing the word "Analysis" into "Analytics" requires two edits: a substitution and an insertion.

Create an edit distance searcher.

vocabulary = ["MathWorks" "MATLAB" "Analytics"];
eds = editDistanceSearcher(vocabulary,5);

Find the two nearest words and their edit distances to "Math" and "Analysis".

words = ["Math" "Analysis"];
idx = knnsearch(eds,words,'K',2)
idx = 2×2

     1     2
     3   NaN

View the two closest words to "Math".

idxMath = idx(1,:);
newWords = eds.Vocabulary(idxMath)
newWords = 1x2 string
    "MathWorks"    "MATLAB"

There is only one word within the maximum edit distance from "Analysis", so the function returns NaN for the other indices. View the nearest words with valid indices.

idxAnalysis = idx(2,:);
idxAnalysis(isnan(idxAnalysis)) = [];
newWords = eds.Vocabulary(idxAnalysis)
newWords = 
"Analytics"

Input Arguments

collapse all

Edit distance searcher, specified as an editDistanceSearcher object.

Input words, specified as a string vector, character vector, or cell array of character vectors. If you specify words as a character vector, then the function treats the argument as a single word.

Data Types: string | char | cell

Name-Value Arguments

Specify optional pairs of arguments as Name1=Value1,...,NameN=ValueN, where Name is the argument name and Value is the corresponding value. Name-value arguments must appear after other arguments, but the order of the pairs does not matter.

Before R2021a, use commas to separate each name and value, and enclose Name in quotes.

Example: knnsearch(eds,words,'K',3) finds the nearest three neighbors in eds to the elements of words.

Number of nearest neighbors to find for each element in words, specified as a positive integer.

Example: 'K',3

Data Types: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64

Option to return neighbors whose distance values are equal, specified as true or false.

If 'IncludeTies' is false, then the function returns the K neighbors with the shortest edit distance, where K is the number of neighbors to find. In this case, the function outputs N-by-K matrices, where N is the number of input words. To specify K, use the 'K' name-value pair argument.

If 'IncludeTies' is true, then the function also returns the neighbors whose distances are equal to the Kth smallest distance in the output. In this case, the function outputs cell arrays of size N-by-1, where N is the number of input words. The elements of the cell arrays are vectors with at least K elements. The function sorts the neighbors in each vector in ascending order of distance.

Example: 'IncludeTies',true

Data Types: logical

Output Arguments

collapse all

Indices of nearest neighbors in the searcher, returned as a matrix or a cell array of vectors.

If 'IncludeTies' is false, then the function returns the K neighbors with the shortest edit distance, where K is the number of neighbors to find. In this case, the function outputs N-by-K matrices, where N is the number of input words. To specify K, use the 'K' name-value pair argument.

If 'IncludeTies' is true, then the function also returns the neighbors whose distances are equal to the Kth smallest distance in the output. In this case, the function outputs cell arrays of size N-by-1, where N is the number of input words. The elements of the cell arrays are vectors with at least K elements. The function sorts the neighbors in each vector in ascending order of distance.

Data Types: double | cell

Edit distances to neighbors, returned as a matrix or a cell array of vectors.

If 'IncludeTies' is false, then the function returns the K neighbors with the shortest edit distance, where K is the number of neighbors to find. In this case, the function outputs N-by-K matrices, where N is the number of input words. To specify K, use the 'K' name-value pair argument.

If 'IncludeTies' is true, then the function also returns the neighbors whose distances are equal to the Kth smallest distance in the output. In this case, the function outputs cell arrays of size N-by-1, where N is the number of input words. The elements of the cell arrays are vectors with at least K elements. The function sorts the neighbors in each vector in ascending order of distance.

Data Types: double | cell

Version History

Introduced in R2019a