基于路径跟随方法的光滑子区间K均值聚类算法

A Smooth Subinterval K-means Clustering Algorithm Based on Path-following Method

时间序列聚类是数据挖掘领域的热点问题之一。结合时间序列的特点,光滑子空间K均值聚类算法在进行稀疏型聚类的同时,可以筛选出连续的时间子区间,并基于这些子区间上的观测对时间序列聚类,其复杂度主要取决于更新聚类权重的方法。然而,现有算法中聚类权重的更新是通过凸二次规划问题求解完成的,其计算复杂度较高。文章的理论推导表明,可以通过复杂度较低的严格凸二次规划问题的求解来更新聚类权重。在此基础上,给出了计算复杂度更低的路径跟随方法来更新聚类权重。数据模拟表明了基于路径跟随方法的新算法在聚类中的有效性,及其在计算速度上的优越性。

Time series clustering is one of the hot issues in data mining. Combined with the characteristics of time series,smooth subinterval K-means clustering algorithm can select continuous time subintervals while sparse clustering, and cluster time series based on observations on these subintervals, andits complexity mainly depends on the method of updating the clustering weight. However, the update of clustering weight in the existing algorithm is solved by convex quadratic programming problem,which has high computational complexity. The theoretical derivation in this paper shows that the clustering weight can be updated by solving a strict convex quadratic programming problem with low complexity, and that on this basis, a path-following method with lower computational complexity is proposed to update the clustering weight. Data simulation shows that the new algorithm based on path-following method is effective in clustering and advantageous in computing speed.