Why are k-means and k-NN considered simple algorithms in machine learning?

Question

We all know the k-means clustering algorithm and the k-nearest neighbors algorithm: the former is an unsupervised clustering method, and the latter is a supervised learning technique in machine learning.

We all know that they both are simple algorithms, and we can explain easily how they work.

Even though most of people in machine learning consider them simple algorithms, why are they simple algorithms? What are the scientific reasons that make them simple? How to define simplicity in machine learning algorithms?

Answer 1

You can put some numbers to answering this question. In general, k-means and kNN are fairly old algorithms, which may be one of the reasons for this.

For k-means, I reference you to Complexity

and this paper Time Complexity of K-Means and K-Medians Clustering Algorithms in Outliers Detection. There is als a more friendly post The Cost Function of K-Means

Vanilla kNN, for large data sets, has a large computational cost. There is an old post on kNN complexity: k-NN computational complexity

You can then compare that with something like recurrent Neural Networks. Here is a paper on the complexity analysis Bounds on the complexity of recurrent neural network implementations of finite state machines

Answer 2

I don't think there's an exact agreed upon consensus about what makes a model simple vs complex, even though everyone would agree a decision tree is simpler model than a deep layered ANN.

In general I think classification comes down to a number of ideas rather than anything specific. For example models which are easier to understand and interpret can be said to be properties of simpler models, as are those that are explicitly white box vs. black box. However sometimes a k-NN or k-means clustering result can be very hard to interpret, especially if the number of factors is large, so ease of implementation is also considered important for simplicity as these models are generally easy to implement.

In addition models which have fewer constraints in implementation can also be considered complex as they are required to work on the general case, i.e. models which constrain data to be from certain distributions and only work on certain dependency assumptions can be quite simple (simple linear models vs. GLMS). Models which build upon the foundations of other models are inherently more complex, i.e. decision trees vs. random forests.

There are probably many more factors which go into it, runtime to a lesser extent for the more CS inclined (or maybe something so naïve as when the model was published as the literature evolves over time and lends itself to developing further and further complicated models).

In general it's an amalgamation of a bunch of these general features.

Maybe building a classification or regression model on this problem and doing some variable analysis and telling us which variables are the most important in determining the general consensus of simplicity in machine learning algorithms might be the best way to go to getting a true answer. (Go to the wiki, either see if the model is considered "simple" or "complex" or give it a value if you want to do regression, do the same for an interpretability variable, implementation variable, date of publishing variable, etc. tell us the results)