核密度估计及其在聚类算法构造中的应用_李存华汇总

《核密度估计及其在聚类算法构造中的应用_李存华汇总》由会员分享，可在线阅读，更多相关《核密度估计及其在聚类算法构造中的应用_李存华汇总（9页珍藏版）》请在装配图网上搜索。

1、Vol 41. Na 10Oct 202第41卷第10期计算机研究与发展2004年 10 月JOURNAL OF COMPUTER RESEARCH AND DEVEU)PM ENT核密度估计及其在聚类算法构造中的应用李存华S孙志挥陈耿胡云 (东南大学计算机科学与工程系 南京210018) ，淮海工学院计算机科学系连云港222005) (cli liliit. edu. cn)摘 要 经典数理统计学中的核密度估计理论是构造基于数据集密度函数聚类算法的理论法础.采用分箱近似的快速 核密度函数估计方法同样为构造高效的聚类算法提供了依据通过对核密度估计理论及其快速分箱核近似方法的讨论. 给出分箱近似

2、密度估计相对于核密度估计的均方误差界,提出基于网格数据重心的分箱核近似方法在不改变计算复杂 度的条件卜；基于网格数据重心的分箱核近似密度函数计算可以有效地降低近似误差，这一思想方法对于构造高效大规 模数据聚类分析算法具有指导意义 揭示了基于网格上密度函数近似的聚类算法与核密度估计理论之间的关系关键词核密度估比分箱规则；聚类算法中图法分类号 TP391Kernel Density Estimation and Its Application to Gustering Algorithm ConstructionLI Cun HuaU S UN Zhi Hui1. Chen Geng I and

3、Hu Yun1, 21 (De/Mtrtmait of Com put o Science and Eg inuring. Southeast Universily. Nanjing 210018)(De/xirt merit of Compute Science. Huaihai Institute of Technology. Li any ungang 222005)Abstract Kernel density estimation provides solid foundation for density based clustering algorithm con， stmctio

4、n. While binned a|)pn)ximation is show n to l)e an efficient mechanism for fast kernel density c(md pu tatioik it is also proven to be a promising approach to construct robust clustering algonthms. This paper deals with formation and accuracy of the binned kernel density eslimators presents mean squ

5、ared ern)r lx)uncls for the closeness of such estimators to the unbinned kernel density estimators. To improve the accu， racy of the binning methods a nave grid level approximated density estimator is constmete(L followed by a detailed proof of its mean squared ern)r 1x)uii(1k The improved approach

6、constructs binned density estimator by substituting the center of a grid with the gravity center of the data point由 hich results in better estimation accuracy without loss of computation efficiency. As a main concern, the close relation between the density lase(l clustering algorithms and the kernel

7、 estimation methods is revealed.Key words kernel density estimation： binning rule； clustering algorithm和工具是人们认识和探索事物之间内在联系的有 1引 言效手段,具有强大的功能和十分广泛的应用领域正因为如此该技术一宜受到研究者的重视并得到 聚类分析是数据挖掘技术的基本而重要的方法广泛深入的研究近年来.众多研究者运用小同的收稿日期:2004-07-15基金项目：国家自然科学基金项11(70371015)；国家科技部中小型企业创新基金项LHO2c26213210070)；江苏省教育厅门然科学基金

8、以U(O2KJB52OOI2)71994-2014 China Academic Journal Electronic Publishing House. All rights reserved, 10期李存华等：核密度估计及其在聚类算法构造中的应用1713理论工具或基丁不同的应用目的构造了 一系列具有 重要应用价值的有效算法.然而，实际问题的复杂 性、数据存储与获取技术的速发展始终对现有聚 类技术提出巨大的挑战其主要的表现之一是被处 理数据的巨量性一不论设备处理能力的增长如何 显著,人们总能够找到足够规模的数据集使计克资 源消耗殆尽因此研究并构造高性能的大规模数据 聚类算法成为目前普遍关注的

9、问题众所周知,聚类分析与回归分析、判别分析一 起，构成r经典数理统计学的三大支柱 其中，聚类 分析是一种不依赖了先验知识的、从数据本身出发 发现其内部分布模式的数据分析方法与其他技术 相比.它在分析和解决大规模复杂问题时体现由史 大的优越性 随着数据挖掘技术的兴起和智能信息 技术的广泛运用.聚类分析理论与实现技术已远远 超越传统统计学的他畴.成为多学科分支相互交义、 共同作用的岐用与研究领域.尽管如此数理统计 学仍然是聚类分析技术的基础和本源聚类方法人 身及对聚类结果的合理解释仍然需要经典数理统计 学的强有力支掾一般地聚类算法可以根据其对聚类的定义方 法加以分类I .常见的聚类定义包括基广距离

10、的、 基于质心的、基于连接的和基于密度的方法等.据 此人们构造了一系列不同的聚类方法尽管不同 方法之间存在或多或少的差异，它们都有一个共同 的出发点，即数据的聚类依赖数据对象之间的相 似性度最 在这一意义上基r数据空间密度函数 构造的方法具有显著的优越性.首先，这种定义方 法具有怕实的理论基砒 它的木源是数理统计学中 的密度估计（kernel density estim ation ）理论 其次, 这一方法泛化了其他关于聚类的定义方法.此 外.基于密度函数的聚类定义对于噪声数据具有良 好的抗干扰性.并能够灵活地对任意形状的聚类加 以定义和发现由于这些显著的优点，基于数据空 间密度函数的聚类描述

11、方法为构造聚类算法提供r 良好的基础条件,典型的基于密度的聚类算法包括 D EN C L U E121等，它们在应用中表现了良好的性能 然而，基于密度的聚类算法在实现上仍有一定的缺 陷,即由密度函数计算所导致的算法复杂性为此. 李存华等人提出基丁数据空间网格划分的近似密 度计算方法 这种方法继承了密度函数理论的严密 性,且充分考虑到聚类算法的要求,利用数据在局部 空间中密度不均匀的性质,有效地避免r对稠密区 不难发现.这种聚类构造方法在理论上与统计学中 的核密度估计具有密切的联系 为此本文从核密 度估计理论出发 讨论实现快速核密度估计的数据 分箱方法,在研究其误差估计问题的基础上,提出新 的基

12、于网格数据重心的分箱核近似估计方法.基r 网格数据重心的核近似估计在保持了分箱方法的高 效率特征的同时，可以有效提高近似精度 这种思 想方法已经成功运用t聚类算法的构超3,因 此.本文从统计学角度揭示了上述聚类算法的合 理性2核密度估计由给定样本点集合求解随机变量的分布密度函 数问题是概率统计学的基本问题之一解决这一问 题的方法包括参数估计和非参数估计.参数估计乂可分为参数回归分析和参数判别分 析.在参数I可归分析中，人们假定数据分布符合某 种特定的性态.如线性、可化线性或指数性态等.然 后在目标函I数族中寻找特定的解.即确定I可归模型 中的未知参数 在参数判别分析中.人们需要假定 作为判别依

13、据的、随机取值的数据样本在各个可能 的类比中都服从特定的分布.经验和理论说明.参 数模型的这种基本假定与实际的物理模型之间常常 存在较大的差距.这些方法并非总能取得令人满意 的结果由于上述缺陷,Rosenblatt161和Parzef 提出了 非参数估计方法，即核密度估计方法.由于核密度 估计方法不利用有关数据分布的先验知识,对数据 分布不附加任何假定是一种从数据样本本身出发 研究数据分布特征的方法.因而.在统计学理论和应 用领域均受到高度的重视为了讨论多维空间上的核密度估计问题.我们 首先引入一维核估计的概念网.定义1.设XI, X2,、X”为取值丁 R的独立同 分布随机变量.其所服从的分布

14、密度函数为/（X）. xER.定义函数：f h（x ）= yjK （力 一 ）,x R, （1） 它称为密度函数/（x）的核密度估计.K （。）称为核 函数7为预先给定的正数.通常称为窗宽或光滑 参数为方便起见,我们记Kh（ ）= K （ /4）/伍则reserved. http: 1714计算机研究与发展2004 年/,(x) = -X Kh(Xi- x), x E R. (2) i-1由定义1可知，分布密度函数f的核密度估计则称K()为A阶核函数在聚类分析应用中，待处理的数据集一般是多 维的.因此.我们需要讨论多维空间上的核密度估/不仅与给定的样本点集合有关，还与核函数的选 择和带宽参数的

15、选择有关其中，带宽参数h控制 r在求点力处的近似密度时不!“距离样本点为点密 度的影响程度在理论上,任何函数均可以用做核函数,但为了 密度函数估计的方便性与合理性.通常要求核函数 满足以下条件：K ( )= K ( )(3)Sup |K()匕 oqK ( u )(1 w =-OO常用的核函数有以下几种：(1)高斯核函数(Gaussian kernel )：I -K (u) = ,reT.(2) Epanechnikov 核函数：(5)3(1 u2 )/4 I u 匕 1.a、(3)Biweight 核函数:I u t 1.(6)K (u) =15(1-I K 1.(I / t 1.(7)由式(

16、2)定义的核密度函数贴切地反映了分布 密度函数在一点的值对该点邻域样本点密度的正比 依赖关系图1为采用高斯核函数时，样本点分布 与所得到的核密度函数曲线图1由10个点描绘的高斯核估计曲线定义2.设K(。)为有界函数.且对正整数，和 份2有：.(h/ = 0.u K ( )d = I 0.1 i A 1,Rk !0. i = k.计问题 为方便起见.我们假设维核函数是个同类 型一维基核函数的积定义3.设,X”为空间上的独立 同分你随机变最，其分布密度函数/(x)的核密度 估计定义为/(%)= :Kd.h(Xi- X).(9)其中， ddKd.h(X)= IIk%(x,)= n K( Xi/hi)

17、/hi./=1/-I(10) K ()为形如式(1)且满足式(3 ), (4)的一维基核 函数特别地.采用d维同参数高斯核函数构造的胪 上的核密度函数具有如下形式：d _ (Y- Xi)Kd. a(x ) =JJe 2J = i-1(万。厂。27-.(11)在文献2中,Henniburg采用形如式(11)的分 布密度函数描述数据集在空间中的分布.通过定义 密度函数的吸引子(H部极大值).给出了中心型聚 类和任意形状聚类的定义并构造了相应的DEN CLUE聚类算法DENCLUE聚类算法从一个任意 的数据点出发运用爬山法搜索其所屈的局部吸引 子若吸引子所在点处的密度函数值达到或超过预 设的阈值，则

18、将该点赋给由吸引子生成的类，否则. 认为该吸引子所吸引的数据点太少而将所吸引的样 本点视为噪声数据.可以证明，基于密度的聚类定 义方法涵盖了其他基了距离或基丁连接的聚类的定 义.因此,它具有更为广泛的适应性尽管如此.卢接基核密度函数构造的聚类方 法在效率上存在巨大的局限性由式(9)易见.计算 含N个数据点的数据集在全体N个数据点上的密 度函数值的计算复杂度为O(Nb尽管文献2运 用高斯函数的快速衰减性质将求解全局密度函数的 过程简化为数据点邻域的局部计徉将聚类计算的 复杂度降低为0( NlnN),其时间与空间效率仍使 其难以有效地运用于大规模数据集聚类问题.基于 这一考虑,文献3 5提出的基于

19、网格上近似密度71994-2014 China Academic Journal Electronic钝blishitll黑粼嗨瀚献那翎行4融镰麟10期李存华等：核密度估计及其在聚类算法构造中的应用1715(由简单分鼾函数(b)线性分相函数与聚类过程的基础框架,研究网格层次上的密度近 似计算所产生的误差并提出了相应的误差补偿方 法将复杂的点对点密度计算问题行化为带近似误 差修正的点对数据网格代表点的密度计宛从而大 大降低了聚类过程的空间需求和时间复杂度文献3,4提出的方法仅宜观地考虑了网格上 近似密度计算问题，没有注意到这一思想与核密度 估计理论之间的关系.事实上，这种方法在快速核 密度估计问

20、题中已经得到r较为深入的讨论,其思 想类似f由Silverman首先提出的分箱核估计理论 (binned kernel estimation ) .3分箱核估计定义4如果函数族3),/GZ满足如 下的条件：Vx R.叼(x, 8)(1 / G Z. (12) 之叼(x, 3) = h(13)jZ则称该函数族为分箱函数族(binning function ).由 该族函数确定的数据分配规则称为数据分箱规则 (binning rule)网.典型的分箱函数族有简单分箱函数族和线性分 箱函数族两种.如图2所示其中.简单分箱函数可 用下式表示： L (；- y 8NjKd. h(X- Xj ), X G

21、 Rd jezu(27) 为基于网格数据重心的分箱核估计.对于由式(27)定义的近似核密度估计,我们有 以下的定理：定理3.设基核函数K/,(。)存:在连续的二阶导 数,则有： 山/一 Y /d)(4)2 (.)2)严 + 0( gi) (28)证明.以X；表示d维空间中标号为1的网格 中全部数据点的重心表示点X所在网格单元 数据点的重心、则/ (X,力)一/(X h)= N I 2Kd.h(X-Xi)- ZnjK&YX-X；)= /-IjezjN121 SKd. h(X-Xi)- Kd. h(X 一 %/). t=ling House. All rights reserved, 10期李存华

22、等：核密度估计及其在聚类算法构造中的应用1719注意到 Kd.h(X XC= JJ Kh(xk- xn ),将 *= i其视为Xi的函数并在点X：做Taylor展开得；Kd.h(X- Xi)= Kd.h(X-X* ) +d.人(X X/ ) (xn x f/ ) +d d-p/ J 八人八/K d. h ( X X i ) ( Xik Xik)(xf/- xn ) + o( S ).由丁在每个网格单元上均有 ，Kd.h(X Xi ) (Xu XH ) = 0./-I /-I XI所以，数据点生成的核密度估计/以及简单分箱核估计 f、基了区间数据重心的改进简单分箱核估计/相 对于/的拟合情况结果

23、表明,/比/具有更理想的 拟合精度.能够更充分地反映原始核估计曲线的特 征本节提出的基丁网格数据重心的简单分箱核估 计方法在文献14中成功地运用于基丁网格上近 似的聚类方法构造 进一步地.文献| 3. 4|还就大规 模数据集条件下近似密度计算的误差补偿问题进行 了进一步的研究显然,本节的结果在论证了上述 聚类算法的合理性的同时.也为提高分箱密度估计 的精确性提出了新的思路.71994-2014 China Academic Journal Electronic Publishing House. All rights reserved. http:/ (X. /:)-/ (%- h)=n 1

24、X/ jKd. h(X X/ ) (xu xu ) + j I1 XN d d /j=l *=1 /=!入 I* i Q(Xik X ik)( Xil X il ) 4- O ( 0 )=N d d J.八X；(Xik - X1)(X 一 X； ) + o( 3 ).因为I Xil X it I d故当 时.Elf-f2X”f(y)dy+o( o ) = /：Kd. h (XX) 2+o ( 8).于是，当8-0时,山7-/iYn id 8 (K 7 供(K力)2) + o( 8). V一l 一楼估计 一2一分箱找估计 一3一改进分箱核体计x数据点 0分箱数据计数图5 力与相对于/；的拟合效果

25、对比5结 论核密度估计及其近似计算方法是数理统计理论 与应用的重要手段尽管源r数理统计学的聚类分 析技术已经演变为多种技术共同促进的综合型数据 分析技术.其解决问题的思想方法仍与传统的数理 统计学具有密切的联系本文分析一类基于数据 空间密度函数构造的聚类算法与核密度估计理论之 间的关系为其提供了坚实的统计学背景比较式(23)和式(28)可见，在采用简单分箱策 略进行核密度近似估计时,利用网格中样本点的重 心取代网格中心.可以有效降低近似计算造成的误 差在具体的算法实现时，非空网格中数据点的重心 可以通过简单的动态更新加以计算，因此计算/ 与/具有相同的复杂度O(nV),其中N为数据集 样本点数

26、,？为采用简单分箱规则时的非空网 格数参考文献J Han M Kmnbei: Data M i ting： Concepts and Tec-hni|iies New York： Morgan Kaufmann 20(X1 335 398?廨朝端源原般MaWmiishing忧黑二含勰施飞腔”一飞扃相A Hinnetuige D A Keims An efficient approach to clustering in kirge muhimeclia ditabases with noise In： B AgrawaL PE Stdor& G PiatetskShapin ed& Proc

27、/ the 4th kit9 1 Conf on Kn)w hxlge Discwvei), and Data Mining (Kl)D 98). New York： AAAI Pn ss 1998 5865DENC L( E aorilhm by mxiinal ion on grids In： Pn)r of t he 4th Int I Conf on Advances in U elrAge Infonnalion M air ageinent. Neu York： SpiingerVerlag. 2003. 202 2134 李存伟孙志探GiiIOF：面向大规模数据集的高效离群点检测

28、算法计算机研究与发展.2003. 40(11)： 15861592(Li Cunluae SunZhihii. GridOF： A dficirnt out-detection algorithm for veiy hrge (lutmeta. Journal of Computer search and l)evdo|ii)ent( in Chineseh 200工 40( 11 )： 1586- 1592)5 1 j (ainhua Sun Zhihui Approximation approach to gri(l-l)ce(l( List ering algiiritlnns and

29、its rrn)r alual iott Journal * 1956b 27( 6)： 832 837E Parzeii On eslinutfion of a prolnbiltr density function and mode Annals of Malhematical St1962. 33(8)： 1065 1076R P HalL M Wand On the arrumry nf binned UpitipI flnnsity Zi- ma tors Journal M Multivariate Analysis. 1994 56(2)： 165 1849 B Silvcnna

30、n Density Estimation for Statistics and Dita .Anahsis. London： Chapman & HalL 1986 1 - 4010 P JaiisMMK J S M arniu N Verrn tTln-kn et al. Scuile intasuivs for bandwidth sdectioa Joumal of Noir Pammetric Statistics* 1995t 7(5)： 359-380v 李存华 男.1963年生.博I：研究生, 副教授.主要研究方向为数据库知识发现、 r图像处理孙志挥男.1941年生.教授.博I:生 导师,主要研究方向为复杂信息系统集成、 数据库知识发现陈耿男.1965年生博I:研究生.主要研究方向为数据库知识发现、管理信 息系统胡 云女.1980年生.硕I：研究生,（主要研究方向为数据库理论、软件工程