基于L1范数的k平面聚类算法设计

基于L2范数度量的k平面聚类(k-Plane Clustering,k PC)设计思想,本文提出了一种采用L1范数度量的聚类算法。由于在平面更新步骤中,所导出的优化问题是非凸的,文中给出了一种求解方法,即将非凸问题转化为有限个子集上的凸问题,为避免求解多个优化问题导致训练时间过长问题,本文还设计了一种新的优选策略,有限个子集的搜索任务可在线性时间内完成。本文所提出的方法只需要求解k个线性规划,而不再是k PC的求解特征值问题。在人工和UCI数据集上的实验结果表明:基于L1范数平面聚类算法的训练和测试时间更短,且在大多数数据集上均表现出了更好的聚类性能。

k Plane Clustering Algorithm Based on L1 Norm

Inspiring by the k-plane clustering (kPC) on L2 norm metrics, a L1 norm clustering algorithm is proposed by introducing L1 metric into clustering, which is termed as L1 kPC (k-plane clustering using L1 norm). The plane-updating of L1 kPC can be characterized by a nonconvex optimization problem. An alternative strategy is provided to conquer such non-convexity. That is, the nonconvex problem can be transformed into a series of convex problems on a finite number of subsets. Meanwhile, in order to avoid solving multiple optimization problems on individual subsets thereby resulting in heavy training burden, a search strategy is also provided to seek suitable subset and this search task can be completed in a linear time. Thus the foresaid optimization problem only needs to solve k linear programming instead of solving the k eigenvalue problems in kPC. Experimental results on artificial and UCI datasets show that the proposed method has less training and testing time-consume, and comparable or even better clustering performance on the majority data sets.