非负l^1图及其在谱聚类中的应用

Nonnegative l^1 -graph and its application in spectral clustering

信息图的构造对许多机器学习任务来说是至关重要的。基于稀疏表示理论,提出了一种有向非负l1图。在构造此图的过程中,先将每个样例表示成其他样例的非负线性组合,再通过求解l1最小化问题来同时获得近邻样例和对应的相似度。最后将基于非负l1图的谱聚类方法应用于手写字符的聚类问题。与基于l1图的谱聚类方法相比,所提方法具有较好的聚类性能和较低的计算复杂度。

The construction of information graph is critical for many machine learning tasks.Based on the sparse representation theory,a directed nonnegative l 1 -graph is proposed.In the procedure of constructing the graph,each sample is first represented by the nonnegative linear combination of the remaining samples,and then the neighboring samples and the corresponding similarities are simultaneously obtained by solving an l 1 -minimization problem.Finally,spectral clustering with nonnegative l 1 -graph is applied to handwritten character clustering.The experimental results demonstrate that the proposed method has better clustering performance and lower computation complexity compared with spectral clustering with l 1 -graph.