В принципе, между ними мало общего, кроме того, что похожи названия и в обоих случаях используются все данные с расстояниями между ними. KNN это алгоритм с учителем, а k-средних -- без учителя.
Кроме того, у алгоритмов разные цели.
KNN -- это алгоритм классификации, то есть, задачей алгоритма является вычисление класса, к которому относится (новый) образец когда известны классы старых образцов.
Например, этот алгоритм может определять пол человека по росту.
Для этого все обучающие данные записываются в базу и для каждого нового образца смотрятся его k ближайших соседей и он считается относящимся к тому классу, к которому относятся большинство из них.
То есть, для нового человека будет браться k людей, близких ему по росту и его пол будет считаться таким, к которому принадлежит большинство из них. То есть, более низкорослых людей алгоритм будет относить к женщинам, а более высокорослых -- к мужчинам. Посередине алгоритм будет часто ошибаться.
k-средних -- это алгоритм поиска кластеров, где k -- их количество. Этот алгоритм начинает со случайного расположения центров кластеров, затем итеративно обновляет их положение с учётом имеющихся данных. Алгоритм не должен знать классы, к которому относятся образцы.
Например, этот алгоритм можно опять-таки натравить на рост людей и он постарается найти два средних роста среди них. Попадут ли в эти кластеры мужчины и женщины -- я сомневаюсь.