類似のデータ同士を１つのクラスタにまとめていく教師なし学習である。
特徴空間においてk個のデータを包有する距離εの球の中で、多数を占める属性をもって分類を行う。
kは通常固定なので、与えられるεによってデータの粗密が分かる。データがある確率密度に従うのであれば、未知のデータが属するクラスタの発生確率は距離εで分かることになる。
εが大きければ発生確率は低く、情報量は大きくなる。これを応用して異常度検出に用いることができ、カットオフは距離εで決める。
教師あり学習ほどではないが分類精度は高く、性能比較の意味もあってよく用いられる。
画像をそのまま処理することは行わないので、特徴量抽出と選択が重要である。
分類のみならず特徴量抽出にも用いられる。