k-Nearest-Neighbor Classifiers These classifiers are memory-based, and require no model to be fit. Given a query point x0, we find the k training points x(r),r = 1,...,k closest in distance to x0, and then classify using majority vote among the k neighbors.

learn more… | top users | synonyms

5
votes
3answers
99 views

What is the best way to detect repetition in xyz data for purposes of splitting data?

I'll use this picture to explain What I want to do is define some patterns as trained patterns. Then given data I want to be able to determine if the pattern exists in the dataset, and if it does ...
0
votes
0answers
8 views

Equal number of neighbors from different classes in k-NN algorithm [closed]

I've been trying to find some reasonable answer for I guess very obvious question regarding k-NN and unfortunately I've failed. What I've been looking for is what is happening if we have k = 2 and ...
2
votes
1answer
245 views

k-NN computational complexity

What is the time complexity of the k-NN algorithm with naive search approach (no k-d tree or similars)? I am interested in its time complexity considering also the hyperparameter k. I have found ...
0
votes
0answers
7 views

Many class, one train sample per class classification

I have a classification task involving one train sample per class with around 300 classes.Furthermore each observasion has about 200 features. Can anyone suggest an approach that might work better ...
0
votes
0answers
10 views

Develop classification model, given the k nearest neighbors

I have a data set listing attributes of clients - a combination of ordinal, categorical and interval data. I am also given the 5 nearest neighbors within the data set for and have to essentially ...
1
vote
0answers
26 views

How to calculate the distance in KNN for mixed data types?

when the data is from different types (numerical and categorical) of course euclidean distance alone or hamming distance alone can't help. so i have 2 approaches: standardize all the data with ...
0
votes
0answers
19 views

Nearest neighbor symmetric matrix

I have a k nearest neighbors (kNN) distance matrix for $n$ samples $S_n$, which is a sparse, almost-symmetric matrix with the property $x_{ij} ∈ \{0, x_{ji}\}~∀~i, j ∈ \{1,...,n\}$. A matrix entry $x_{...
0
votes
0answers
14 views

Computing confidence for k-NN class prediction

Is there any sound way to add a confidence measure to the prediction of a k-NN classifier? In my case I have a binary classification problem and the dataset is pretty balanced, with around 50% of ...
0
votes
0answers
11 views

SK Learn with a user defined metric (again)

Someone posted a similar question here but i couldn't get my job done see http://stackoverflow.com/questions/21052509/sklearn-knn-usage-with-a-user-defined-metrgammaic i want to define my ...
0
votes
0answers
23 views

kNN bad performance for iris data set

I've implemented kNN algorithm in Python and now I'am testing it on iris data set. I have two questions. The performance seems to be bad: if I run the program 100 times and then calculate the ...
0
votes
3answers
47 views

Finding the optimal value of k in the k-nearest-neighbor classifier: is this cross-validation?

I have collected 1000 data points with each data point belonging to eight categories. I would like to be able to correctly estimate the categories of any new data by using the k-nearest-neighbor ...
0
votes
0answers
21 views

How does the fraction of retained PCA variance affect the accuracy of a model?

I was checking various tools for classification and optimisation; I trained a sample dataset using KNN. I got 100% accuracy with 95% PCA explained variance and 99.2% accuracy with 5% PCA explained ...
0
votes
0answers
78 views

Discriminant function of 1 Nearest Neighbor

Consider the following question: We will consider the case of 1-nearest neighbor, and look at the details of computing the error probability. In this case, let us assume that we have two classes, $\...
0
votes
1answer
44 views

Comparison of LDA vs KNN time complexity

Which algorithm has a better performance in terms of time complexity, LDA or KNN?
0
votes
0answers
9 views

Nearest neighbours approach variant?

Hi i'd like to know a bit more about kNN-like approach implementations for classification problems, and specifically classification problems where we want to have a probability distribution as an ...
0
votes
0answers
9 views

Explanation on time complexity for nearest neighbor search

My problem is related to the approximate nearest neighbor search. I found a useful link http://cstheory.stackexchange.com/questions/8875/calculating-the-distance-to-the-kth-nearest-neighbor-for-all-...
0
votes
0answers
11 views

kNN used as a metafeature for future ensemble

Lately I've saw a lot of classification approaches for large datasets that involved ensemble methods, most of them using kNN. If I don't miss-understand the algorithm, it is meant to use a portion of ...
0
votes
0answers
12 views

How to add pseudorandom noise into data - too many ties in knn

I have a discrete training data and I amtrying to model it with caret's knn. Then I saw this post: Dealing with lots of ties in kNN model The accepted answer says that we need to add a very small ...
0
votes
0answers
24 views

K-NN Binary classification with boolean features

inexperienced forum user and ML 'user'. I'm trying to shed some light on some data. The feature vector is all booleans (isMale, isAmerican, hasMac etc..) and it is a binary classification problem. (...
0
votes
1answer
46 views

KNN classifier + cross validation

how can I find the mean and standard deviation of error rate or accuracy of a k- fold cross validation performing K-nearest-neighbour classification model for each fold?
1
vote
0answers
36 views

Degree correlation of network

I'm trying to analyze the degree correlation of a given network and I can't understand what is the best way to do it. With degree correlation I mean to find if the network is assortative (hubs ...
0
votes
0answers
11 views

Orientation of point dataset

Looking at the well-known Pine dataset (Numata, 1961) it appears in different articles in different orientations. 1983 Digggle: Then sometimes appears rotated: Or even flipped: Other than ...
0
votes
1answer
113 views

What's a better classifier for simple A-Z letter OCR: SVMs or kNN?

Disclaimer: I'm nearing the end introductory machine course so knowledge on the subject is not too strong (yet)! Context: I'm thinking of building an optical word search solver for a term project ...
0
votes
0answers
21 views

Help in understanding hashing for nearest neighbor search

Hashing is a technique for large- scale visual search and a variety of hashing-based method- s have been proposed Survey paper : Hashing for similarity search . The application of hashing to ...
1
vote
1answer
88 views

On what kind of data (simple example) will KNN outperform linear regression

Linear regression outperforms KNN in simple dataset like a line or a polynomial (say quadratic) I am looking for a simple example where KNN would outperform linear regression. I tried sin and cosine ...
0
votes
0answers
22 views

What are the methods to measure feature relevance

I have implemented K-NN(K-nearest neighbor) algorithm and wanted to apply feature selection/weighting to it. I know some methods to measure the feature relevance such as computing the correlation ...
0
votes
0answers
35 views

Time series pattern recognition tools

I have a matrix of 500 X 12 of time series, represented by each row. The columns being the 12 sampling times. I have also another matrix of 500 X 1 corresponding to 500 time series of which we only ...
1
vote
1answer
74 views

What machine learning model would I use for predicting rainfall given numerical data

I'm brand new to machine learning and am currently taking a course on it. In the course, we have been using things such as gradient boosting, and linear regression to take data that has been collected ...
0
votes
0answers
31 views

kNN: What are the reasonable limits for $k$ to try with CV?

In my Machine Learning module assignment, we are supposed to try out several classification algorithms (kNN among them) and optimise the hyperparameters via a grid search by Cross - Validation. Of ...
4
votes
1answer
36 views

Hypothesis space of Naive Bayes and kNN

I am confused about the hypothesis space of those two classifiers. In the case of linear regression, it's pretty straightforward ; the possible hypothesis are equations of lines, that is, linear ...
0
votes
1answer
75 views

K-nearest neighbour imputation of missing values

I have a dataset where the columns correspond to features and the rows correspond to data points. I have around 5'000 data points and 8 features. Now, I would like to impute the missing values with ...
1
vote
1answer
77 views

Help with Kaggle Data Set

I'm doing the following competition on Kaggle https://www.kaggle.com/c/street-view-getting-started-with-julia/details/knn-tutorial Its data set consists of bmp images of size 20x20 and we are ...
4
votes
2answers
114 views

Simple kNN example

Can someone explain, in very simple way, how can kNN algorithms predict classes of set of points? Is there any resource for beginners to understand algorithms with graph?
0
votes
1answer
124 views

Variables involved in kNNdistplot (dbscan package) in R

I have a time-series of a feature(metric) for 4 different servers each of length 2000. I want to use dbscan algorithm to figure out if all 4 machines fall in the same cluster or not using dbcscan on ...
-2
votes
2answers
82 views

Training a 3 million sample data which has unbalanced labels

I have data which has 3 million samples and unbalanced label. I have tried many neural network approaches, but I couldn't get a good result. Which path do you suggest me to follow in this case, in ...
1
vote
2answers
93 views

PCA not helping in very high dimensional regression using KNN

I am using sklearn.neighbors.KNeighborsRegressor() to train over a set of very high dimensional input (721 dimensions) and continous output (a regression problem). ...
1
vote
1answer
33 views

Margin of k-nearest neighbor classifier [closed]

How can I evaluate the margin of k-nearest neighbor classifier in R? For example, in Matlab exist such function: http://www.mathworks.com/help/stats/classificationknn.margin.html
2
votes
0answers
47 views

A modeling technique combining $k$ nearest neighbors and multiple linear regression

I have been modeling data using a hybrid $k$-nearest neighbors (kNN) and multiple linear regression (MLR) and have found the technique to be (at least with my data) much more accurate than either ...
-1
votes
1answer
143 views

Estimate Epsilon in DBSCAN with k-nearest neighbor algorithm

Following DBSCAN paper (quote below), I'm trying to develop a simple heuristic to determine the parameter Epsilon with K-nearest neighbors (k-NN) algorithm. For a given k we define a function k-...
1
vote
0answers
38 views

How to plot ROC for knn (and potentially kernel spectral regression)

I understand how to plot ROC for logistic classifier (like varies the probability cutoff). For KNN, how can I find the ROC? Also, what about kernel spectral regression?
0
votes
0answers
23 views

Is it possible to sum counts and normalize?

So what happens if you sum counts and then normalize them to use it in k-nearest neighbor (k-NN) analysis? Will this do the trick or should I go look for another method instead of the Euclidean one? ...
0
votes
0answers
30 views

Evaluating performance Neural Network embeddings in kNN classifier

I am solving a classification problem. I train my unsupervised neural network for a set of entities (using skip-gram architecture). The way I evaluate is to search k nearest neighbours for each point ...
0
votes
0answers
37 views

Difference between Nearest Neighbour and Nearest Centroid

I'm trying to understand the difference between Nearest neighbour classifiers and Nearest centroid classifier. Using the nearest neighbour, one selects a data point ...
0
votes
1answer
144 views

Time series analysis for predicting a binary outcome

I'm fairly new to time series analysis. I want to analyze two series of variables in a span of time to predict a binary outcome. For example i collect data over time at my home of two variables: ...
0
votes
0answers
47 views

How to draw a 3 nearest neighbour decision boundary

I have an exam tomorrow, and I can't seem to get my head around how to do this, nor can I find any information online for this particular case of a 3NN decision boundary. We are presented with sets of ...
1
vote
1answer
48 views

Cross Validation and Nearest Neighbors

What is the best way to approach multiple-fold cross validation for a 1 nearest-neighbor model used for prediction? A common approach to cross validation is to, for example, split the dataset into ...
2
votes
1answer
36 views

application of 1-nearest-neighbor

In the book The elements of statistical learning by Trevor Hastie, there is a sentence (on page 17) saying : In fact 1-nearest-neighbor, the simplest of all, captures a large percentage of the ...
1
vote
1answer
135 views

minimizing total travel time [closed]

Green circles are salesman and A-B-C are destination points. I need to move green circles so that total travelled time should be minimum and each salesman should go to a different point. So ideal ...
0
votes
1answer
83 views

kNN speed up using triangle inequality

can someone explain how the triangle inequality helps speed up kNN? I understand the general principle of the triangle inequality, however I don't see how a lower bound on $d(x_1, x_2)$ would help ...
0
votes
0answers
18 views

Dynamic Time Warping finds erroneous similarity between time series

I am implementing 1NN using DTW as the distance measurement. It finds erroneous similarity between two time series when they are actually not similar. To give an example, let's suppose a & b are ...