Sparse computation for large-scale data mining
Sparse computation for large-scale data mining
复制标题
大规模数据挖掘的稀疏计算
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
P. Baumann
中科院分区：
文献类型：
--
作者：
D. Hochbaum;P. Baumann
几个领先的数据挖掘和聚类算法依赖于成对相似性形式的输入。然而，由于潜在的成对相似性的数量在数据集的大小上呈二次方增长，因此将这样的算法应用于大数据集在计算上是禁止的。本文提出了一种新的稀疏计算方法，只计算相关的相似性，而不是完整的相似性矩阵。该方法采用了一种有效的算法，提供了一个“近似的主成分分析”。在生成的低维空间中，应用网格邻域的概念，以识别具有潜在高相似性的对象组。与已知的稀疏化方法不同，稀疏化方法首先生成成对相似性的完整集合，从而花费至少二次时间，稀疏计算方法仅生成相关相似性。稀疏计算可以用于任何需要成对相似性的数据挖掘或聚类算法，例如k-最近邻算法或谱方法。这种方法与基于网格的聚类算法相比，网格邻域的接近度仅用于确定稀疏相似性矩阵中的条目，而不是识别聚类。事实上，对象可以属于同一个网格邻域，但最终在不同的集群，或者相反，属于不同的邻域，但得到集群联合。稀疏计算的二进制分类的适用性证明了这里最近设计的监督归一化割（SNC）。我们的实证结果表明，该方法实现了显着减少的相似性矩阵的密度，从而大大减少了运行时间，同时具有最小的影响（往往没有）的准确性相比，使用一个完整的相似性矩阵的输入。
Several leading data mining and clustering algorithms rely on inputs in the form of pairwise similarities. Yet, since the number of potential pairwise similarities grows quadratically in the size of the data set, it is computationally prohibitive to apply such algorithms to large data sets. This paper addresses this challenge with a novel method of sparse computation that computes only the relevant similarities instead of the complete similarity matrix. The method employs an efficient algorithm that provides an “approximate Principal Component Analysis”. In the low-dimensional space generated, the concept of grid neighborhoods is applied in order to identify groups of objects with potentially high similarity. Unlike known sparsification approaches that generate first the full set of pairwise similarities and thus take at least quadratic time, the sparse computation method generates only the relevant similarities. Sparse computation can be utilized in any data mining or clustering algorithm that requires pairwise similarities, such as the k-nearest neighbors algorithm or the spectral method. This approach is contrasted with that of grid-based clustering algorithms in that grid neighborhoods proximity is used only to determine the entries in the sparse similarity matrix, not to identify the clusters. Indeed objects can belong to the same grid neighborhood while ending up in different clusters, or conversely, belong to different neighborhoods yet get clustered jointly. The applicability of sparse computation for binary classification is demonstrated here for the recently devised supervised normalized cut (SNC). Our empirical results show that the approach achieves a significant reduction in the density of the similarity matrix, resulting in a substantial reduction in running time, while having a minimal effect (and often none) on accuracy as compared to inputs using a complete similarity matrix.