In my opinion it seems fairly obvious that a $k$ nearest neighbours (KNN) Classifier would be fairly expensive in terms of memory, as the model is the training set itself. However, any notes I've read have only mentioned that the KNN-Classifier is computationally expensive, and have not mentioned any memory requirements as a disadvantage. I assume this to be true, but I wouldn't want to mention it in any exams or anything without proper confirmation. Are the memory requirements implicit and not worth mentioning, or am I overlooking something?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ You seem to be assuming that "computationally expensive" refers only to running time and not memory. I'm not sure that's a good assumption. $\endgroup$– David RicherbyCommented Jan 6, 2015 at 14:56
-
$\begingroup$ I did consider this upon writing the question, but upon looking up the definition, it did still seem to refer to just the running time. However, it's probably sensible to assume that computationally expensive does actually refer to the memory requirements as well, which would explain why there is no mention of memory in any notes I've read. I'll take this as an answer unless someone can provide proper clarification. $\endgroup$– SammdahammCommented Jan 6, 2015 at 15:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
KNN is a memory intensive algorithm and it is already classified as instance-based or memory-based algorithm. The reason behind this is KNN is a lazy classifier which memorizes all the training set O(n) without learning time (running time is constant O(1)).
Inversely, When it comes to querying new points to find the nearest K, the query time will be expensive O(n) in terms of the running time.
-
$\begingroup$ We need to add indexing for k-nn into the the fit function of KNN classifiers in libraries like scikit learn. They do nothing in fit, then when you run the function that does the classification, it loads all the data in memory and crashes in my case. Ex: vldb.org/conf/2001/P421.pdf $\endgroup$ Commented Aug 15, 2018 at 13:07