一种基于密度值动态变化的流数据聚类方法

摘要

本发明提供一种基于密度值动态变化的流数据聚类方法，该方法为采用历史流数据集D中所有点对之间的距离确定数据结构CluCell的半径r；对于新增流数据，采用密度中心聚类算法建立基于密度值动态变化的流数据聚类模型；根据新增流数据与数据结构CluCell的距离关系和新增数据与离群点的距离关系，更新流数据聚类模型，从而处理新增流数据；该方法不仅能对任意形状的流数据进行聚类，而且能够发现流数据聚类过程中所发生的聚类生成、合并与分裂的变化，用户可以根据检测到的聚类结果变化，该算法在执行聚类的过程中还能够检测出离群点，离群点往往是系统中产生的错误数据等，通过检测到的离群点可以判断系统是否发生故障。

主权项

一种基于密度值动态变化的流数据聚类方法，其特征在于，包括以下步骤：步骤1：采用历史流数据集D中所有点对之间的距离确定数据结构CluCell的半径r；步骤1.1：将历史缓存的K个流数据组成历史流数据集D；步骤1.2：计算历史流数据集D中各点对之间的距离；步骤1.3：将历史流数据集D中各点对之间的距离值从小到大进行排序，选取前A％处的值作为数据结构CluCell的半径r，其中1<A<2：步骤2：对于新增流数据，采用密度中心聚类算法建立基于密度值动态变化的流数据聚类模型：步骤2.1：设定数据结构CluCell的个数阈值M；步骤2.2：接收当前到达的流数据点p，判断当前是否存在数据结构CluCell，若是，执行步骤2.3，否则，执行步骤2.5；步骤2.3：根据当前时刻对当前所有数据结构CluCell进行密度衰减，寻找距离流数据点p最近的数据结构CluCell c_k，并确定其距离d_pk；步骤2.4：判断距离d_pk与数据结构CluCell的半径r的大小关系，若d_pk≤r，则执行步骤2.6，若d_pk>r，则执行步骤2.5；步骤2.5：以流数据点p为中心建立数据结构CluCell c_p，删除流数据点p，执行步骤2.7；步骤2.6：将距离流数据点p最近的数据结构CluCell c_k的密度值加1，删除流数据点p，返回步骤2.2；步骤2.7：统计当前数据结构CluCell的个数N是否达到数据结构CluCell的个数阈值M，若是，执行步骤2.8，否则，返回步骤2.2；步骤2.8：计算当前所有数据结构CluCell的斥群值，根据当前所有数据结构CluCell的密度值和斥群值绘制数据结构的决策图；步骤2.9：根据数据结构的决策图确定密度中心点，将所有密度中心点的斥群值中的最小值作为最小斥群值δ_min；步骤2.10：根据当前所有数据结构CluCell的斥群值的依附关系得到以密度中心点为根的树状结构，即聚类树，所有聚类树组成一个流数据聚类模型；步骤3：根据新增流数据与数据结构CluCell的距离关系和新增数据与离群点的距离关系，更新流数据聚类模型，从而处理新增流数据；步骤3.1：设定时间阈值Δt；步骤3.2：接收当前到达的流数据点p'；步骤3.3：根据当前时刻对当前所有数据结构CluCell进行密度衰减，并删除在时间阈值Δt内没有插入流数据的数据结构CluCell；步骤3.4：寻找距离流数据点p'最近的数据结构CluCell c_k'，并确定其距离d_p'k'；步骤3.5：判断距离d_p'k'与数据结构CluCell的半径r和最小斥群值δ_min的大小关系，若d_p'k'≤r，则执行步骤3.6，若r<d_p'k'≤δ_min，则执行步骤3.7，若d_p'k'>δ_min，则执行步骤3.8；步骤3.6：将距离流数据点p'最近的数据结构CluCell c_k'的密度值加1，删除流数据点p'，执行步骤3.11；步骤3.7：以流数据点p'为中心建立数据结构CluCell c_p'，删除流数据点p'，执行步骤3.9；步骤3.8：将流数据点p'插入到暂时存放离群点的离群点池中，执行步骤3.12；步骤3.9：计算离群点池中各离群点到数据结构CluCell c_p'的距离d_p'o，若存在Z个d_p'o≤r的离群点，则将数据结构CluCell c_p'的密度值加该Z个离群点的新鲜度，删除该Z个离群点，若存在Z'个r<d_p'o≤δ_min的离群点，则以该Z'个离群点为中心建立数据结构CluCell，删除该Z'个离群点；步骤3.10：更新各数据结构CluCell的斥群值，并根据更新后的各数据结构CluCell的斥群值更新聚类树，返回步骤3.2；步骤3.11：寻找流数据点p'最近的离群点o'，并确定其距离d_p'o'；步骤3.12：判断距离d_p'o'与数据结构CluCell的半径r和最小斥群值δ_min的大小关系，若d_p'o'≤r，则执行步骤3.13，若r<d_p'o'≤δ_min，则执行步骤3.14，若d_p'o'>δ_min，则返回步骤3.2；步骤3.13：以流数据点p'为中心建立数据结构CluCell c_p'，将数据结构CluCell c_p'的密度值加上离群点o'的新鲜度，删除离群点o'和流数据点p'，返回步骤3.9；步骤3.14：以流数据点p'为中心建立数据结构CluCell c_p'，以离群点o'为中心建立数据结构CluCell c_o'，删除离群点o'和流数据点p'，返回步骤3.9。