基于奇异值分解的单位球面聚类算法优化

杜科君

（中国矿业大学徐海学院计算机系 江苏省徐州市 221000）

简单来说，奇异值分解（SVD）是一种矩阵分解方法，用于将矩阵简化为其组成部分，以使某些后期矩阵计算更容易。特征分解从半正定矩阵扩展到任意 m×n 矩阵。

SVD 能够提供具有最大奇异值的单位奇异向量，它解释了数据点的最大方差，这符合我们的要求。这里，令M为m×n数据矩阵，其行可以代表样本，列可以代表变量。U是m×m正交矩阵，∑是m×n对角矩阵。V是一个n×n正交矩阵，U和V分别称为左奇异向量和右奇异向量。

这里满足UU=VV=I，Σ=diag(σ,…,σ), σ≥σ≥…≥σ，σ是 M 的奇异值，按照惯例以非递增顺序排列。奇异值 σ与特征值相似，σ 减小得很快，因此大矩阵 M 被分解为三个矩阵。

此外，如果向量 v 是矩阵 A 的特征向量，它可以写成Aν=λν。此处λ是特征向量v的特征值，矩阵的特征向量集合由正交向量组成。根据典型公式，两边同时平方，当矩阵为二维时，由于M向量矩阵由行向量组成，指的是每一个行向量，可以进一步写成：

几何上也可以理解成SVD分解的过程，通过单位圆半径的变换，认为是椭圆的椭圆的两个半轴。如图1所示。

图1：奇异值分解过程

通过数据的 SVD 处理，可以用一个小得多的数据集来表示原始数据集，从噪声数据中提取相关特征，这实际上是去除了噪声和冗余信息，从而实现了优化。

1 目标

在此项目中，笔者提出了一种基于SVD和k-means的聚类方法，用于单位超球面上的数据条目，以解决两个问题，即

（1）找到同一单位球面上的集群代表；

（2）将相对于超球面中心对称的数据条目分组到同一个簇。

确定项目需求后，我将球面上的点可视化，展示了一个二维球面上的对称点之间的关系，并在此基础上进行扩展。

本次指导性研究的主要目的是研究降维聚类算法在球体上的具体应用，可归纳如下：给定欧几里得L空间中单位(L-1)超球面上的一组点X，将X划分为K个簇，使得：每个簇有一个同一个超球面的质心来表示簇，满足(a)；每个点被分类到最合适的簇，满足(b)。

2 现有的样本点聚类算法

如今，聚类分析已广泛应用于多种应用，包括模式识别、数据分析、图像处理和市场研究。现有的聚类方法有很多，如层次聚类、k-means聚类、基于密度的聚类等。在大多数情况下，这些方法能够有效地执行聚类。

但是，当数据空间的维度很高（例如，数百甚至数千）时，其中一些方法可能效率低下甚至失败。在这种情况下，通常使用基于 SVD 的主成分分析对数据集进行降维，然后才能进行聚类。

除了区分和分组数据条目之外，聚类分析还可以帮助在每个集群中寻找具有代表性的条目来代表该集群中的所有条目，可以通过选择从所有数据条目的每个维度的平均值计算的质心来完成。

但是，它可能无法在特定情况下找到合适的代表，例如所有数据条目都位于超球面上，并且代表也必须位于同一个球面上。

此外，当考虑到数据对称性并且期望彼此对称的条目属于同一个簇时，经典聚类无法进行聚类。本报告的目的是选择 SVD 对数据点进行聚类。

2.1 层次聚类

层次聚类是一种聚类算法，它通过计算不同类别数据点之间的相似度来创建层次嵌套的聚类树。层次聚类算法可以是凝聚的也可以是分裂的，这取决于层次划分是“自下而上”还是“自上而下”。

优点之一是数据集的聚类可以在不同的尺度（层次结构）上显示。层次聚类试图将样本数据集划分为不同的“层次”，并将它们逐层聚类。

在建立过程中，可以通过第二步设置阈值。当最近的两个类之间的距离大于阈值时，认为迭代终止。

然而，层次聚类的局限性是显而易见的。计算复杂度太高，算法的执行时间大大延长，无法追溯处理。因此，当解决大量数据时，不推荐使用这种聚类算法。

2.2 基于K-means的聚类

K-means 的空间要求适中，因为只存储数据点和质心。得到N个待聚类的样本和待聚类的数量K（K

因此，第一次结束迭代，下一步就是看本次迭代能否达到你设定的目标（即迭代终止条件），如果达到则集群结束，否则继续下一次迭代。

下一次迭代是重新计算聚类中心点（可能是样本数据点），然后计算其他点与新聚类中心的距离并重新选择类别。这将依次迭代，直到达到设定的终止条件。

这种方法快速且易于实施，但缺点也很明显。首先，你需要设置其中的几个 k 值，但是你不知道应该确定多少 k 值，而不知道数据。虽然这里K-means导出的目标形式和上面SVD介绍的表达式是一样的，但是K-means实际上并没有做 SVD。

K-means要求误差分布，即误差服从标准正态分布。传统的K-means算法在聚类过程中，聚类数K的取值难以确定，聚类结果受初始中心的影响，它具有对噪声敏感和不稳定的弱点。

因此，K-means在处理非标准正态分布数据集时会产生较差的聚类效果。此外，每次迭代后都要重新计算每个点到质心的距离，然后进行排序，时间成本很高。

3 系统建模与结构

通过比较三种数据聚类方法，我选择了SVD算法。SVD作为一种非常基础的算法，在很多机器学习算法中都有自己的形象，尤其是在当前大数据时代。因为SVD可以实现并行化，所以功能更加强大。

3.1 SVD算法的广泛应用

现在SVD有很多应用，可以说SVD是矩阵分解、降维、压缩、特征学习的基础工具。因此，SVD在机器学习领域非常重要。此外，SVD 是一种具有明显物理意义的方法。它可以通过乘以更小更简单的子矩阵来表示更复杂的矩阵。

3.1.1 SVD在推荐系统中的应用

基于 SVD 的推荐系统应该结合向量相似度的计算方法，找到与被推荐用户相似的用户项目分数进行推荐或找到比被推荐用户评分更高的项目。

推荐系统的简单版本可以计算物品或相似度。假设可以使用矩阵A中的维度来表示某用户的相关信息。通过SVD计算机，可以生成U、S、V三个矩阵。

此时，先来简单选择k=2来降低U、S、V的维数。如果k=2，说明数据集中包含两个不可见的因素：

将降维后的U、S、V相乘得到A'。通过矩阵A和A'的比较，可以直观地看出这两个矩阵非常相似，可以看作是一种数据有损压缩。

首先我用公式p'=p*U'*S'*V'推导出用户的二维向量，然后计算余弦相似度得到用户评分向量与新用户最相似。这样就可以根据向量q填充向量p，也就是预测。

将SVD用于推荐系统可以使推荐结果准确，而且模型的扩展性也很强，可以应用于各种场景。然而，SVD模型的可解释性较差，隐性因素无法对应现实生活中的具体概念。模型的训练速度还有待提高。

3.1.2 SVD在图像处理中的应用

这些较小数量的奇异值（奇异向量）用于表示可能比较大的事物，因此在图像压缩等方向上有很多应用。在图像处理领域，奇异值不仅可以应用于数据压缩，还可以应用于图像去噪。

如果图像包含噪声，我们有理由相信较小的奇异值是由噪声引起的。当这些较小的奇异值被强制为0时，它们可以去除图片中的噪声。

比如说一张 25*15 的图片，通过奇异值分解，可以发现矩阵的奇异值分别为：14.15, 4.67, 3.00, 0.21, ..., 0.05。除前三个奇异值外，其他奇异值彼此相比都很小。将这些小的奇异值强制为0，然后只用前3个奇异值构造新矩阵，可以得到噪声减少后的图片。

3.2 SVD算法的考虑

通过以上两个应用的介绍，SVD算法具有很好的适用性，所以我把它应用在自己的问题：“在计算中使用矩阵的SVD，而不是原始矩阵，具有对数值误差更稳健的优势。”

SVD将一个复杂的变换分解为三个简单的基本变换（旋转、缩放、投影），奇异值的大小代表对应奇异向量的缩放程度。奇异值越大，这个奇异向量对最终空间的影响就越大。因此，SVD可用于压缩图像或去噪。

因此，我借用了SVD算法来求基。另外，与之前的模型相比，SVD更适合这个主题的需求。此外，每个碱基在生成列时的权重也不相同。通常情况下，某些基本权重特别大，而另一些则特别小，使用SVD时可以获得该值。

对于现在要解决的问题，特点是对称点也可以组合在一起，可以找到代表点。使用我之前介绍的方法也无法满足此要求。

但是，SVD也存在一些问题。矩阵Σ只有对角元素从大到小排列。在科学和工程领域，一直有一个普遍的事实，即在一定数量的奇异值r之后，其他奇异值都被设置为零。这意味着数据集中只有r个重要特征，其余都是噪声或冗余数据。

在这个项目中，我想对球体上的样本点进行聚类。上一篇文章中提到了很多聚类方法，但是其中SVD方法可以找到代表点。在绘图过程中，我可以清楚地看到对称点的关系。这一优势是基于其强大的应用性能。

具体来说，当数据很多时，奇异值分解的计算量会很大，而矩阵的大小只与属性的个数有关。

对比这几种算法，前三种不能反映样本点的对称性。SVD很好地解决了这个问题。

4 方法论和算法

从这部分开始，我将讨论处理单位球面上点的聚类问题的项目概要和方法论。

基于前面的目标，我们的分析步骤如下：

（1）使用SVD算法得到每个样本的类别号。

（2）结合第一步得到样本数最多的类号。

（3）根据第二步得到的类号提取该类的样本数据。

（4）对第三步得到的样本数据，进行SVD分析，得到最大特征向量模的指标。

4.1 仿真数据的确定

在实现算法之前，我首先导入一个模拟数据包。在这里，我指定 m=3 并假设 k≥3。

在程序开始时，我定义了一个 m×n 矩阵 x，其中 n 表示维度，m 表示样本数。

首先，我将球面上需要聚类的点簇分为两种情况，一种是非对称的，一种是对称的。我将数据训练分为两个阶段。在第一阶段，我选择了 3*20 的数据进行模拟。

在对少量数据的代码进行了模拟测试后，我随机生成了100个数据并绘制出来。

4.2 对应样本数据的提取

第一步，我定义了一个标签来表示数据的类别号。我需要获取每个样本的类别号。这里我对矩阵x中的数据进行归一化，然后将所有样本的类别标签初始化为-1。初始迭代次数为 1。

当所有的样本都分类后，就停止迭代，因为如果还有该类的样本，肯定有标签-1<0。在这里，我使用了循环语句。然后我得到样本数据和没有类别的数据的列数。如果样本数小于1，直接退出。

从而得到没有标签的样本索引号，继续进行 SVD 并返回到三个矩阵。其中，u矩阵的数据依次集中、转置、标准化。

得到类别总数 k 和中心点 c。类号设置好以后，值一样的时候就可以直接跳出。

对样本数最多的簇中包含的所有样本数据进行SVD，得到最大特征向量模的索引。

4.3 绘制3D图形

在对数据进行聚类后，我添加了绘图代码并绘制了立体图像。

5 初步性能分析

收集阅读相关文章后，成功运行代码。并验证了项目要求。该部分主要展示最终结果，并对结果进行分析，指出不足之处。

5.1 结果简要分析

在整个代码中，我两次使用了 SVD 算法。第一次是对分散的数据进行聚类，得到每个样本的类别号。第二次是获取样本数据后的计算。得到对应的数据后，我对数据进行标准化，得到最终的矩阵。

值得一提的是，在计算聚类点时，我选择了一个高斯拟合，b1,b2代表拟合模型的平均浮动范围。此外，方程可以列为Xμ=μ+ε其中εi为噪音。

代码运行成功后，得到最大迭代次数为2以及如图2所示。

图2：生成的图像

在第一张图中，我尝试将 100 个模拟数据分成一个簇，图形不是很明显。

在第二张图片中，三种颜色代表三个不同的集群。可以看出，在单位球面上，样本点分为三类。对称性也可以体现出来。以圆心为球心，球面上各点对称。

5.2 假设算法的局限性和潜在优化

该算法的局限性在于，由于两个集群相对于所选择的奇异向量对称的可能性，集群可能是不明确的。由于只分析了100个模拟数据，结果图像看聚类情况不是很清楚。

如果有机会，我会添加更多数据进行验证（例如，大于1000）。此外，在数据处理过程中会产生一些噪声，这可能会导致结果不准确。此外，算法的性能也需要优化，目前的算法效率不高。

6 结语

通过这篇论文，我意识到了自己对机器学习理解肤浅的缺点。本人对算法理解有一定障碍，相关知识点存在很多盲点。在下一阶段，我将学习更多关于机器学习和数据分析的知识。