一种基于网格的加强聚簇边缘检测的混合属性数据流聚类方法

摘要

一种基于网格的加强聚簇边缘检测的混合属性数据流聚类方法，包括如下步骤：1)网格预处理过程：将数据对象所在d维的数据空间进化划分，由于混合属性包含数值型属性和分类型属性，将每一维数值型数据按照网格粒度的大小划分为P个等分的区间，再将每一维分类型数据按其域内可能取值数量进行划分，将数据空间划分为若干互不相交的超方体，每一个矩形网格单元描述为S_1,j1×S_2,j2×...×S_d,jd，其中属性S_i,i＜d为数据空间S上的一个属性，下标j_i表示在S_i该维上所取得的区间；2)在线网格维护过程；3)离线聚类过程。本发明提供了一种聚类质量较高、处理边缘网络能力较强的基于网格的加强聚簇边缘检测的混合属性数据流聚类方法。

主权项

一种基于网格的加强聚簇边缘检测的混合属性数据流聚类方法，其特征在于：所述聚类方法包括如下步骤：1)网格预处理过程：将数据对象所在d维的数据空间进化划分，由于混合属性包含数值型属性和分类型属性，将每一维数值型数据按照网格粒度的大小划分为P个等分的区间，再将每一维分类型数据按其域内可能取值数量进行划分，将数据空间划分为若干互不相交的超方体，每一个矩形网格单元描述为S_1,j1×S_2,j2×...×S_d,jd，其中属性S_i,i＜d为数据空间S上的一个属性，下标j_i表示在S_i该维上所取得的区间；2)在线网格维护过程2.1当新数据点到达时，按照新数据点每一维上对应的数据，将其映射到相应的网格中。假设数据对象x＝(x₁,x₂,...,x_d)被映射到单元网格g(x)＝(j₁,j₂,...,j_d)，则对于x的任意一维必然满足若在现有的网格中匹配不到对象网格，则新建一个网格，将数据对象x映射到其中，在所有现存的非空网格中，搜索新建网格的直接相邻网格，若找到新建网格的直接相邻网格，则分别将新建网格和其直接相邻网格加入到对方的直接相邻网格集合内；2.2当新数据对象x被映射到相应网格g(x)中时，则对网格g(x)的特征向量进行更新，更新操作如下：$\left\{\begin{array}{c}g.CF1=g.CF1+X.r,\\ g.H=g.H+X.q,\\ g.T_l=T,\\ D(g,T)=2^{-\lambda (T-t_1)}D(g,t_1)+1.\end{array}\right.---\left(1\right)$其中为数据对象数值属性的线性和，H为一个向量，代表分类属性中每一个属性的频度，T_l记录网格最后一次更新的时间，D(g,T)为网格在T时刻更新的密度值，r和q分别代表数值属性和分类属性；若对应的网格g(x)是稀疏网格，则在新加入一个数据对象，并更新其网格密度后，对网格g(x)的网格密度进行判断，若D(g,t)＞D_thred则将网格g(x)标记为密集网格，设置其Dlabel＝Dense；2.3将一个密集网格衰减为稀疏网格的最小时间作为检测的时间间隔，设置其检测时间TimeGap如下：$TimeGap=\frac{1}{\lambda }log\left(\frac{D_{thred}}{D_{thred}-1}\right)---\left(2\right)$其中D_thred是密度阈值，λ是衰减因子；每隔TimeGap时间，对所有网格进行检测，若密集网格的密度不断衰减，而使得其密度值小于权值，即D(g,T_c)＜D_thred，则意味着该密集网格已经退化为离群点噪声，将其删除释放空间来存储新的网格；3)离线聚类过程：3.1从数据空间中寻找到一个密集网格g，以网格g为本次聚类的起始点开始聚类过程；3.2按照广度优先搜索原则，寻找到密集网格g直接相邻的网格g_i，然后对每个g_i网格单元继续进行广度优化搜索，直到所有到网格g相邻可达的网格单元到被搜索为止；3.3当检测到边缘网格时，需要进行进一步的处理，检测该边缘网格是否是争议网格，若为争议网格，则计算争议网格内数据对象到吸引其的直接近邻网格中心的平均距离，将其划分到距离其最近的直接相邻网格内；3.4当一次聚类过程结束时，从剩余的未聚类网格中找出新的密集网格，则重复3.1‑3.3步骤继续聚类，若不存在任何未被聚类密集网格，则跳到步骤3.5；3.5输出离线聚类的最终结果，输出结果并结束。