英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
基于主成分分析的K-means聚类
Chris Ding Xiaofeng He
劳伦斯伯克利国家实验室，计算研究部，伯克利，CA 94720
摘要
主成分分析（PCA）是一种广泛使用的无人监督维数缩减的统计技术。K-means聚类是用于执行无监督学习任务的常用数据聚类。这里我们证明了主成分是K-means聚类的离散聚类隶属度指标的连续解。被导出的K-means目标函数的新下限是总方差减数据协方差矩阵的特征值。这些结果表明，非监督维数减小是密切相关的无监督学习。讨论以下几个影响。关于维数减小，结果提供了新的见解，这种见解是观察到的基于PCA的数据缩减的有效性，超越了常规噪声降低解释，PCA通过奇异值分解提供了数据的最佳低维线性近似。在研究时，结果表明了K-means数据聚类的有效技术。为了说明我们的结果，分析了DNA基因表达和互联网新闻组的例子。实验表明，最佳值的新界限在0.5-1.5％内。
- 介绍
数据分析方法对于分析不断增长的大量高维数据至关重要。一方面，聚类分析（Duda等，2000; Hastie等，2001; Jain和Dubes，1988）试图通过将数据点分成不相交的组，快速地通过数据以获得一级知识，到相同的簇的数据点是相似的，而数据点属于不同的簇是不同的。 最流行和有效的聚类方法之一是K-means方法（Hartigan和Wang，1979; Lloyd，1957; MacQueen，1967），其通过优化平方误差函数使用原型（质心）来表示聚类。（K-means和相关的ISODATA方法详细地描述在（Jain和Dubes，1988）中给出，也参见（Wallace，1989）。
另一方面，高维数据通常通过主成分分析（PCA）（Jolliffe，2002）（或奇异值分解）转换为较低维数据，其中可以更清楚地检测相干模式。这种无监督的维度减少用于非常广泛的领域，例如气象学，图像处理，基因组分析和信息检索。还常见于PCA用于将数据投影到较低维子空间，然后在子空间中应用K-means（Zha等人，2001）。在其他情况下，数据嵌入在低维空间中，例如图形拉普拉斯算子的本征空间，然后应用K-means（Ng等人，2001）。
基于PCA的维数缩减的主要基础是PCA选取具有最大方差的维数。数学上，这相当于通过奇异值分解（SVD）找到数据的最佳低秩近似（在范数中）（Eckart和Young，1936）。 然而，这种降噪特性本身不足以解释PCA的有效性。
在本文中，我们探讨这两种广泛使用的方法之间的联系。我们证明主成分实际上是K-means聚类方法中的聚类隶属度指标的连续解，即PCA维度缩减根据K-means目标函数自动执行数据聚类。这提供了基于PCA的数据简化的重要理由。
我们的结果还提供了有效的方法来解决K-means聚类问题。K-means方法使用K原型聚类的质心来表征数据。它们通过最小化误差平方和来确定，
其中是数据矩阵,是聚类的质心，是中的点数。 K-means的标准迭代解遇到一个众所周知的问题：随着迭代的进行，由于更新算法的贪婪性质，解决方案被困在在局部最小值中（Bradley and Fayyad，1998; Grim等人，1998；Moore，1998）.
关于PCA的一些符号说明。 X表示原始数据矩阵; 其中,,表示中心数据矩阵,这里。协方差矩阵（忽略因子1/n）为。主方向和主成份是特征向量，满足：
,, (1)
这些是Y的SVD的定义方程：（Golub和Van Loan，1996）。的元素是主方向上的数据点的投影值。
2.双向聚类
首先考虑K = 2的情况。给出
是两个簇,之间的平方距离的总和。在一些代数后，我们获得
(2)
和
(3)
这里的是一个常数，因此最小的相当于最大的(。此外，我们可以展示
(4)
将式（4）代入式（3），我们看到总是正的。 我们总结这些结论在
定理2.1 对于K = 2，K-means的最小化聚类目标函数等于距离目标的最大化，其总是为正。
备注.（1）在中，第一项表示最大化的簇间距离的平均值; 这迫使得到的簇尽可能分离。 （2）第二和第三项代表将被最小化的平均群内距离; 这迫使所得到的簇尽可能紧凑。这也从等式(2)中显而易见。（3）因子n1 n2促进簇平衡。由于，意味着最大化，这导致。
这些备注给出了K-means聚类的一些见解。然而，定理2.1的首要重要性是通过主成分得到一个解。
定理2.2。 对于K-means聚类，其中，簇指示符向量的连续解是主成分，即簇由下式给出
, (5)
K-means目标的最优值满足边界
(6)
证明。考虑平方距离矩阵，其中。让簇指示符向量为
该指示符向量满足和是零，正则化条件：。可以容易地看到。如果我们忽略q必须取两个离散值中的一个的限制，并且令q取[-1,1]中的任何值，则的最小化的解由特征向量对应于等式的最低（最大负）特征值。
使用中心距离矩阵D是将离散值指示符q更好地松弛为连续解，即减去D的列和行均值。令，其中
(8)
其中,,现在我们有,因为等式（8）中第2，第3和第4项在中贡献为零。因此，期望的簇指示符向量是对应于的最低（最大负）特征值的特征向量。
通过构造，这个中心距离矩阵具有很好的属性，每个行（和列）总和是零，对于。因此，是具有特征值的的特征向量。由于的所有其他特征向量都与e正交，即,所以它们具有和为零的性质，,所以它们具有和为零的性质,初始指示矢量q。相反，的特征向量不具有该属性。
用一些代数，，代入式(8)，我们得到或者。
因此，簇指示矢量的连续解是对应于最大（正）特征值，其根据定义恰好是主成分。明确地，，其中是协方差矩阵的主特征值。通过式（2），我们得到上的界限。
图1说明了主成分如何确定K均值聚类中的聚类隶属度。一旦是根据式（5）通过主成分确定，我们可以计算当前的聚类方式并迭代K-means，直到收敛。这将使集群解决方案达到局部最优。我们将称之为PCA指导的K-means聚类。
图1（A）2D空间中的两个集群。 （B）主成分，展示出每个元素i的值。
3.K-way 聚类
以上我们集中在使用单个指示符向量的情况。这里我们使用指示符向量来概括。
正则化松弛
这种一般方法首先在（Zha等，2001）中提出。在这里，我们提出一个扩展和一致的松弛方案和连通性分析。首先，在方程(2)的帮助下，可以写成
(9)
第一项是常数。第二项是表示群内（内积）相似性的矩阵的K个对角块元素的总和。
聚类的解由K个非负指示符向量表示：，其中
(10)
（不失一般性，我们对数据进行索引，使得每个簇内的数据点相邻。）由此，等式(9)变为
(11)
其中。在中有冗余。例如，。因此，一个是其他的线性组合。我们通过(a)对:执行线性变换T来消除冗余：
,h或者, (12)
其中是正交矩阵：，并且(b)要求T的最后一列是
(13)
所以我们总是有
.
这种线性变换总是可能的（见后文）。 例如，当K = 2时，我们有
, (14)
并且，这正是方程(7)的指标向量。在中这种K-way聚类的方法是K = 2聚类的泛化。
，如果; 否则为0）的相互正交性意味着的相互正交性,
。
令，上述正交性关系可以表示为
, (15)
,对于 (16)
现在，K-means目标可以写成
(17)
注意，不区分原始数据和居中数据。 重复以上对的推导，我们有
(18)
注意，因为Y的行是中心的。第一项是不变的。的优化成为
(19)
受限于式(15)、(16)的约束，附加约束条件是是如等式(12)中的的线性变换。如果我们忽略最后一个约束，即让取连续值，同时仍然保持约束等式(15)、(16)，则最大化问题可以以闭合形式求解，具有以下结果：
定理3.1。 当优化K-means目标函数，用于变换的离散群成员指示符向量的连续解是K-1个主成分：。满足上下限
(20)
其中是总方差，是协方差矩阵的主特征值。
注意，等式(16)的约束自动得到满足，因为e是具有和特征值不同的特征向量之间的正交性的的特征向量。这个结果对于任何K是成立的。对于，它减少到sect;2里介绍的。
证明是Ky Fan（Fan，1949）（下面的定理3.2）对公式(19)的优化问题的公知定理的直接应用。
定理3.2。 （Fan）设A是具有特征值和对应的特征向量 的对称矩阵。 受限于约束的的最大化具有解 ，其中R是任意正交矩阵，max。
式（11）首先在（Gordon和Henderson，1977）以稍微不同的形式指出，作为的审稿人意见，并及时驳回。它在（Zha等人，2001）中被重新发现，其中应用频谱松弛技术[到等式(11)而不是等式(18)]，导致的K个主特征向量作为连续解。本方法具有三个优点：
（a）在式(11)中的上的直接忽略，不如等式(18)的上的忽略所期望的那样理想。这是因为满足通常PCA分量的总和为零属性，而不满足。离散指示符向量的项具有正值和负值，因此更接近连续解。另一方面，离散指示符向量的条目仅具有一个符号，而的所有特征向量（除之外）都具有正值和负值。换句话说，的连续解将显着不同于其离散形式，而的连续解将更接近其离散形式。
（b）本方法与在sect;2中使用单个指示符向量呈现的情况和情况一致。对于的方程（11）的松弛将需要两个特征向量；这与sect;2中的单指标向量方法不一致。
（c）式（11）中的松弛方法使用了原始数据，而本方法使用了中心矩阵。使用使得正交性条件方程(15)、(16)一致，因为e是的特征向量。此外，与协方差矩阵密切相关，是统计中的一个中心主题。
恢复K个群集
一旦计算了个主成分，如何恢复非负群集指标，难道还是集群本身吗？
显然，由于，每个主成分具有许多负元素，因此它们与非负群集指示符基本不同。因此，关键是计算等式(12)中的正交归一变换T.
正交变换等效于K维空间中的旋转; 存在具有约束的个元素（Goldstein，1980）;剩余的个自由度最方便地由欧拉角表示。对于K = 2单旋转指定变换; 对于K = 3，三个欧拉角确定旋转等。在K-means问题中，我们要求T的最后一列具有式(13)的特殊形式; 因此，真实自由度为.对于并且解是固定的; 它在等式(14)中给出。对于并且我们需要通过2-D空间搜索以找到最佳解，即找到将将变换为非负指示符向量的T矩阵。
使用欧拉角来指定高维空间中的正交旋转与特殊约束通常是复杂的。这个问题通过以下表示，给定任意和为一的正数，并且。与我们的问题中的自由度相同。我们形成以下矩阵：
,
其中
(21)
可以看出对于任何都有。因此，对称矩阵是半正定的。具有非负特征值的实值的K个特征向量：，其中。显然，式(13)的是特征值的的特征向量。其他K-1特征向量是相互正交的，。在一般条件下，Z是非奇异的，。因此，Z是等式(12)中的期望的正交变换T.。总结这些结果，我们有
定理3.3。 等式(12)的线性变换T由等式(21)指定的的K个特征向量形成。
这个结果表明K-means聚类减少到具有参数的优化问题。
PCA连接分析
通常，计算变换T是困难的，计算也是困难的。这里我们提出一种绕过T的方法。我们尝试恢复。而不是像前一节那样从主成分中恢复。从公式(12)，我们得到,其中是等式(12)中的那些离散值指示符。这里不需要T的确切形式。现在这些被它们的连续解，即主成分代替。 一旦计算，我们可以很容易地形成
其中我们忽略了常数项。
注意，具有清晰的对角块结构，这自然导致连接解释：如果，则,在同一个簇中，我们说它们是连接的。我们进一步将i，j之间连通性的概率关联为。 显然，,。对角块结构是簇的特征结构。
如果数据具有清楚的簇结构，则由于主成分是离散值指示符近似的事实，所以我们期望P具有类似的对角块结构以及一些噪声。例如，P可以包含负元素。因此，如果,则设。此外，具有较小正值的P中的元素具有不太好的连接性，其应
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[26456]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
