主成分分析和谱聚类 详义.ppt

可能方法 利用矩阵表示相似性图 利用线性代数… 谱图理论 分析代表图的矩阵的“谱” 谱 :图的特征向量，根据它们相应的特征值幅值排序 矩阵的特征值和特征向量提供了结构的全局信息 邻接矩阵(A) n x n 矩阵 : 节点xi and xj之间的边权 x1 x2 x3 x4 x5 x6 x1 0 0.8 0.6 0 0.1 0 x2 0.8 0 0.8 0 0 0 x3 0.6 0.8 0 0.2 0 0 x4 0 0 0.2 0 0.8 0.7 x5 0.1 0 0 0.8 0 0.8 x6 0 0 0 0.7 0.8 0 0.1 0.2 0.8 0.7 0.6 0.8 0.8 1 2 3 4 5 6 0.8 重要特性 对称阵 特征值为实数 特征向量可以按正交基展开 Degree matrix (D) n x n 对角矩阵 : 入射到xi边权和 重要应用: 归一化邻接矩阵 x1 x2 x3 x4 x5 x6 x1 1.5 0 0 0 0 0 x2 0 1.6 0 0 0 0 x3 0 0 1.6 0 0 0 x4 0 0 0 1.7 0 0 x5 0 0 0 0 1.7 0 x6 0 0 0 0 0 1.5 0.1 0.2 0.8 0.7 0.6 0.8 0.8 1 2 3 4 5 6 0.8 Laplacian 矩阵 (L) n x n 对称矩阵 x1 x2 x3 x4 x5 x6 x1 1.5 -0.8 -0.6 0 -0.1 0 x2 -0.8 1.6 -0.8 0 0 0 x3 -0.6 -0.8 1.6 -0.2 0 0 x4 0 0 -0.2 1.7 -0.8 -0.7 x5 -0.1 0 0 0.8- 1.7 -0.8 x6 0 0 0 -0.7 -0.8 1.5 0.1 0.2 0.8 0.7 0.6 0.8 0.8 1 2 3 4 5 6 0.8 L = D - A Laplacian matrix (L) n x n对称阵 0.00 -0.06 0.00 -0.39 -0.52 1.00 0.00 0.00 0.00 -0.50 1.00 -0.52 0.00 0.00 -0.12 1.00 -0.50 -0.39 -0.44 -0.47 1.00 -0.12 0.00 0.00 -0.50 1.00 0.47- 0.00 0.00 -0.06 1.00 -0.50 -0.44 0.00 0.00 0.00 0.1 0.2 0.8 0.7 0.6 0.8 0.8 1 2 3 4 5 6 0.8 将二分问题(A,B) 表示为一个向量 The laplacian is semi positive The Rayleigh Theorem shows: The minimum value for f(p) is given by the 2nd smallest eigenvalue of the Laplacian L. The optimal solution for p is given by the corresponding eigenvector λ2, referred as the Fiedler Vector. c Laplacian matrix Some definitions: Define f as follows Only the vertex that have edge between them from different set would be meaningful For each edge the sum is on the diagonal Hence it would be equal to zero only than vol(s)=vol(s’) now it could definite as From simple algebra.. The relaxation method is for each vector on Eigen value worth Because the min of eigenvalue is 0 it doesn’t give us any information ,and that’s why its bw(g)=2nd eigenvalue 预处理 构造表示数据集的矩阵表示 分解 计算矩阵的特征值和特征向量 基于1个或更多的特征值将点映射到低维表示 分类 基于新的低维表示进行分类.