K means 聚类

假设

有kk个subset C1,C2,C3,...,CkC_1, C_2, C_3, ... , C_k，有1,...,n1, ..., n个数据点，且所有数据点满足以下条件：

  1. 每个点都属于一个cluster
  2. 每个cluster都互不重叠

定义距离

Z(C1,⋯ ,Ck)=∑l=1k12∣Cl∣∑i,j∈Cl∥xi−xj∥22Z ( C _ { 1 } , \cdots , C _ { k } ) = \sum _ {l = 1 } ^ { k } \frac { 1 } { 2 | C _ { l } | } \sum _ {i , j \in C _ { l }} { \| x _ { i } - x _ j\|_2 ^ { 2 }}

where ∣Ck∣|C_k| denotes the number of observations in the kth cluster.

目的是最小化每个cluster的pairwise squared distance

Z(C1,⋯ ,Ck)=∑l=1k∑i∈Clk∣∣xi−μl∣∣22Z ( C _ { 1 } , \cdots , C _ { k } ) = \sum _ { l = 1 } ^ { k } \sum _ { i \in C_l } ^ { k } | | x _ { i } - \mu_l | | _ { 2 } ^ { 2 }

其中，

ul=1∣Cl∣∑i∈Clxiu _ { l } = \frac { 1 } { | C _ { l } | } \sum _ { i \in C _ { l } } x _ { i }

迭代目标

min⁡c1,⋯ ,ckZ(C1,⋯ ,Ck)\operatorname { m i n } _ { c _ { 1 }, \cdots , c _ { k } } Z ( C _ { 1 } , \cdots , C _ { k } )

算法｜Lloyd’s algorithm

不一定是最优的，因为如果initialize给的点不好的话，会导致结果收敛到一个次优的聚类

  • input：x1,x2,...,xkx_1, x_2, ..., x_k
  • initial：C1,C2,...,CkC_1, C_2, ..., C_k
  • loss function

Z(C1,⋯ ,Ck)=∑l=1k12∣Cl∣∑i,j∈Cl∥xi−xj∥22Z ( C _ { 1 } , \cdots , C _ { k } ) = \sum _ {l = 1 } ^ { k } \frac { 1 } { 2 | C _ { l } | } \sum _ {i , j \in C _ { l }} { \| x _ { i } - x _ j\|_2 ^ { 2 }}

  • 如果还没有converge，

    1. update centroids
    2. update clusters

选择一：决定k的大小

如果Zk+1<<ZkZ_{k+1}<<Z_k，则有必要增加这个k，即k→k+1k\rightarrow k+1

即找到loss function-k函数中所谓的knee的位置

选择二：决定初始聚类分配initial cluster assignment

  • 每个人都尝试几个随机的初始聚类分配点，然后从中找到Lloyd’s algorithm下最小的那个结果
  • 或者通过k-means ++的方法：随机选择第一个数据点作为中心，然后根据已选中心的距离加权的分布来选择后续的中心

Decision boundaries

通过两个cluster centroids μl\mu_l, μl′\mu_{l'}计算{x∈Rd  ∣  ∣∣x−μl∣∣2=∣∣x−μl′∣∣2}\{x\in \mathbb{R}^d\ \ |\ \ ||x-\mu_l||_2 = ||x-\mu_{l'}||_2\}可以计算得到

参考资料

https://www.cs.cornell.edu/courses/cs4780/2022sp/notes/LectureNotes04.html

声明：此blog内容为上课笔记，仅为分享使用。部分图片和内容取材于课本、老师课件、网络。如果有侵权，请联系aursus.blog@gmail.com删除。