(defun k-means (k data)
  (k-means-prim k (make-array `(,(length data)
                                ,(length (first data)))
			      :initial-contents data)))		   
(defun k-means-prim (k data)
  "k-means: performs a k-means clustering."
  (let ((memberof (make-array (array-dimension data 0)
                              :initial-element nil))
	(oldmemberof (make-array (array-dimension data 0)
                                 :initial-element nil))
	(num.in.cluster (make-array k :initial-element 0))
	(centroids (make-array (list k (array-dimension data 1))
                               :initial-element 0))
	(distances (make-array (list (array-dimension data 0) k)
                               :initial-element nil))
	(tempmin nil)
	(finaldata
         (adjust-array data
                       (list (array-dimension data 0)
                             (+ (array-dimension data 1) 1)))))
    (dotimes (i (array-dimension data 0))
      (setf (aref memberof i) (mod i k))
      (setf (aref num.in.cluster (mod i k))
            (+ (aref num.in.cluster (mod i k)) 1)))
    (dotimes (i (array-dimension data 0))
      (dotimes (j (array-dimension data 1))
	(setf (aref centroids (aref memberof i) j)
	      (+ (/ (aref data i j)
		    (aref num.in.cluster (aref memberof i)))
		 (aref centroids (aref memberof i) j)))))
    (dotimes (iteration (array-dimension data 0) memberof)
      (if (equalp oldmemberof memberof)
	  (return memberof))
      (dotimes (i (array-dimension memberof 0))
	(setf (aref oldmemberof i) (aref memberof i)))
      (setf distances (set-distance-matrix2 data centroids))
      (dotimes (i (array-dimension distances 0))
	(setf tempmin (aref distances i 0))
	(dotimes (j (array-dimension distances 1))
	  (cond ((<= (aref distances i j) tempmin)
		 (setf tempmin (aref distances i j))
		 (setf (aref memberof i) j)))))
      (setf num.in.cluster (make-array k :initial-element 0))
      (dotimes (i (array-dimension memberof 0))
	(setf (aref num.in.cluster (aref memberof i))
              (+ (aref num.in.cluster (aref memberof i)) 1)))
      (setf centroids (make-array (list k (array-dimension data 1))
                                  :initial-element 0))
      (dotimes (i (array-dimension data 0))
	(dotimes (j (array-dimension data 1))
	  (setf (aref centroids (aref memberof i) j)
		(+ (/ (aref data i j)
		      (aref num.in.cluster (aref memberof i)))
		   (aref centroids (aref memberof i) j))))))
    (dotimes (i (array-dimension data 0))
      (setf (aref finaldata i (- (array-dimension finaldata 1) 1))
            (aref memberof i)))
    finaldata))				;end k-means