基于等式约束的高维数据多分类问题的归一化割改进算法

Improved Normalized Cut Algorithm for Multi Classification of High-dimensional Data Based on Equality Constraints

本文对归一化割(NC, Normalized Cut)进行了改进,在能量泛函中引入了度平衡约束以提高模型的约束能力。经典的NC是实现平衡约束的一种重要方法,通过平衡约束来克服通过最小割算法进行数据分类的平凡解问题。但NC的平衡约束能力是不够的,尤其是当数据集不平衡时,约束能力会进一步下降,以此为基础提出了本文的模型。改进后的模型还可以扩展到解决不平衡的多分类问题。在解决不平衡的二分类和多分类问题时,实验结果表明,本文改进的归一化割方法比原始模型具有更高的分类精度和保持平衡的能力。此外,与原来的归一化割方法相比,在保真度集规模很小的情况下,改进的归一化割模型可以实现有效的数据分类。

In this paper, we improved the normalized cut(NC) method, and the degree balance constraint is introduced into the energy functional to improve the constraint ability of the model. The classical NC method is an important method to realize balance constraint, which overcomes the trivial solution problem of data classification by the minimum cut algorithm. However, the NC balance constraint capacity is not enough, especially when the data set is unbalanced, the constraint ability will decline further. Based on this, the model in this paper is proposed. The improved model can also be extended to solve the unbalanced multi-classification problem. The experimental results show that the improved normalized cut method has higher classification accuracy and balance ability than the original model. In addition,compared with the original normalized cut method, in the case of a very small fidelity set size, the modified Normalized Cut can realize effective classification.