k-均值問題是經典組合優(yōu)化問題, 也是著名的NP-難問題之一, 相應的Lloyd算法是數(shù)據(jù)挖掘的 十大經典算法之一. k-均值問題在人工智能、數(shù)據(jù)挖掘、理論計算機科學、運籌學和管理科學中有 著廣泛的應用. 本書介紹k-均值問題及其變形的基于隨機抽樣、降維、核心集、近似質心集、局部 搜索、線性規(guī)劃舍入等技術的近似算法. 主要內容包括: 經典k-均值問題的近似算法, k-中位, 球面 k-均值, 魯棒k-均值, 帶約束的k-均值, 隱私保護k-均值, k-均值的其他變形等.