一种网格k-近邻集的边界点识别算法

李光兴

(成都农业科技职业学院基础部 成都 611130)



一种网格k-近邻集的边界点识别算法

李光兴

(成都农业科技职业学院基础部 成都 611130)

为了高效识别聚类边界,根据边界周围区域存在密度差异的特征,提出了一种网格k-近邻集的边界识别算法(BGN)。在网格空间中,该算法根据网格单元和它最近邻居单元的k-近邻集的质量及其单元间中心距离确定边界度,由边界度和边界阈值判断每个网格单元是否为边界单元或噪声单元。通过从边界单元中提取更靠边缘的数据作为边界点的方式,使得边界更精细。实验结果表明,该算法能有效和快速识别出多密度数据集的聚类边界和噪声。

网格单元;k-近邻集; 边界度; 边界点; 噪声

Class Number TP311

1 引言

边界点是指位于不同密度数据区域边缘的数据对象,边界就是边界点的集合[1]。边界反映了数据的分布特征和结构信息,同时也提供了一种有用的模式,如果数据分布的边界确定了,那么就可以根据边界对数据聚类或分类[2～4]。边界识别研究有助于提高聚类的精度以及分类的准确度。另外,边界识别也是图像处理和数据分析的有用手段[5～7]。

DBSCAN是基于密度的聚类算法[8],它定义了聚类的边界点,如果一个对象不是核心对象,且它对某个核心对象是直接密度可达,则该对象为边界点。由于识别的边界点与全局参数密切相关,不能有效识别多密度数据集的边界点,算法时间复杂度较高,为O(nlogn)(n是数据规模的大小)。BORDER算法[1]是基于密度的边界点识别算法。若一个对象p在某个对象o的k-近邻中,则称对象o是对象p的反向k-近邻。利用边界点的反向k-近邻个数一般小于处于聚类内部对象的反向k-近邻的个数思想来识别边界点。数据集的所有对象按它的反向k-近邻数从小到大排列顺序,并把前w个对象作为边界点。因为噪声和聚类内部的一些点的反向k-近邻数可能少于边界点的反向k-近邻数,所以该算法不能正确地从多密度和带噪声的数据集中提取聚类的边界点。另外,参数w的多寡取舍比较困难。算法时间代价也较高为O(kn2)。BDKD算法[9]用基于密度的聚类思想,把数据对象的k-近邻距离与其邻域内数据对象的平均k-近邻距离之比定义其k-离群度,对k-离群度超过阈值的数据对象规定为边界点。但时间复杂度为O(kn2)消耗不低。

BOURN算法[10]是根据数据分布的统计信息来识别边界模式的算法,由数据分布的均值和方差定义数据对象的边界度,按边界度的大小对数据集降序排列,选取前w个边界度最大的对象作为边界点输出。虽然该算法在含有噪声的数据集上能有效地识别出边界点,但参数选择较困难,算法的执行效率不高,时间复杂度与DBSCAN相当。在基于网格聚类的算法中,文献[11～12]只考虑了识别低密网格聚类的边界点,并没有给出提取所有聚类边界点的策略。

BPGG算法[13]是基于网格的边界识别算法。该算法的思路是:当一个网格处在类的边界区域时,其梯度会明显大于那些处在类内部的网格的梯度。算法首先通过卷积运算定义网格梯度,运用梯度算子,近似求出网格所对应的每一个维的梯度值,然后从中选取绝对值最大的梯度值与给定阈值比较确定边界网格,再把边界网格中的对象标记为边界点。算法的不足是运算较复杂,且把边界网格中的数据点都作为边界点,得到的边界较粗糙精度不高。文献[14]提出了一种基于网格的边界点识别算法,利用相邻网格单元间的数据分布关系识别边界单元和边界点。但由于边界识别过程中只分析了单元和相邻单元小范围内的数据分布信息,因而结果受网格划分方法和划分数量的影响较大。

为克服现有边界识别算法难以有效地对带噪声的多密度和大数据集的聚类进行边界识别,绝对参数选择困难以及精度和效率低的缺点,减少基于网格的边界识别算法中网格划分方法对结果影响,提出一种网格k-近邻集的边界点识别算法(The boundary point recognition algorithm for Gridk-nearest neighbor set,BGN)。

2 相关概念

2.1 网格单元和k-近邻集

S=A1×A2×…×Am是一个m维数据空间,其中Aj(j=1,2,…,m)是第j个属性的有界定义域,X={x1,x2,…,xn}是包含n个数据点的m维空间中的数据集,数据点xi=(xi1,xi2,…,xim)(i=1,2,…,n),其中xij∈Aj,每个数据点的质量规定为1,一个数据集的质量就是这个数据集中的数据点数。

定义2 给定近邻距离k,若p和q是非空单元,p与q的几何中心欧式距离rqp不超过k,除j维外其它各维p与q的划分区间相同。

1) 当p在j维的划分区间的左端点大于或等于q在j维划分区间的右端点,则称p是q的j维右邻居,与q的几何中心距离最短的j维右邻居,称为q的j维最近右邻居。

2) 当p在j维划分区间的右端点小于或等于q在j维划分区的左端点,p与q在其它各维的划分区间相同,则称p是q的j维右邻居,与q的几何中心距离最短的j维左邻居,称为q的j维最近左邻居。

从定义可知,若p是q的j维最近左邻居,则q是p的j维最近右邻居。一个非空单元在某维不一定有邻居单元。

定义3 单元q的k-近邻集k{q}是由单元q和它的各维左右邻居组成。k{q}的质量N(k{q})为它所含的各单元质量的和。

图1 k-近邻集图

并不是所有与单元q的几何中心距离小于k的单元都是k{q}的元素,而只有那些沿维轴正负方向q的邻居,才成为k{q}的元素,这样规定能减少算法的复杂度。如图1,取近邻距离k为单元划分区间长度的三倍,则k{q}={a,q,b,c,d,e,f},单元a,b,e是q单元的最近邻居,N(k{q})=10。

2.2 边界度与边界单元

定义中|N(k{q})-N(k{p})|/N(k{q}∪k{p})为k{q}的质量与k{p}的质量差的绝对值比k{q}与k{p}并集的质量,值越大表明k{q}与k{p}分布密度相对差越大。rqp/k越大表明p与q相距越远。边界度的范围为[0,1]。

显然,如果p是q的j维最近左邻居,q是j维右边界单元,那么p是j维右边界单元。如果p的j维无左(右)邻居,则p是j维左(右)边界单元。

噪声单元实质上是一种特殊的边界单元,它对每一维的左右两个方向而言都是边界单元,或者说噪声单元与它的任意一维的最近左或右邻居都不是同类,因而噪声单元又可看成是孤立单元。不是噪声单元的边界单元称为非噪声边界单元。

3 BGN边界点识别算法

3.1 边界的细化

3.2 BGN边界点识别算法步骤

BGN边界点识别算法包括网格划分、数据映射,确定k-近邻集和边界度,判断边界单元或噪声单元,提取边界点和噪声等过程。具体步骤如下:

输入 数据集X,每维网格划分区间数t,近邻距离k,边界阈值h

输出 边界点和噪声

步骤1 将数据空间S划分为网格单元,确定网格单元的中心,并将数据集X映射到网格单元中,统计和计算非空网格单元的质量和质心。

步骤2 查找每个非空单元的k-近邻集。

步骤3 计算每个非空单元的每一维的左右边界度,根据定义5判断单元是否是边界单元。

步骤4 根据定义6从边界单元中找出噪声单元,提取噪声数据。

步骤5 提取非噪声边界单元中的初边界点。

步骤6 按边界细化的方法提取非噪声边界单元中的细边界点。

步骤7 输出噪声数据、初边界点和细边界点,算法结束。

网格划分一般可按平均每个网格单元的数据不少于一个来确定每维划分数。近邻距离k一般取单元划分区间长度的倍数。边界度是一种相对数,比采用绝对数来说,更容易确定边界阈值h,一般取为0

3.3 算法复杂度分析

m维数据空间中有n个数据,划分网格并将数据投影到网格中,扫描网格空间一次,统计单元的数据数量,时间复杂度为O(2n)。一个k-近邻集最多只有2km个元素,计算非空单元d(d≤n)的边界度,时间复杂度为O(2kmd),对边界单元进行细化处理,其时间复杂度为O(md),所以BGN整个算法的时间复杂度为O(2n+(2k+1)md),算法的时间复杂度与数据规模呈线性关系。

4 实验结果及分析

4.1 算法性能实验

比较BGN与BORDER的时间效率。九个数据集分布为正六形。BGN边界阈值h=0.32。BORDER实验参数为近邻居数10,在相同数据规模情况下,取BORDER边界点数量与BGN算法识别的初边界点数相同。

不同数据规模的数据集的分布结构不一样,因而识别的边界点数也不相同。从表1可见,数据量递增时GAB算法的时间复杂度呈线性增长,执行时间远远低于BORDER,具有良好的数据规模可扩展性。

表1 BORDER与BGN数据规模执行时间比较

4.2 算法有效性对比实验

试验1 二维数据集呈叶形分布(图2(a)),共16666个数据。BGN每维网格划分区间数为t=129,共划分成8281单元,边界阈值0.23。BGN识别出边界单元838个,共有1066个初边界点(图2(c)),经过细化后边界点精减为745个(图2(d)),边界更精致平滑,如叶柄部分边界更清楚。识别出分布于叶边缘的10个噪声点。BORDER参数为近邻个数12,边界点数为900。从图2(b)中可见,BORDER算法的效果没有BGN好,表现在叶形外围边界完整性差,丢失了较多的外围边界点,因为叶内部的一些点的反向k-近邻个数比聚类边界点的反向k-近邻个数还少,所以叶内部的这些点也被当作边界点。

图2 叶型边界识别比较

试验2 二维多密度数据集包含13885个数据,分布形成“花”型(图3(a))。构成花(数据量13728个)的花瓣、花蕊、叶及枝等部分密度不同,形状各异。分布在花周围有157个随机离散点。

BORDER参数为近邻个数30,边界点2200个。BGN每维网格划分区间数为t=117,边界阈值0.16。BGN识别出边界单元1778个,共有3028个初边界点(图3(c)),经过细化后边界点精减为1935个(图3(d))。识别出噪声数据150个(图3(e))。从图3可见,BORDER识别出构成“花”的花瓣、花蕊、叶及枝等部分外围边界完整性较差,没能把噪声点与边界点相区分。BGN能较完整地识别出构成“花”的各部分边界和分布在“花”周围的小聚类边界,有效地去除了噪声。经细化后的边界更清晰简洁。这说明BGN算法边界点的识别效果比BORDER好。

图3 花型数据集边界识别效果比较

5 结语

在充分考虑了局部区域数据分布相对差异能反映不同密度数据集边界分布特征的基础上,给出了相应边界点识别算法BGN。利用相对参数来降低参数选择的难度。通过按维分析单元k-近邻集和该单元的左右最近邻单元的k-近邻集数据分布关系来识别边界单元方法,较好地克服网格划分对边界单元识别的影响。理论分析和实验显示,BGN算法能识别出分布呈任意形状的多密度数据集的聚类边界点和噪声,输入参数少,与数据输入顺序和单元顺序无关,具有较高的边界检测精度和执行效率。

[1] Xia C, Hsu W, Lee M L, et al. BORDER: efficient computation of boundary points[J]. Knowledge and Data Engineering, IEEE Transactions on,2006,18(3):289-303.

[2] 张选平,祝兴昌,马琮.一种基于边界识别的聚类算法[J].西安交通大学学报,2007,41(12):1387-1390.

[3] 邱保志,琚长涛.具有聚类功能的边界检测技术的研究[J].计算机工程与应用,2010,46(20):133-137.

[4] 楼晓俊,孙雨轩,刘海涛.聚类边界过采样不平衡数据分类方法[J].浙江大学学报(工学版),2013,47(6):944-949.

[5] 李灿灿,王宝,王静,等.基于K-means聚类的植物叶片图像叶脉提取[J].农业工程学报,2012,28(17):157-161.

[6] 安萌,姜志国,赵丹培.边界片段模板方法在空间探测识别中的应用[J].宇航学报,2009,30(3):1231-1236.

[7] 邱磊,杨承志,何佃伟.一种新的基于网格聚类的雷达信号预分选算法[J].现代防御技术,2013,41(2):167-172.

[8] Ester M, Kriegel H P, Sander J. A density-based algorithm for discovering clusters in large spatial databases with nosise[C]//Proceedigs of the 2nd International Conference on Knowledge Discovery and Data Mining. Portland, Oregon:[s.n.],1996:226-231.

[9] 王桂芝,李井竹,狄志超.支持k-离群度的边界点检测方法[J].计算机工程与应用,2011,47(33):140-142.

[10] 邱保志,张枫,岳峰.基于统计信息的聚类边界模式检测算法[J].计算机工程,2008,34(3):91-93.

[11] 高亚鲁,宋余庆,朱玉全.改进的CLIQUE优化算法[J].计算机工程与设计,2009,30(16):3801-3804.

[12] 张鸿雁,刘希玉,付萍.一种网格聚类的边缘检测算法[J].控制与决策,2011,26(12):1846-1850.

[13] 邱保志,余田.基于网格梯度的边界点检测算法的研究[J].微电子学与计算机,2008,25(3):77-80.

[14] Li G, Li B. Boundary Point Recognition Algorithm Based on Grid Adjacency Relation[M]//Recent Advances in Computer Science and Information Engineering. Heidelberg,2012:Springer:211-218.

Boundary Point Recognition Algorithm for Gridk-nearest Neighbor Set

Li Guangxing

(Department of Fundamental Courses, Chengdu Vocational College of Agricultural Science and Technology, Chengdu 611130)

In order to efficiently identify the cluster boundary, based on the existence of density differences in the surrounding area of the boundary, a boundary point recognition algorithm for Gridk-nearest neighbor set(BGN) is proposed. In the grid space, based on the number of elements of grid cell and its nearest neighbor’sk-neighbor set, along with the cell-center distance of the unit grids, the boundary degree is determined by this algorithm. According to boundary degree and boundary threshold, this algorithm determines if each unit grid is boundary unit or noise unit. By extracting the data closer to the edge of the boundary to represent as boundary points, this algorithm is capable to make finer boundary. The experimental results indicate that the algorithm can effectively and quickly identify the cluster boundaries and noise for multi-density datasets.

grid cell,k-nearest neighbor set, boundary degree, boundary point, noise

2015年1月13日,

2015年2月27日 作者简介:李光兴,男,副教授,研究方向:人工智能与计算数学。

TP311

10.3969/j.issn1672-9730.2015.07.035