kNN-algorithm

I still have no idea what I could use this for in OPMO. In Max/MSP, it has interesting und usefull applications in the area of corpus-sampling. I didn’t write this code myself (Copilot), but it seems to fit.

GeeksforGeeks

;; kNN implementation in Common Lisp with weighted voting
;; -------------------------------------------------------
;; This program classifies a new data point based on the k nearest neighbors
;; from a given dataset, giving more weight to closer neighbors.

(defun euclidean-distance (vec1 vec2)
  "Compute the Euclidean distance between two numeric vectors."
  (unless (= (length vec1) (length vec2))
    (error "Vectors must have the same length."))
  (sqrt (reduce #'+
                (mapcar (lambda (a b) (expt (- a b) 2))
                        vec1 vec2))))

(defun knn-classify-weighted (dataset labels query k)
  "Classify QUERY using weighted k nearest neighbors from DATASET with LABELS.
   Closer neighbors contribute more to the vote."
  (when (or (null dataset) (null labels))
    (error "Dataset and labels cannot be empty."))
  (unless (= (length dataset) (length labels))
    (error "Dataset and labels must have the same length."))
  (when (or (<= k 0) (> k (length dataset)))
    (error "Invalid k value."))

  ;; Compute distances and pair with labels
  (let* ((distances (mapcar (lambda (point label)
                              (list (euclidean-distance point query) label))
                            dataset labels))
         ;; Sort by distance
         (sorted (sort distances #'< :key #'first))
         ;; Take k nearest
         (neighbors (subseq sorted 0 k))
         ;; Weighted label counts
         (label-weights (make-hash-table :test #'equal)))
    (dolist (n neighbors)
      (let ((dist (first n))
            (label (second n)))
        ;; Weight: inverse of distance (avoid division by zero)
        (incf (gethash label label-weights 0)
              (if (zerop dist) 1e6 (/ 1.0 dist)))))
    ;; Return label with highest total weight
    (car (car (sort (loop for key being the hash-keys of label-weights
                          collect (list key (gethash key label-weights)))
                    #'>
                    :key #'second)))))

;; Example usage
(let* ((dataset '((1.0 2.0) (2.0 3.0) (3.0 3.0) (6.0 5.0) (7.0 8.0)))
       (labels  '("A" "A" "B" "B" "B"))
       (query   '(2.5 3.0))
       (k 3))
  (format t "Predicted class for ~a: ~a~%"
          query
          (knn-classify-weighted dataset labels query k)))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; GENERATING A 2D-RND_DATASET

(setf dataset_1
      (loop for x from 0.0 to 0.999 by 0.001 
            for y in (gen-noise 1000 :seed 6235)
            collect (list x y)))


;; GENERATING LABELS (a scale, 7 labels)

(setf labels_1 (rnd-sample 1000 (make-scale 'c4 7 :alt '(1 2)) :prob 0.5))
            

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; EXAMPLE

(let* ((dataset dataset_1)
       (labels  labels_1)
       (query   '(0.21 0.112)) ;; what i'm searching (2d)
       (k 5))
  (format t "Predicted class for ~a: ~a~%"
          query
          (knn-classify-weighted dataset labels query k)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;