data modeling and machine intelligence - FURTHER UNSUPERVISED LEARNING-CLUSTERING
本节目标:
这些目标聚焦于无监督学习中的聚类相关知识和机器学习的更广泛影响。
聚类
无监督学习的输入是一组无标签的数据(Unlabeled data),表示为 { x i } i = 1 N \{x_i\}_{i = 1}^{N} {xi}i=1N 。这些数据被输入到一个算法模块中,经过处理后,输出数据的结构(Structure)、相关性(Correlations)和模式(Patterns)。
- 聚类(Clustering):是无监督学习的一类方法,它将数据划分或分离成“相似”的组。这意味着聚类算法会根据数据点之间的相似性将它们分组,而不需要事先知道每个数据点的类别。
- 与主成分分析(PCA)的区别:无监督学习与PCA不同。PCA旨在通过找到数据的最大变化方向来寻求数据的低维表示,而无监督学习并不降低维度,只是简单地对数据进行分组。 (因为聚类属于无监督学习,而无监督学习又与PCA不同,所以聚类不属于PCA)
聚类例子
展示聚类应用的一个例子,以肺癌数据为例说明聚类在医学中的应用。
- 数据来源:左侧显示了肺癌数据(Lung cancer data),其特征可能包括DNA(可能导致非常高维的特征空间)、疼痛程度(Level of pain)、粘液颜色(Colour of Mucus)等。
- 聚类结果:右侧展示了聚类后的三种肺癌亚型,分别为Lung cancer subtype A、Lung cancer subtype B和Lung cancer subtype C 。
- 应用目的:这里不是试图预测患者是否患有某种类型的癌症(这是监督学习问题),而是试图识别聚类,这可能会导致发现新疾病。在发现之后,可以开发检测和治疗方法。
聚类可视化
- 划分原则:
- 每个数据点都在其中一个簇内,即 ∪ i = 1 K C i = { x i } i = 1 N \cup_{i = 1}^{K} C_i = \{x_i\}_{i = 1}^{N} ∪i=1KCi={xi}i=1N 。这意味着所有的数据点都能被分配到某个簇中,没有数据点被遗漏。
- 簇与簇之间不重叠,即对于所有 i ≠ j i \neq j i=j, C i ∩ C j = ∅ C_i \cap C_j = \varnothing Ci∩Cj=∅ 。这保证了每个数据点只属于一个簇。
- 数学表示:有时从数学角度将 C i C_i Ci 表示为簇 i i i 中数据的索引集合更方便。也就是说,如果 j ∈ C i j \in C_i j∈Ci,那么 x j x_j xj 在簇 i i i 中。同时有:
- ∪ i = 1 K C i = { 1 , ⋯ , N } \cup_{i = 1}^{K} C_i = \{1, \cdots, N\} ∪i=1KCi={1,⋯,N} ,这是从索引角度说明所有数据点的索引都在这些簇的索引集合中。
- 对于所有 i ≠ j i \neq j i=j, C i ∩ C j = ∅ C_i \cap C_j = \varnothing Ci∩Cj=∅ ,同样强调了簇的索引集合之间不重叠。
- 选择标准:我们希望选择这样的簇,如果 i , j ∈ C l i, j \in C_l i,j∈Cl,那么 x i x_i xi 和 x j x_j xj 是“相似的” 。即同一簇内的数据点具有相似性。
在聚类分析中定义数据点之间相似性 / 相异性的方法
这张图片主要讲解了在聚类分析中定义数据点之间相似性/相异性的方法。
- 相异性定义公式:两个数据点 x , x ~ ∈ R n x, \tilde{x} \in \mathbb{R}^n x,x~∈Rn 之间的相异性定义 D ( x , x ~ ) : = ∑ i = 1 n w i d ( x i , x ~ i ) D(x, \tilde{x}) := \sum_{i = 1}^{n} w_i d(x_i, \tilde{x}_i) D(x,x~):=i=1∑nwid(xi,x~i) 其中:
- w i > 0 w_i > 0 wi>0 且对于所有 x , y ∈ R x, y \in \mathbb{R} x,y∈R, d ( x , y ) ≥ 0 d(x, y) \geq 0 d(x,y)≥0(任何距离/相异性度量都应为正)。
- 对于所有 x ∈ R x \in \mathbb{R} x∈R, d ( x , x ) = 0 d(x, x) = 0 d(x,x)=0(当数据相同时,相异性应为零)。
通常会选择 w i = 1 w_i = 1 wi=1 ,并且 d ( x , y ) = ( x − y ) 2 d(x, y) = (x - y)^2 d(x,y)=(x−y)2 ,这样 D ( x , y ) = ∥ x − y ∥ 2 2 D(x, y) = \|x - y\|_2^2 D(x,y)=∥x−y∥22 ,即平方欧几里得范数。
当特征以不同单位测量,或者某些特征被数据科学家认为更重要时,权重 w i w_i wi 就会发挥作用。
聚类优化问题
- 优化目标:我们希望最小化簇内的平均相异性(average dissimilarity within clusters)。
- 簇内平均相异性公式:簇 C l C_l Cl 内的平均相异性公式:
1 ∣ C l ∣ ∑ i , j ∈ C l D ( x i , x j ) = 1 ∣ C l ∣ ∑ i , j ∈ C l ∥ x i − x j ∥ 2 2 \frac{1}{|C_l|} \sum_{i,j \in C_l} D(x_i, x_j) \\ = \frac{1}{|C_l|} \sum_{i,j \in C_l} \|x_i - x_j\|_2^2 ∣Cl∣1i,j∈Cl∑D(xi,xj)=∣Cl∣1i,j∈Cl∑∥xi−xj∥22 这里选择欧几里得范数作为相异性度量(上面说了),所以进一步写成 1 ∣ C l ∣ ∑ i , j ∈ C l ∥ x i − x j ∥ 2 2 \frac{1}{|C_l|} \sum_{i,j \in C_l} \|x_i - x_j\|_2^2 ∣Cl∣1∑i,j∈Cl∥xi−xj∥22 。其中, ∣ C l ∣ |C_l| ∣Cl∣ 表示簇 l l l 中的元素数量。 - 寻找最优K个簇:为了找到最佳的 K K K 个簇,最小化每个选定簇内平均相异性的总和是合理的。对应的数学表达式为:
- min C 1 , ⋯ , C K ∑ k = 1 K 1 ∣ C k ∣ ∑ i , j ∈ C k ∥ x i − x j ∥ 2 2 \min_{C_1, \cdots, C_K} \sum_{k = 1}^{K} \frac{1}{|C_k|} \sum_{i,j \in C_k} \|x_i - x_j\|_2^2 C1,⋯,CKmink=1∑K∣Ck∣1i,j∈Ck∑∥xi−xj∥22
- 约束条件为: ∪ i = 1 K C i = { 1 , ⋯ , N } \cup_{i = 1}^{K} C_i = \{1, \cdots, N\} ∪i=1KCi={1,⋯,N} (所有数据点都在这些簇中)且 C i ∩ C j = ∅ C_i \cap C_j = \varnothing Ci∩Cj=∅ (簇与簇之间不重叠)。
尝试使用暴力法解决聚类优化
提出问题:有多少个K - 簇?
对于每个数据点,都有K个簇可以分配。因此,几乎有 K × K × ⋯ × K = K N K×K×\cdots×K = K^N K×K×⋯×K=KN 个不同的簇。这里说“几乎”是因为这种计算会重复计算相同的簇,例如, C 1 = { x 1 } , C 2 = { x 2 } C_1 = \{x_1\}, C_2 = \{x_2\} C1={x1},C2={x2} 和 C 1 = { x 2 } , C 2 = { x 1 } C_1 = \{x_2\}, C_2 = \{x_1\} C1={x2},C2={x1} 在这种计算中被当作两种不同的数据划分方式。
对于这几乎 K N K^N KN 个簇中的每一个,我们可以计算每个簇内平均相异性的总和(目标函数)如下,然后找出使这个目标函数最小的簇。 ∑ k = 1 K 1 ∣ C k ∣ ∑ i , j ∈ C k ∥ x i − x j ∥ 2 2 \sum_{k = 1}^{K} \frac{1}{|C_k|} \sum_{i,j \in C_k} \|x_i - x_j\|_2^2 k=1∑K∣Ck∣1i,j∈Ck∑∥xi−xj∥22
顺带一提:
- 当 N = 200 N = 200 N=200 且 K = 6 K = 6 K=6 时,几乎有 6 200 ≈ 4.3 × 1 0 155 6^{200} \approx 4.3×10^{155} 6200≈4.3×10155 个不同的簇。
- 宇宙中大约有 1 0 82 10^{82} 1082 个原子,因此进行如此多的计算是难以处理的(intractable),说明暴力法在大规模数据下计算量过大。
既然暴力法这么拉,那肯定要找一些更好的聚类算法。
K - 均值聚类算法(K - Means Clustering)
上图是一个可视化的例子,显示了在迭代开始(Iteration #0)时的数据点分布情况,数据点被分成了不同颜色的组,代表不同的聚类。
大致算法步骤
- 随机地为每个数据点 x i x_i xi( i = 1 , ⋯ , N i = 1, \cdots, N i=1,⋯,N)分配一个介于 1 1 1到 K K K之间的数。
- 迭代直到聚类分配不再改变:
伪代码示例:
Algorithm: K-means # 初始时随机将数据分配到聚类中, L i 表示数据点 x i 所属的聚类 . Input: { x i } i = 1 N , K ∈ N , L ∈ { 1 , … , K } N , and ε = 1 while ε > 0 do for j = 1 : K do # 计算每个聚类的中心,即聚类中数据的平均值 c j = 1 ∑ i = 1 N 1 { L i } ( j ) ∑ i = 1 N 1 { L i } ( j ) x i end for i = 1 : N do # ε ≥ 0 用于判断在本次循环中任何数据点的聚类分配是否发生了变化。 ε = ∑ i = 1 N ( L i − arg min 1 ≤ j ≤ K ∥ x i − c j ∥ 2 ) 2 # 将数据点分配到最近的聚类中心所在的聚类来更新数据的聚类分配 L i = arg min 1 ≤ j ≤ K ∥ x i − c j ∥ 2 end end Output: c 补充说明: 1 A ( x ) = { 1 , x ∈ A 0 , otherwise 用于判断元素 x 是否属于集合 A 。 x ∗ = arg min x f ( x ) 表示当 f ( x ∗ ) = min x f ( x ) 时, x ∗ 是使函数 f ( x ) 取得最小值的 x 值 \begin{array}{l} \text { Algorithm: K-means }\\ \#初始时随机将数据分配到聚类中,L_i表示数据点x_i所属的聚类.\\ \text { Input: }\left\{x_{i}\right\}_{i=1}^{N}, K \in \mathbb{N}, L \in\{1, \ldots, K\}^{N} \text {, and } \varepsilon=1 \\ \text { while } \varepsilon>0 \text { do }\\ \qquad\text { for } j=1: K \text { do }\\ \qquad\qquad\#计算每个聚类的中心,即聚类中数据的平均值\\ \qquad\qquad c_{j}=\frac{1}{\sum_{i=1}^{N} \mathbb{1}_{\left\{L_{i}\right\}}(j)} \sum_{i=1}^{N} \mathbb{1}_{\left\{L_{i}\right\}}(j) x_{i}\\ \qquad\text { end }\\ \qquad\text { for } i=1: N \text { do }\\ \qquad\qquad\#\varepsilon\geq0用于判断在本次循环中任何数据点的聚类分配是否发生了变化。\\ \qquad\qquad\varepsilon=\sum_{i=1}^{N}\left(L_{i}-\arg \min _{1 \leq j \leq K}\left\|x_{i}-c_{j}\right\|_{2}\right)^{2}\\\\ \qquad\qquad\#将数据点分配到最近的聚类中心所在的聚类来更新数据的聚类分配 \\ \qquad\qquad L_{i}=\arg \min _{1 \leq j \leq K}\left\|x_{i}-c_{j}\right\|_{2}\\ \qquad\text { end }\\ \text { end }\\ \text { Output: } c\\ \\ \text { 补充说明:}\\ \mathbb{1}_A(x)=\begin{cases}1, & x\in A \\ 0, & \text{otherwise}\end{cases} 用于判断元素x是否属于集合A。 \\ x^*=\arg\min_{x}f(x)\text{表示当}f(x^*)=\min_{x}f(x)时,x^*是使函数f(x)取得最小值的x值 \end{array} Algorithm: K-means #初始时随机将数据分配到聚类中,Li表示数据点xi所属的聚类. Input: {xi}i=1N,K∈N,L∈{1,…,K}N, and ε=1 while ε>0 do for j=1:K do #计算每个聚类的中心,即聚类中数据的平均值cj=∑i=1N1{Li}(j)1∑i=1N1{Li}(j)xi end for i=1:N do #ε≥0用于判断在本次循环中任何数据点的聚类分配是否发生了变化。ε=∑i=1N(Li−argmin1≤j≤K∥xi−cj∥2)2#将数据点分配到最近的聚类中心所在的聚类来更新数据的聚类分配Li=argmin1≤j≤K∥xi−cj∥2 end end Output: c 补充说明:1A(x)={1,0,x∈Aotherwise用于判断元素x是否属于集合A。x∗=argminxf(x)表示当f(x∗)=minxf(x)时,x∗是使函数f(x)取得最小值的x值
注意
-
因为K - 均值聚类算法是一种启发式聚类方法(启发式算法介绍),所以K - 均值算法可能收敛到局部最小值,而非全局最优聚类。它是一种比暴力搜索更易于执行的启发式算法。
-
K - 均值算法与之前课程中介绍的用于分类的K - 近邻算法不同。
K-均值聚类例子
考虑数据集 D = { 2 , 3 , 4 , 7 , 12 } D = \{2, 3, 4, 7, 12\} D={2,3,4,7,12},目标是使用K - 均值算法将其划分为 2 2 2个聚类。
- 初始化
初始聚类分配向量 L = [ 1 , 2 , 1 , 2 , 1 ] ⊤ L = [1, 2, 1, 2, 1]^{\top} L=[1,2,1,2,1]⊤,这意味着将数据点 2 2 2、 4 4 4、 12 12 12分配到聚类 C 1 C_1 C1,将数据点 3 3 3、 7 7 7分配到聚类 C 2 C_2 C2,即 C 1 = { 2 , 4 , 12 } C_1 = \{2, 4, 12\} C1={2,4,12}, C 2 = { 3 , 7 } C_2 = \{3, 7\} C2={3,7}。 - 步骤1:计算两个聚类的中心。
- 对于 C 1 C_1 C1, c 1 = 1 3 ( 2 + 4 + 12 ) = 6 c_1=\frac{1}{3}(2 + 4 + 12)=6 c1=31(2+4+12)=6。
- 对于 C 2 C_2 C2, c 2 = 1 2 ( 3 + 7 ) = 5 c_2=\frac{1}{2}(3 + 7)=5 c2=21(3+7)=5。
- 步骤2:根据新的聚类中心重新分配数据点。得到新的聚类分配向量 L = [ 2 , 2 , 2 , 1 , 1 ] ⊤ L = [2, 2, 2, 1, 1]^{\top} L=[2,2,2,1,1]⊤,此时 C 1 = { 7 , 12 } C_1 = \{7, 12\} C1={7,12}, C 2 = { 2 , 3 , 4 } C_2 = \{2, 3, 4\} C2={2,3,4}。
- 步骤3:再次计算两个聚类的中心。
- 对于 C 1 C_1 C1, c 1 = 1 2 ( 7 + 12 ) = 9.5 c_1=\frac{1}{2}(7 + 12)=9.5 c1=21(7+12)=9.5。
- 对于 C 2 C_2 C2, c 2 = 1 3 ( 2 + 3 + 4 ) = 3 c_2=\frac{1}{3}(2 + 3 + 4)=3 c2=31(2+3+4)=3。
- 步骤4:重新分配数据点,聚类分配向量依然是 L = [ 2 , 2 , 2 , 1 , 1 ] ⊤ L = [2, 2, 2, 1, 1]^{\top} L=[2,2,2,1,1]⊤, C 1 = { 7 , 12 } C_1 = \{7, 12\} C1={7,12}, C 2 = { 2 , 3 , 4 } C_2 = \{2, 3, 4\} C2={2,3,4},聚类分配没有发生变化。
- 输出:由于聚类分配不再改变,算法结束,输出两个聚类的中心:
- c 1 = 1 2 ( 7 + 12 ) = 9.5 c_1=\frac{1}{2}(7 + 12)=9.5 c1=21(7+12)=9.5。
- c 2 = 1 3 ( 2 + 3 + 4 ) = 3 c_2=\frac{1}{3}(2 + 3 + 4)=3 c2=31(2+3+4)=3。
K-均值聚类性能评估示例
这张图片展示了一个一维数据集上K - 均值算法的性能评估示例,具体内容如下:
还是上面是数据集:
- 给定数据集 D = { x 1 , x 2 , x 3 , x 4 , x 5 } = { 2 , 3 , 4 , 7 , 12 } D = \{x_1, x_2, x_3, x_4, x_5\} = \{2, 3, 4, 7, 12\} D={x1,x2,x3,x4,x5}={2,3,4,7,12}。
- 使用K - 均值算法将其划分为两个聚类: C 1 = { 7 , 12 } = { x 4 , x 5 } C_1 = \{7, 12\} = \{x_4, x_5\} C1={7,12}={x4,x5}, C 2 = { 2 , 3 , 4 } = { x 1 , x 2 , x 3 } C_2 = \{2, 3, 4\} = \{x_1, x_2, x_3\} C2={2,3,4}={x1,x2,x3}。以索引形式表示为 C 1 = { 4 , 5 } C_1 = \{4, 5\} C1={4,5}, C 2 = { 1 , 2 , 3 } C_2 = \{1, 2, 3\} C2={1,2,3}。
评估指标
评估指标为每个选定聚类内的平均相异度总和。计算公式为:
∑ k = 1 K 1 ∣ C k ∣ ∑ i , j ∈ C k ∣ ∣ x i − x j ∣ ∣ 2 \sum_{k = 1}^{K}\frac{1}{|C_k|}\sum_{i, j \in C_k}||x_i - x_j||^2 k=1∑K∣Ck∣1i,j∈Ck∑∣∣xi−xj∣∣2
其中, K K K是聚类数(这里 K = 2 K = 2 K=2), ∣ C k ∣ |C_k| ∣Ck∣是聚类 C k C_k Ck中的数据点数量, x i x_i xi和 x j x_j xj是聚类 C k C_k Ck中的数据点。
计算过程
- 对于聚类 C 1 C_1 C1: ∣ C 1 ∣ = 2 |C_1| = 2 ∣C1∣=2,数据点为 7 7 7和 12 12 12,则 1 ∣ C 1 ∣ ∑ i , j ∈ C 1 ∣ ∣ x i − x j ∣ ∣ 2 = 1 2 ( ( 7 − 12 ) 2 + ( 12 − 7 ) 2 ) \frac{1}{|C_1|}\sum_{i, j \in C_1}||x_i - x_j||^2 = \frac{1}{2}((7 - 12)^2 + (12 - 7)^2) ∣C1∣1∑i,j∈C1∣∣xi−xj∣∣2=21((7−12)2+(12−7)2)
- 对于聚类 C 2 C_2 C2: ∣ C 2 ∣ = 3 |C_2| = 3 ∣C2∣=3,数据点为 2 2 2、 3 3 3、 4 4 4,则 1 ∣ C 2 ∣ ∑ i , j ∈ C 2 ∣ ∣ x i − x j ∣ ∣ 2 = 1 3 ( ( 2 − 3 ) 2 + ( 2 − 4 ) 2 + ( 3 − 4 ) 2 + ( 3 − 2 ) 2 + ( 4 − 2 ) 2 + ( 4 − 3 ) 2 ) \frac{1}{|C_2|}\sum_{i, j \in C_2}||x_i - x_j||^2 = \frac{1}{3}((2 - 3)^2 + (2 - 4)^2 + (3 - 4)^2 + (3 - 2)^2 + (4 - 2)^2 + (4 - 3)^2) ∣C2∣1∑i,j∈C2∣∣xi−xj∣∣2=31((2−3)2+(2−4)2+(3−4)2+(3−2)2+(4−2)2+(4−3)2)。
- 对上述两部分求和并化简:
1 2 ( ( 7 − 12 ) 2 + ( 12 − 7 ) 2 ) + 1 3 ( ( 2 − 3 ) 2 + ( 2 − 4 ) 2 + ( 3 − 4 ) 2 + ( 3 − 2 ) 2 + ( 4 − 2 ) 2 + ( 4 − 3 ) 2 ) = 2 ( 1 2 ( 7 − 12 ) 2 + 1 3 ( ( 2 − 3 ) 2 + ( 2 − 4 ) 2 + ( 3 − 4 ) 2 ) ) = 29 \begin{align*} &\frac{1}{2}((7 - 12)^2 + (12 - 7)^2) + \frac{1}{3}((2 - 3)^2 + (2 - 4)^2 + (3 - 4)^2 + (3 - 2)^2 + (4 - 2)^2 + (4 - 3)^2)\\ =&2\left(\frac{1}{2}(7 - 12)^2 + \frac{1}{3}((2 - 3)^2 + (2 - 4)^2 + (3 - 4)^2)\right)\\ =& 29 \end{align*} ==21((7−12)2+(12−7)2)+31((2−3)2+(2−4)2+(3−4)2+(3−2)2+(4−2)2+(4−3)2)2(21(7−12)2+31((2−3)2+(2−4)2+(3−4)2))29
这个数值 29 29 29表示在该聚类结果下,所有聚类内的平均相异度总和,用于衡量聚类的紧密程度,数值越小通常表示聚类效果越好。
非唯一性问题
还记不记得K均值算法是启发性算法?启发性算法又被称为试探法,所以在 K - 均值算法中,存在由质心定义的聚类的非唯一性问题。
假设现在考虑问题:寻找与数据点 x i x_i xi距离最近的聚类中心 c j c_j cj的索引. arg min 1 ≤ j ≤ k ∥ x i − c j ∥ 2 \underset{1\leq j\leq k}{\arg\min}\|x_i - c_j\|_2 1≤j≤kargmin∥xi−cj∥2
这个问题就可能存在多个解。这是因为当数据点 x i ∈ R n x_i \in \mathbb{R}^n xi∈Rn与两个或更多聚类中心的距离恰好相等时,就会出多个解。
例如,对于 j ≠ l j \neq l j=l,可能有 { j , l } ∈ arg min 1 ≤ j ≤ k ∥ x i − c j ∥ 2 \{j, l\} \in \underset{1\leq j\leq k}{\arg\min}\|x_i - c_j\|_2 {j,l}∈1≤j≤kargmin∥xi−cj∥2 ,即数据点 x i x_i xi到聚类中心 c j c_j cj和 c l c_l cl的距离都是最小的。
在实现中,当出现上述距离相等的情况时,工程师必须选择一个任意的规则来实现K - 均值算法,这个规则是一个超参数。
在本节中,将采用最小索引的规则。当然还可以选择其他规则,比如将数据点分配到质心最小或最大的聚类(即 ∥ c i ∥ 2 \|c_i\|_2 ∥ci∥2最小或最大的聚类)。总之,这些规则的选择是任意的。
采用最小索引规则:
如果 j ∗ ∈ arg min 1 ≤ j ≤ k ∥ x i − c j ∥ 2 j^* \in \underset{1\leq j\leq k}{\arg\min}\|x_i - c_j\|_2 j∗∈1≤j≤kargmin∥xi−cj∥2 ,并且对于所有 l ∈ arg min 1 ≤ j ≤ k ∥ x i − c j ∥ 2 l \in \underset{1\leq j\leq k}{\arg\min}\|x_i - c_j\|_2 l∈1≤j≤kargmin∥xi−cj∥2 且 l ≠ j ∗ l \neq j^* l=j∗ ,都有 j ∗ < l j^* < l j∗<l ,那么数据点 x i x_i xi将被分配到聚类 j ∗ j^* j∗ 。
用于选择K值的肘部法则
刚刚我们的讨论里,都没有关于如何选择聚类数量的 K K K的问题。对于某些应用,聚类的数量是由问题本身的内在性质决定的:
- 以销售人员分配客户为例进行说明:假设公司有 K K K名销售人员,希望对客户进行聚类,以便为每位销售人员分配相似规模和特征的客户群,从而实现专业化服务。在这种情况下,聚类的数量 K K K就等于销售人员的数量,这样每个聚类对应一位销售人员的客户群体。
随着聚类数量 K K K的增加,通常每个聚类内的平均相异度总和会下降。这是因为更多的聚类意味着每个聚类可以更加精细地划分数据,使得同一聚类内的数据点更加相似,进而导致平均相异度降低。
既然增加聚类数量会使平均相异度下降,那么如何合理地选择聚类数量 K K K呢?
聚类分析中用于选择聚类数量 K K K的肘部法则(The Elbow Method)
假设数据集 { x i } i = 1 N \{x_i\}_{i = 1}^{N} {xi}i=1N存在一些自然形成的聚类 C 1 , ⋯ , C K ∗ C_1, \cdots, C_{K^*} C1,⋯,CK∗ ,其中 K ∗ K^* K∗是数据中真实的聚类数量。
不同 K K K值下的聚类情况
- 当 K < K ∗ K < K^* K<K∗时:某些聚类会包含来自多个自然形成聚类的元素。这会导致每个聚类内的相异度较高,因为不同自然聚类中的元素特征差异较大。
- 当 K > K ∗ K > K^* K>K∗时:某些聚类会对自然形成的聚类进行划分。进一步增加 K K K只会使总相似度有少量下降。这是因为自然聚类中的数据已经比较接近,进一步划分这些聚类只能少量减少相异度。
肘部法则原理
定义 S A D ( K ) = ∑ k = 1 K 1 ∣ C k ∣ ∑ i , j ∈ C k ∥ x i − x j ∥ 2 SAD(K)=\sum_{k = 1}^{K}\frac{1}{|C_k|}\sum_{i, j \in C_k}\|x_i - x_j\|^2 SAD(K)=∑k=1K∣Ck∣1∑i,j∈Ck∥xi−xj∥2,它表示当聚类数量为 K K K时,所有聚类内平均相异度的总和。随着 K K K的增加, S A D ( K ) SAD(K) SAD(K)通常会下降。在 K = K ∗ K = K^* K=K∗处, S A D ( K ) SAD(K) SAD(K)的曲线会出现一个拐点或类似肘部的形状。对于一些数据集,可能没有明显的肘部,所以肘部法则是一种启发式方法,用于帮助用户选择合适的 K K K值。
上图展示了 S A D ( K ) SAD(K) SAD(K)随 K K K变化的曲线。曲线在 K ∗ K^* K∗处出现明显的弯曲,类似肘部,可据此判断合适的聚类数量。但是需要知道,并非所有数据集都有清晰可辨的肘部,该方法只是辅助选择 K K K的一种手段。
K均值聚类的优缺点
优点
与通过暴力搜索找到最优聚类相比,K - 均值算法在计算上更高效。暴力搜索需要穷举所有可能的聚类组合来找到最优解,计算量巨大,而K - 均值算法基于启发式策略,通过迭代计算聚类中心和分配数据点,能在较短时间内得到一个较满意的聚类结果,适用于大规模数据集。
缺点
-
聚类数量选择困难:用户必须自行选择聚类数 K K K,但这是一个主观的选择,只能依靠如肘部法则等启发式方法辅助,没有一种绝对准确的方法来确定最优的 K K K值,不同的 K K K值可能导致不同的聚类结果。
-
易陷入局部最优:算法不一定能收敛到最优的 K K K个聚类。输出的局部最小值在很大程度上取决于聚类数据分配的初始化。不同的初始聚类中心选择可能会使算法收敛到不同的局部最优解,而非全局最优解。
如上图,凸函数图像呈现为一个碗状,只有一个全局最小值;非凸函数图像有多个起伏,存在多个局部最小值,这恰恰说明K - 均值算法因为初始化随机,很可能陷入局部最优的问题。 -
无法处理非凸聚类:K - 均值算法无法处理非凸形状的聚类。因为它基于质心来分配聚类,质心的计算方式会导致聚类结果倾向于凸形状。
凸区域内任意两点连线都在区域内,非凸区域则不满足此条件,K - 均值算法因为计算质心的特性,在处理非凸聚类时的局限性。
实现通用人工智能(AGI)所面临的障碍
这张图片主要探讨了实现通用人工智能(AGI)所面临的障碍,具体内容如下:
- 数据标注瓶颈:
- 摩尔定律的局限性:
- 摩尔定律指出微芯片上的晶体管数量大约每两年翻一番。
- 物理限制的存在给维持当前计算能力的指数级增长带来了不确定性。
- 仅依靠规模扩展可能不是可持续的解决方案,算法和架构方面的创新势在必行。
- 过拟合与算法挑战:
- 封闭与开放游戏及不确定性:
- 区分封闭游戏(规则明确)和开放游戏(具有不可预测性和模糊性)至关重要。
- 人工智能模型处理不确定性的能力是关键挑战,影响其在两种游戏中的表现。
- 像国际象棋、围棋和蛋白质折叠等应用属于封闭游戏,而掌握开放游戏仍然是一个悬而未决的挑战。
- 数据质量与人类偏见: