Abstract: The construction of information graph is critical for many machine learning tasks.Based on the sparse representation theory，a directed nonnegative l1-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 l1-minimization problem.Finally，spectral clustering with nonnegative l1-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 l1-graph.

Key words: nonnegative l1-graph, spectral clustering, l1-minimization, handwritten character clustering

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

关键词: 非负l1图, 谱聚类, l1最小化, 手写字符聚类