Isotropic PCA and Affine-Invariant Clustering
Isotropic PCA and Affine-Invariant Clustering
复制标题
DOI：
10.1109/focs.2008.48
复制
发表时间：
2008-04
期刊：
影响因子：
--
通讯作者：
Charles Brubaker;S. Vempala
中科院分区：
文献类型：
--
作者：
Charles Brubaker;S. Vempala
提出了一种扩展的主成分分析（PCA）算法，并在此基础上提出了一种新的Rn空间点聚类算法，该算法的关键特性是具有仿射不变性.当输入是来自两个任意高斯的混合的样本时，该算法正确地分类样本，仅假设两个分量可由超平面分离，即，存在一个半空间，其中包含一个高斯的大部分，而几乎没有其他的概率质量。这几乎是最好的可能，大大改善了已知的结果。对于k>2的分量，该算法只要求存在某个（k-1）维子空间，其中每个方向上的“k”都很小。我们的主要工具是各向同性变换，光谱投影和一个简单的重新加权技术。我们称这种组合为各向同性PCA。
We present an extension of principal component analysis (PCA) and a new algorithm for clustering points in \Rn based on it. The key property of the algorithm is that it is affine-invariant. When the input is a sample from a mixture of two arbitrary Gaussians, the algorithm correctly classifies the sample assuming only that the two components are separable by a hyperplane, i.e., there exists a halfspace that contains most of one Gaussian and almost none of the other in probability mass. This is nearly the best possible, improving known results substantially. For k>2 components, the algorithm requires only that there be some (k-1)-dimensional subspace in which the ``overlap'' in every direction is small. Our main tools are isotropic transformation, spectral projection and a simple reweighting technique. We call this combination isotropic PCA.