Questions tagged [k-nearest-neighbour]

A non-parametric method of classification and regression. The input consists of the $k$ closest training examples in the feature space. The output is either the mode of the neighbors (in classification) or their mean (in regression).

Filter by
Sorted by
Tagged with
2 votes
1 answer
34 views

Can we regularize/penalize the KNN model?

While reading through KNN in detail, I was checking if there is a way to improve/penalize KNN? I didn't find any concrete/easily understandable solutions.
user avatar
  • 21
2 votes
1 answer
26 views

How is a distance metric used in KNN when $K$ is given?

I am new to non-paramtric methods. The conditional probability for classification using KNN is gen by: $$ P(y=c|x,D)=\frac{1}{K}\sum_{n\in N_K(x,D)}I(y_n=c) $$ where $N_K(x,D)$ is the set such that $K$...
user avatar
  • 287
0 votes
1 answer
23 views

How to infer nearest neighbors using distance metrics

My team and I are trying to identify group of customers to target for an investment promotion exercise. We decided to use the control group (which already are a part of this investment exercise) and ...
user avatar
  • 101
2 votes
0 answers
33 views

Any theory on whether good choices of $k$ depend on $N$ and $D$ in KNN classification?

I am well aware that cross validation is a usual method for selecting hyperparameters. However, I am looking for theoretical guidance on how to pick $k$, the number of neighbors, for a $k$-nearest-...
user avatar
  • 579
3 votes
0 answers
45 views

How many features/dimensions/variables can K-Nearest Neighbors handle with a finite amount of data?

KNN is an algorithm where the "Curse of Dimensionality" applies extremely literally and directly. Let's take some kind of basic, 50/50 balanced, binary classification problem. I'm wondering ...
user avatar
2 votes
0 answers
63 views

Lower RMSE but worse model prediction

I am using a KNN model to predict quantity sold for a highly seasonal business. I chose KNN because I thought that using nearest neighbors would inform my model about said seasonality better than a ...
user avatar
1 vote
0 answers
19 views

Bootstrapping with 1-NN classifier

Given the naive bootstrap estimate of the error of a classifier defined as: $$\frac{1}{N}\frac{1}{B}\sum_{b=1}^{B}\sum_{i=1}^{N} L(y_i, \hat{c}_b(x_i))$$ Where $L(y, c(x)) = \mathbb{1}\{c(x)=y\}$ is ...
user avatar
  • 113
1 vote
0 answers
93 views

K-fold cross validation for kNN Imputer in Python [closed]

I have a dataset with columns, say, y, x1, x2, x2 and a lot of missing values in x1, x2, x3. I decided to use ...
user avatar
  • 249
0 votes
0 answers
47 views

Why does a Decision Tree algorithm outperform the Random Forest Algorithm in certain cases?

Currently I write my master thesis that deals with the binary prediction of university dropouts (dropout - yes/no). In the thesis, I compare the performance of three different classification ...
user avatar
0 votes
0 answers
10 views

Predictors for Classification Models using caret in R

I have been reading several different resources on classification and I am finding conflicting information. Some literature says caret's train() function assumes all predictors are numeric and the ...
user avatar
  • 185
1 vote
1 answer
179 views

Is there a way to locate automatically the knee of the k-nearest neighbour graph in a DBSCAN analysis? [duplicate]

I am trying to write a function in R that automatically chooses the optimal parameters epsilon and MinPts in a DBSCAN analysis. I found that the k-nearest neighbour plot was very useful in order to ...
user avatar
  • 11
1 vote
1 answer
46 views

Decide which K for KNN-model based on plot

I've been working with a dataset containing handwritten numbers, and to classify what number it is I've used KNN. I've made a plot comparing validation with training misclassification rate for each K =...
user avatar
  • 81
2 votes
0 answers
44 views

K nearest neighbor VS Kernel density estimation (Parzen window)

I appreciate it if anyone could explain to me the advantages and disadvantages of knn and parzen relative to each other.
user avatar
2 votes
1 answer
166 views

Cosine similarity seems to perform better with higher dimensions than Euclidean distance? Should this be the case?

I've generated 100 random vectors (data points) in n∈[1,...,50] dimensions. I then compared distances between each pair of vectors and calculated the mean value. I've done this for all dimensions ...
user avatar
2 votes
0 answers
54 views

How is UMAP a valid dimensionality reduction technique when it uses KNN, which suffers from the curse of dimensionality?

I have not a found a satisfactory, or really any answer, to the following problem that I cannot resolve myself. UMAP is touted as an excellent dimensionality reduction technique by constructing a high-...
user avatar
  • 106
0 votes
0 answers
22 views

Benchmarking a KD Tree vs a VP Tree

Hey so I am currently trying to use both a vp tree and a kd tree on a audio dataset, where i have about 10 features and the dataset consists of 1000 samples. For the KD Tree I use the sklearn package ...
user avatar
  • 1
0 votes
1 answer
61 views

LOF vs k-NN in data with varying density

When the dataset is comprised of regions of varying densities, which technique is more effective for outlier detection Localised Outlier Factor(LoF) or K-Nearest neighbors (KNN)
user avatar
  • 101
1 vote
1 answer
44 views

How to construct training set for anomaly detection?

I am using a K-Nearest-Neighbor calculation as part of an outlier detection method, and I'm trying to decide how to construct the training dataset on which to base my KNN calculation for subsequent ...
user avatar
  • 337
1 vote
0 answers
26 views

2NN classifier with neighbours having different labels

In 2-Nearest-Neighbourhood classifier, given a input x, and 2 neighbours of x have different labels, what can I assign as label for x? (Assuming I am not weighting neighbours based on distance)?
user avatar
  • 11
2 votes
1 answer
59 views

K-nearest-neighbor - relationship between K, parameters and complexity

I want to understand the relationship (if any) between parameters and hyperparameters in a k-nearest-neighbor (KNN) model and how they relate to complexity. Assume A model which should classify ...
user avatar
  • 81
0 votes
0 answers
109 views

Imbalanced classification using K-nearest neighbors classifier

For an NLP classification task I need to train two different classifiers and I've chosen to use a RandomForest and KNeighbors both the scikit-learn implementations. My dataset is strongly imbalanced. ...
user avatar
  • 239
0 votes
1 answer
97 views

Bayes error and nearest neighbor classification

Upon studying for my midterm using Pattern Classification by Richard O. Duda, David G. Stork, Peter E.Hart (2001), I stumbled upon the following exercise: Using the solutions manual written by David ...
user avatar
  • 1
0 votes
0 answers
103 views

How to get probabilities from KNN with cross-fold validation using caret::train in R

I am confused about the output of train() with knn models in R. My code below uses the Caravan data set, which comes included in the ISLR2 library: ...
user avatar
3 votes
1 answer
324 views

Why does error rate of kNN increase when k approaches size of training set?

I've been experimenting with the effect that different values of k have on the generalisation error of kNN classifier, and I've gotten some unexpected results towards the end when k approaches the ...
user avatar
0 votes
0 answers
16 views

What is the underlying intuitions behind the boundary bias problem?

I am trying to understand why k-nearest neighbors estimations suffer from bias at the boundary point of support. As far as I know, this is also true for kernel and random forest methods. If possible, ...
user avatar
2 votes
2 answers
42 views

Does KNN fail if the test data have no epsilon close nearest neighbors to the training data?

If I have binary-classification data and a Euclidean metric, and I know the best number of nearest neighbors, then I draw circles on my training data based on my K-value which tell me which regions ...
user avatar
  • 224
0 votes
0 answers
9 views

Approximating the pdf at a sampled point using k-nearest neighbours?

I'm reading a (more or less classical) paper on Nearest-neighbour approximations to Entropy. At some point in the paper, given $N$ samples $X_1,...X_N$ from a $p$-dimensional random variable $X$ with ...
user avatar
  • 239
4 votes
2 answers
59 views

Why $\sum^C_{c\neq c^*}P(c|x)[1-P(c|x)]+p^*(1-p^*) \leq (C-1)\frac{1-p^*}{C-1}[1-\frac{1-p^*}{C-1}]+p^*(1-p^*)?$

I have the following theorem in my textbook: As the number of samples goes to infinity the error rate of 1-NN is no more than twice the Bayes error rate. Proof sketch: Abbreviate notation $P(c|x) := P(...
user avatar
5 votes
1 answer
66 views

Describe a situation where a training point can be removed without affecting the resulting 1-NN classification for any test point in the input space

I have the following question in my textbook: One of the drawbacks of the nearest-neighbour algorithm is that we must retain all of the training data. Describe a situation where a training point can ...
user avatar
0 votes
0 answers
35 views

1-NN classifier error rate achieving the Bayes classifier error rate example

I have a theorem in my textbook: Theorem: As the number of samples goes to infinity the error rate of a 1-NN classifier is no more than twice the Bayes error rate. I.e. The expected (Bayes) error of ...
user avatar
1 vote
0 answers
83 views

K-nearest neighbor with kernel gives me the exact same accuracy with different initial conditions (R,caret)

...
user avatar
  • 43
0 votes
0 answers
26 views

how to find the right number for a training set for machine learning

I would like to develop a machine learning algorithm using the knn model to perform a classification of my data records. My question is: is there a general method to follow to determine how large my ...
user avatar
0 votes
0 answers
28 views

How to build a predictive model to predict Temperature values using voltage values for generated for 1 second

I have a dataset which has voltage values for 1 second sampled each millisecond and number of rows = 200 X = [T1, T2, T3,... T1000] ( each in milli Volt) Y = Target (in Celsius) ----id------| T1(mV)|...
user avatar
7 votes
0 answers
107 views

Proof: Nearest Neighbor classifier achieves Bayes rate asymptotically on countable domains

I am trying to understand in which situations the 1-NN classifier asymptotically attains the Bayes error rate. My intuition is that if the domain is countable, then 1-NN will asymptotically do as well ...
user avatar
  • 236
0 votes
0 answers
72 views

How to find the best value of K in KNNImputer?

I have a dataset having missing values and I want to impute/fill these missing values with KNNImputer from sklearn. But in that imputer how can I know that what should be the value of K. In the case ...
user avatar
0 votes
0 answers
23 views

Any advice on parameter tuning on large dataset for KNN and SVM using R

I am pursuing KNN and SVM models on a somewhat large dataset (80k training observations, 360k test observations, 23 features). I randomly picked some values of k between 1 and sqrt(n) and only testing ...
user avatar
  • 1
3 votes
1 answer
55 views

Training error when k=N in KNN

I know the training error of k=1 is 0 because k=1 is basically picking itself as the closest point. However, what would be the training error if k=sample size? Say if there are 20 reds and 30 blues, ...
user avatar
1 vote
1 answer
40 views

Two types of kNN classifier algorithm

The following is copy-pasted from a lecture note on machine learning... k-NN classification can be realized in two ways: Selecting for the classified sample it's $k$ nearest neighbors for each class ...
user avatar
  • 1,518
1 vote
1 answer
14 views

What does the KNNclassifier do differently from the KNNregressor?

While I understand how KNNregressor will fit a line to data by taking the k nearest neighbors to a point and averaging them, I am having more trouble understanding what KNNclassifier does with respect ...
user avatar
5 votes
1 answer
560 views

Why is $k = \sqrt{N}$ a good solution of the number of neighbors to consider?

In $k$-NN it is often stated that a good starting number of neighbors to select is $k = \sqrt{N}$ , where $N$ is the total number of points. But why is this so? Examples: Section 10.2.3.2: "When ...
user avatar
  • 287
-1 votes
2 answers
582 views

Mean Accuracy and Standard Error of the Accuracy for KNN Classification algorithm

The given below code snippet is from the assignment of online course IBM ML with Python. Here's the assignment. The used variable names :mean_acc and ...
user avatar
0 votes
1 answer
41 views

K-Fold Cross Validation for K'-NN when K' greater than number of samples in each fold

I'm trying to evaluate the predictive power of a K'-NN algorithm for regression. My idea is to use K-Fold Cross Validation, but the problem is: what happens if I have a K' higher than the number of ...
user avatar
0 votes
0 answers
4 views

Algorithm to sqeeze a location structure

I'm looking an algorithm to squeeze the structure of the location of some items. The item are sensors that have a fixed location x,y on a floormap.and I want to sort them in an array like to be able ...
user avatar
  • 101
0 votes
0 answers
87 views

Given specificity and sensitivity, how do we get ROC value for KNN [R]

I trained a KNN model with k fold cross validation, and I got the following results. I know how specificity and sensitivity are calculated, but the ROC value I don't know. How is that estimated? For ...
user avatar
  • 1
0 votes
0 answers
77 views

KNeighborsClassifier Score with a precomputed user defined distance matrix

I am trying to implement a KNN from SKLEARN using an user defined distance matrix. I want to know which n_neighbors is giving the minimum error for my dataset. So, to avoid long calculation for ...
user avatar
  • 1
3 votes
1 answer
62 views

Speed up Nearest Neighbour classification in highly duplicated data

I have a classification problem on a data set with 3 features and 2,000,000 examples. I have decided that I want to use K-Nearest Neighbors. Is there a way I can leverage the fact that the data only ...
user avatar
1 vote
0 answers
21 views

KNN Distance measures [duplicate]

Why in KNN Euclidean distance is preferred over Manhattan for low dimension dataset whereas for high dimension, manhattan is preferred?
user avatar
0 votes
1 answer
235 views

What values of k in knn classifiers lead to overfitting and underfitting?

I am working on one of the common practice datasets "Breast Cancer" to create a model based on kNN classifiers. I am trying to find the number of k which leads to overfitting or underfitting ...
user avatar
0 votes
0 answers
10 views

Track peaks of two or more moving pulse generators

I want to disentangle the signals of two or more moving pulse sources using recordings of these pulses (see pictures). Example plots (4 panels per example to stretch the x axis a bit, the peaks of ...
user avatar
1 vote
1 answer
23 views

How to avoid a model bias to perform differently depending on the data split?

Example: trying to predict grades (regression) based on a specific group of students' grades on different subjects. When performing random cross-validation, one sees that some models outperform the ...
user avatar

1
2 3 4 5
11