并行谱聚类的稀疏化方法研究

### 并行谱聚类的稀疏化方法研究 #### 1. 引言 谱聚类是一种重要的无监督学习方法，它能够在没有数据形状和局部性先验信息的情况下对数据进行聚类。传统的谱聚类方法在处理大规模数据集时，面临着计算复杂度高和内存消耗大的问题。为了解决这些问题，人们提出了基于重叠界面的域分解并行策略。不过，该策略在处理大规模数据时，仍然存在谱聚类步骤耗时过长以及内存受限的问题。 为了应对这些挑战，我们研究了并行谱聚类的鲁棒性，引入了稀疏化技术、稀疏结构和适配的特征求解器，以处理更大规模的问题，并在几何示例和图像分割任务中进行了测试。 #### 2. 并行谱聚类 假设我们有一个数据集 $S = \{x_i\}_{i=1..n} \in R^p$，并且已知目标聚类数 $k$。谱聚类的主要步骤如下： 1. **构建亲和矩阵**：基于数据集中点之间的高斯亲和度度量构建亲和矩阵 $A \in R^{n×n}$，公式为： - $A_{ij} = \begin{cases} \exp\left(-\frac{\|x_i - x_j\|^2}{(\sigma/2)^2}\right) & \text{if } i \neq j \\ 0 & \text{otherwise} \end{cases}$ 2. **构造归一化矩阵**：$L = D^{-1/2}AD^{-1/2}$，其中 $D_{i,i} = \sum_{j=1}^{n} A_{ij}$。 3. **提取特征向量**：将与 $L$ 的 $k$ 个最大特征值相关联的特征向量堆叠成矩阵 $X = [X_1 X_2..X_k] \in R^{n×k}$。 4. **归一化矩阵**：对矩阵 $X$ 的每一行进行归一化，得到矩阵 $Y$。 5. **K - 均值聚类**：将矩阵 $Y$ 的每一行视为 $R^k$ 中的一个点，使用 K - 均值方法将它们分为 $k$ 个聚类。 6. **分配原始点**：当矩阵 $Y$ 的第 $i$ 行属于第 $j$ 个聚类时，将原始点 $x_i$ 分配到第 $j$ 个聚类。 该谱聚类方法可以通过域分解进行并行实现，具体步骤如下： - **主进程（Master）**： 1. **预处理步骤**： - 读取全局数据和参数。 - 将数据分割成 $q$ 个子集。 - 计算亲和参数 $\sigma$，重叠带宽固定为 $3 × \sigma$。 2. 向其他处理器发送 $\sigma$ 值和数据子集。 3. 在自己的子集上执行谱聚类算法： - 计算亲和矩阵的谱。 - 确定聚类数 $k$。 - 进行谱嵌入。 4. 接收每个处理器的局部分区和聚类数。 5. **分组步骤**： - 利用传递关系将局部分区合并为全局分区。 - 输出整个数据集 $S$ 的分区和最终聚类数 $k$。 - **从进程（Slave）**： 1. 从主处理器接收 $\sigma$ 值和数据子集。 2. 在自己的子集上执行谱聚类算法。 3. 向主处理器发送局部分区和聚类数。 并行实现的优势在于： - **减少内存消耗**：每个子问题的局部亲和矩阵所需的内存总和远小于全局亲和矩阵所需的内存。 - **降低浮点运算量**：每个子问题的聚类数远小于整个数据集的聚类数，从而减少了特征向量计算的成本。 然而，当局部数据子集的点数过多时，仍然会遇到内存限制问题。 #### 3. 谱聚类的稀疏化 尽管采用了域分解，但谱聚类算法仍然是最耗时的部分。为了解决这个问题，我们研究了阈值化作为稀疏化技术。 ##### 3.1 理论解释