当前位置：文档库 › 一种不确定数据流聚类算法

一种不确定数据流聚类算法

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.wendangku.net/doc/4a15250287.html,

Journal of Software, Vol.21, No.9, September 2010, pp.2173?2182 https://www.wendangku.net/doc/4a15250287.html, doi: 10.3724/SP.J.1001.2010.03654 Tel/Fax: +86-10-62562563

一种不确定数据流聚类算法

张晨1, 金澈清2+, 周傲英2

1(复旦大学计算机科学技术学院上海市智能信息处理重点实验室,上海 200433)

2(华东师范大学软件学院上海市高可信计算重点实验室,上海 200062)

Clustering Algorithm over Uncertain Data Streams

ZHANG Chen1, JIN Che-Qing2+, ZHOU Ao-Ying2

1(Shanghai Key Laboratory of Intelligent Information Processing, School of Computer Science, Fudan University, Shanghai 200433,

China)

2(Shanghai Key Laboratory of Trustworthy Computing, Software Engineering Institute, East China Normal University, Shanghai 200062,

China)

+ Corresponding author: E-mail: cqjin@https://www.wendangku.net/doc/4a15250287.html,

Zhang C, Jin CQ, Zhou AY. Clustering algorithm over uncertain data streams. Journal of Software, 2010,

21(9):2173?2182. https://www.wendangku.net/doc/4a15250287.html,/1000-9825/3654.htm

Abstract: This paper proposes a novel algorithm, named EMicro, to cluster uncertain data streams. Although most

of the works used today mainly use the distance metric to describe the cluster quality, EMicro considers distance

metric and data uncertainty together to measure the clustering quality. Another contribution of this paper is the

outlier processing mechanism. Two buffers are maintained to reserve normal micro-clusters and potential outlier

micro-clusters, respectively, to obtain good performance. Experimental results show that EMicro outperforms

existing methods in efficiency and effectiveness.

Key words: uncertain data stream; clustering; outlier

摘要: 提出了EMicro算法,以解决不确定数据流上的聚类问题.与现有技术大多仅考虑元组间的距离不

同,EMicro算法综合考虑了元组之间的距离与元组自身不确定性这两个因素,同时定义新标准来描述聚类结果质

量.还提出了离群点处理机制,系统同时维护两个缓冲区,分别存放正常的微簇与潜在的离群点微簇,以期得到理想

的性能.实验结果表明,与现有工作相比,EMicro的效率更高,且效果良好.

关键词: 不确定数据流;聚类;离群点

中图法分类号: TP391文献标识码: A

近年来,随着信息技术不断发展,数据流模型在许多应用中广泛出现,其特征是数据到达速度极快、规模庞

大,例如Internet应用、传感器网络等[1].此外,受物理仪器精度限制、周围环境等因素的影响,流数据还同时具有

? Supported by the National Natural Science Foundation of China under Grant Nos.60933001, 60803020 (国家自然科学基金); the

National Science Foundation for Distinguished Young Scholars of China under Grant No.60925008 (国家杰出青年基金项目); the

Shanghai Leading Academic Discipline of China under Grant No.B412 (上海市重点学科建设项目)

Received 2008-11-17; Revised 2009-02-24; Accepted 2009-04-29

2174

Journal of Software 软件学报 V ol.21, No.9, September 2010

不确定性.因此,面向不确定数据流的分析与挖掘技术已成为新近的研究热点.本文研究聚类(clustering)问题,即如何将数据集合划分为若干个簇(cluster),并保证簇内元组的相似性高,簇间元组的相似性低.

现有数据流聚类算法大多针对确定性数据流,各元组均为确定性元组.但是,由于这些算法仅考虑元组间的距离因素,并不考虑元组的存在概率等不确定因素,因而无法直接应用到不确定数据流中去.以图1为例,各元组按照相互间的距离被划分成A ,B ,C 和D 这4个簇.在簇B 与簇D 内,各元组的空间位置关系完全相同,距离平方和(sum of square distance,简称SSQ)也相同.进一步观察会发现:簇B 中元组的存在概率较高,在70%~90%之间;而簇D 中的元组的存在概率则小得多,在10%~30%之间.传统聚类算法无法描述这种差异,迫切需要针对不确定数据流的特点提出新的解决方案.

Fig.1 Impacts of data uncertainty for clustering results

图1 不确定性对聚类结果的影响

离群点检测与处理是与数据流聚类相关的一个重要问题,不同算法所采用的策略不同.在CluStream 算法[2]

中,若新元组无法被现有微簇(micro-cluster)所吸收,则首先合并两个靠得最近的微簇,然后再为新元组创建一个微簇.例如在图2中,初始阶段存在A ,B ,C ,D 这4个簇;在T 1时刻,元组X 1到达,导致C ,D 两个簇合并,且另外为X 1创建一个新微簇.易知,若元组X 1是一个离群点,则该合并操作会降低聚类质量.UMicro 算法[3]的策略有所不同.例如,假设T 2时刻来了新的元组X 2,UMicro 会删除一个最久未更新的微簇,并为元组X 2创建一个新微簇.易知,若X 2也是一个离群点,该删除操作亦会降低聚类质量.

Fig.2 CluStream vs. UMicro

图2 CluStream 算法与UMicro 算法的对比

本文提出了一种针对不确定数据流的聚类算法EMicro,主要贡献包括:1) 充分考虑存在级不确定性对聚类问题的影响,提出了新的数据结构(UCF)来描述微簇,并定义了新标准来描述聚类质量;重新定义了不确定簇

X 2

X 1

T 1

X 1

T 2

T 3

T 4

Delete (UMicro)

Merge (CluStream)

张晨等:一种不确定数据流聚类算法

2175

的聚类特征与质量标准,使聚类过程能够兼顾距离与不确定性双重因素;2) EMicro 算法的一个关键步骤是新元组的被吸附准则,本文在制定该准则时兼顾了距离因素和元组的不确定因素;3) 设计了新机制来应对离群点情况.最后,基于真实数据集和模拟数据集的实验表明,EMicro 具有良好的聚类质量、较快的处理速度,能够有效适应不确定数据流场景.

本文第1节介绍相关工作.第2节定义不确定数据流模型,提出新的数据结构以描述微簇.第3节详细描述EMicro 算法的各个步骤,分析离群点处理机制.第4节提供实验结果及其分析.第5节对全文做总结并指出后续研究方向.

1 相关工作

1.1 数据流聚类

数据流聚类问题得到了广泛的研究.STREAM 算法首先将数据流划分成若干个小段,在各个小段内部分别应用传统的聚类方法(如k -means 或k -medians)进行处理,最终将这些中间数据整合成聚类结果[4].CluStream 算法采用在线维护微簇和离线高层聚类的框架,用金字塔框架(pyramid framework)来存储微簇快照[2].文献[5]提出了一种采用空间分割、组合以及按密度聚类的算法ACluStream.Babcock 等人利用指数直方图EH [6]来维护滑动窗口内相关簇的统计信息[7].D-Stream 算法则采用基于密度的数据流聚类方法,充分运用剪枝技术,空间复杂度低,且能观测各个微簇的演化情况[8]. 1.2 不确定数据聚类

典型的面向不确定数据的聚类算法包括FDBSCAN [9],FOPTICS [10]和UK-means [11].这些算法主要针对静态不确定数据库,而非不确定数据流.FDBSCAN 算法是基于密度的DBSCAN 算法的改进版本,元组之间的距离被定义为模糊距离(fuzzy distance),需要通过两个元组的概率密度函数计算得到.FOPTICS 算法是OPTICS 算法的改进版本[10].UK-means 算法改进了传统的k -means 算法,利用最小边界矩形(MBR)描述数据点可能出现的区域,并通过设计剪枝策略来降低计算复杂度. 1.3 不确定数据流聚类

Aggarwal 等人提出了UMicro 算法,以针对不确定数据流进行聚类[3].他们将CF(clustering feature)结构[12]

扩展成ECF 结构,增加了描述不确定性的部分,从而计算各元组与簇之间的距离以及簇半径.

近期,Aggarwal 为了解决高维数据聚类所面临的“维度灾难”问题,提出了一种投影空间下的不确定数据流聚类算法[13].同样,为了突破UMicro 只能用于某些特定不确定数据模型的限制,文献[14]提出一种基于信息熵的不确定性数据流聚类算法,采用信息熵来衡量元组的不确定性信息,并在聚类过程中综合考虑不确定性与距离双重因素的影响.

上述工作均仅考虑了元组的属性级不确定性,并未考虑元组的存在级不确定性.本文所提出的EMicro 算法则主要面向含存在级不确定性的不确定数据流.

2 不确定数据流模型

元组的不确定性可以通过多种方式进行描述,本文研究点概率模型(point probability case).在该模型中,元组的属性值确定,而存在性不确定,用一个[0,1]之间的概率值表示[15?17].点概率模型应用广泛,例如在RFID 应用中,RFID 读卡器存在漏读、多读等现象,所读数据的存在性并不确定.一个不确定数据流是一个由不确定元组构成的序列.

定义3.1(不确定数据流). 不确定数据流S (或称点概率流)是一个由相互独立的k 维不确定性元组构成的序

列,1122{(,),(,),...,(,)}n n S X p X p X p =uu v uu u v uuu v ,其中,i X uu v

是第i 个元组的值,p i 是该元组的存在概率,0≤p i ≤1.

文献[3]中定义的ECF 结构能够概括由不确定数据组成的簇,并可计算中心点、半径等重要统计信息.但是

2176

Journal of Software 软件学报 V ol.21, No.9, September 2010

ECF 结构仅能处理属性级不确定性,无法处理存在级不确定性,因而无法针对点概率流进行挖掘.鉴于此,本文提出了UCF 结构以对点概率流进行概括,同时也能够计算一些重要统计量.

定义3.2(UCF ). 由一组具有时标T 1,…,T n 的k 维元组1,...,n X X uu v uuu v

所组成的不确定聚类特征(uncertain

clustering feature,简称UCF)可描述为2k +3维的向量(2,1,,,)c PF PF n p t uuuur uuuu r .其中:2PF uuuuv

为各元组的概率加权平方和,

包含k 项,第m 项的值为()()212()m m n

i i i PF p X ==∑uuuur uu r ;1PF uuuu r 为各元组的概率加权线性和,也包含k 项,第m 项的值为()()11m m n i i i PF p X ==∑uuuu r uu r ;n 为簇包含的元组个数;p c 为所有元组的概率和1n

c i i p p ==∑;t 为集合中最新元组的时标

t =max(T i ).

性质3.1. 令U 是针对簇C 的UCF,则当C 中新加入元组(X uu v

,p )后,U 也可相应更新.

该性质的正确性非常直观.当新元组加入之后,字段t 被更新为新的时间戳,字段n 的值加1,其余字段的值均线性增加.

在现有的确定性聚类算法中,簇的中心点是簇内元组的几何中心.即在任一维度,中心点的值是各元组的平

均值.但是,几何中心无法反映不确定元组的概率分布情况.例如在图1中,尽管簇B 和簇D 的几何中心一致,但是簇B 中概率较高的点主要分布于上方,而簇D 中概率较高的点主要分布于下方.显然,如果以概率值来描述元组的权重,则簇B 的中心点应在其几何中心稍上位置,而簇D 的中心点应在其几何中心稍下位置.因此,有必要重新定义簇的中心点与半径,使之适应不确定数据模型.

定义3.3. 簇的概率中心C p 定义为簇内元组的概率加权线性均值,即1/p c C PF p =uuuu r

容易验证,若各元组的存在概率均为100%时,概率中心与几何中心匹配.

半径是簇的重要统计数据,描述簇的规模以及对新元组的吸附能力.在现有工作中,半径一般被定义为簇内各元组到中心点的距离平方和的均值的开方根.现以加权想法重新定义包含不确定元组的簇的半径,概率高的元组对簇的半径值影响更为显著,如下所示:

222222*********n n i i i i i c i i c i i c c c c c PF PF PF p X PF p PF R p X p p X p p p p p p ==??????????????=?=?+=??????????????????

?∑∑uuuur uuuu r uuuu r uu ruuuu r uuuu r uu r uu r . 由图1可以观察到,簇的质量不仅与簇内元组的相似性程度有关,也与簇内元组的存在概率有关.一般来说,如果簇内元组的相似性越高(即半径越小),则簇的质量越高;如果簇内元组的平均存在概率越高,则簇的质量也会提升.鉴于此,我们定义Q 来描述簇的质量.

定义3.4. 一个簇的质量Q 与簇内元组的平均概率成正比,与半径成反比,即Q =p c /(n ?R ).

对于任一簇而言,新元组的加入会导致簇的质量Q 出现3种可能的变化情况:首先,若该元组的概率值高于簇的平均概率值时,且该元组与中心点距离较近,则该元组的加入能够提高簇的质量;其次,若新元组的概率值低于簇的平均概率值,且该元组离中心点距离较远,则该元组的加入将降低簇的质量;最后,若新元组概率高且离中心点远,或者概率低且离中心点近,则簇质量的变化趋势需要通过进一步的计算才能得到.

3 聚类算法

本节描述新的EMicro 算法,以处理不确定数据流聚类问题.如图2所示,在现有的主流数据流聚类算法(例如CluStream 或UMicro)中,当新元组无法被任何现有微簇吸收时,则将其认定为种子点,并创建新微簇.然而,若新元组实际上是离群点而非新簇的起点时,这些策略却对现有微簇集合产生了负面的影响.EMicro 算法拟采用一种新缓冲机制来处理这种情况.

首先,在内存中保存两类缓冲区:核心微簇缓冲区(BUF C )和离群点微簇缓冲区(BUF O ),分别存放微簇(即

UCF ).核心微簇缓冲区对正常元组进行聚类;离群点缓冲区用于检验离群点,并判断是否将其提升到核心微簇缓冲区之中或者直接删除.令n c 与n o 分别表示核心微簇缓冲区和离群点缓冲区的规模,n ratio 表示算法使用的最大微簇数目,易知n ratio =n c +n o .EMicro 算法的细节见算法1.

张晨等:一种不确定数据流聚类算法 2177

算法1. Emicro

1. 将核心微簇缓冲区BUF C 与离群点微簇缓冲区BUF O 初始化为空;

2. while (新元组(X uu v

,p )到达)

3. if (核心微簇缓冲区未满,即|BUF C |

4 创建仅包含(X uu v

,p )的UCF ,并加入BUF C 中; 5 else

6. C c =FindOptimalCluster (X uu v

,p ,BUF C );

7. if (C c is not NULL ) //说明(X uu v

,p )能够被某一核心微簇所吸收

8. 核心微簇C c 吸收(X uu v

,p ); 9. else

10. if (离群点微簇缓冲区未满,即|BUF O |

11. 创建仅包含(X uu v

,p )的UCF ,并加入BUF O 中; 12. else

13. C o =FindOptimalCluster (X uu v

,p ,BUF O );

14. if (C o is not NULL ) //说明(X uu v

,p )能被某一离群点微簇所吸收

15. 离群点C o 吸收(X uu v

,p ); 16. else

17. delete (X uu v ,p ); //(X uu v

,p )是全局离群点 18. CheckClustersProcess (); //对微簇进行调整维护

在EMicro 中,对于新到达的元组(X uu v ,p ),首先判断核心微簇缓冲区是否已满,如果未满,则创建仅包含(X uu v

,p )的UCF ,并加入到BUF C 中(第4行);反之,若核心微簇缓冲区已满,则需通过调用FindOptimalCluster 函数来判断

这个新元组是否能够被现有的核心微簇缓冲区成员所吸收.若返回结果不为NULL ,则C c 将吸收(X uu v

,p )(第8行);若返回NULL ,则认定该新元组是一个潜在的离群点,需做进一步的判断.如果离群点微簇缓冲区未满,则创建一

个仅包含(X uu v

,p )的微簇,加入到BUF O 中去(第11行);否则,尝试在离群点微簇缓冲区中寻找最合适的微簇吸收之.如果找不到目标簇,则直接删除该元组(第13~17行).最后,算法调用CheckClustersProcess 函数对微簇缓冲区进行调整维护(第18行).

3.1 簇选择算法FindOptimalCluster

FindOptimalCluster 用于在一个微簇集合中找到一个能够吸收元组(X uu v

,p )的最合适的微簇.首先,计算各个

微簇的半径以及元组(X uu v

,p )与各微簇的概率中心之间的距离.若元组到簇的距离大于簇半径的τ倍(通常τ=3[2]),则可认为该元组无法被任何簇所吸收,返回NULL ;反之,该元组能够被某一簇吸收.若存在多个满足半径限制的微簇,则返回一个最优的微簇(即概率引力值最高,见定义4.1).

定义4.1(概率引力). 元组(X uu v ,p )到微簇(2,1,,,)c UCF PF PF n p t =uuuur uuuu r 的概率引力为p c /d 2,其中,d 为元组(X uu v

,p )

到UCF 的概率中心的距离.

定义 4.1源于一个朴素的观察:当新元组(X uu v

,p )越靠近一个微簇,则越有可能被该微簇所吸附;当微簇内元

组的概率和越大时,则该微簇内的元组越密集,对新元组(X uu v

,p )的吸附能力越强.事实上,这个思想与物理学中的万有引力思想有相似之处.

3.2 簇进化算法CheckClustersProcess

算法2.

1. 核心微簇缓冲区与离群点微簇缓冲区分别以λC 和λO 衰减;

2. while (两个缓冲区存在某微簇,其权重比低于ρ)

3. 从缓冲区中移除该微簇;

4. while (min(w (u )|u ∈BUF C )

2178 Journal of Software 软件学报 V ol.21, No.9, September 2010

5. 在两个缓冲区间交换相应的微簇;

6. while (核心微簇缓冲区BUF C 未满,且离群点微簇缓冲区BUF O 非空)

7. 将BUF O 中权重值等于max(w (u )|u ∈BUF O )的微簇移到BUF C 中;

在CheckClustersProcess 算法中,首先需要对两个缓冲区进行衰减操作.所谓衰减,是指元组(或微簇)的重要

性随着时间的推移而逐步减弱,新元组的重要性比旧元组高.常用的衰减方法是指数衰减法.若元组(X uu v

,p )在t 1

时刻到达,则在t 2时刻,该元组的权重为21()(,)2t t w X p p λ??=?uu r

,其中,λ为衰减速率.λ的取值越大,则衰减越快.微簇的权重也可以依此定义.假设微簇u 包含n 个元组{(x i ,p i )},分别于T 1,…,T n 到达,则在T 时刻微簇u 的权重为

()1()2i n

T T i i w u p λ??==∑.易知,每过一个单位时间,微簇的权重等于在原权重基础上乘以2?λ.如果为每个UCF 额外附加表征权重的w 字段,则该字段总是容易维护的.CheckClustersProcess 算法对核心微簇缓冲区与离群点微簇缓冲区采用不同的衰减速率,分别记为λC 和λO .如果数据流中存在较大的进化性,希望聚类过程能够敏感地反映出这种进化特征时(即尽快地发现新簇),那么应该设置λO <λC ;反之,如果用户更加关注结果的稳定性,或者根据领域知识能够判断出数据流进化的相对平缓(不会经常出现新簇)的情况下,那么可以设置λC <λO (第1行).

其次,检查各个缓冲区是否存在过于陈旧的微簇.若有,则从内存中移除.我们采用权重比参数进行检验.如前所述,微簇的p c 字段表示该微簇的概率和,则可将微簇u 的权重比定义为w (u )/p c ,该值位于[0,1]之间.然后可将权重比与预定义的参数ρ进行比较,若小于ρ,则表示构成该微簇的元组大多较为陈旧,可以将其从内存中移除

(第2~3行).

再次,随着新元组的不断到达,两个缓冲区不断演化,导致核心微簇缓冲区中的部分微簇的权重反而低于离群点微簇缓冲区中的微簇.此时就触发交换机制,将离群点微簇缓冲区中权重最高的微簇移到核心微簇缓冲区中,将核心微簇缓冲区中权重最低的微簇移到离群点微簇缓冲区中,最终使得核心微簇缓冲区中的微簇均比离群点微簇缓冲区中的微簇更加重要(第4~5行).

最后,若核心缓冲区未满,则需要从离群点缓冲区中将权重最高的微簇移至核心微簇缓冲区中,直至核心微簇缓冲区充满为止(第6~7行). 3.3 分析

CheckClustersProcess 算法提供了两个参数来实现对离群点的支持:第1个参数是缓冲比参数,描述离群点微簇缓冲区的大小占全部缓冲区大小的比率,记为α=n o /(n c +n o ).假设总空间开销不变,则缓冲比的值越高,可分配给潜在的离群点的空间越大,对离群点的支持越充分;第2个参数是衰减速率比(λratio =λc /λo ),描述不同缓冲区的衰减速度比较.换句话说,该参数描述了对不同类型的微簇的倾向性,可以通过对核心微簇与缓冲微簇采用不同的衰减率来调整是倾向于重视离群点还是倾向于忽视离群点.

4 实验分析

4.1 实验设置

本节以UMicro [3]为基准算法来验证EMicro 的性能.两个算法均由matlabV14R7工具实现,运行在一台配置了Pentium IV 3.0GHz 的CPU 的电脑上,操作系统是Windows XP Professional.

我们首先设计3个确定性数据集合,包括一个模拟数据集和两个真实数据集,然后再将其转化成相应的不确定数据集.确定性数据集如下所示:

? 模拟数据集Syndrift.首先,随机选定一系列簇中心点,半径也随机设定.随着时间推移,不断调整半径值(每次调整±ε),以模拟簇漂移现象.簇内元组的总体分布满足高斯分布,总共产生60万条记录.

? 真实数据集1:网络入侵检测(network intrusion detection)数据集.该数据集包括一个局域网内某一时段的TCP(transfer control protocol)连接日志记录,含持续时间、传输字节数等属性.每条记录对应于一个正常的连接或者是4种类型的网络攻击之一,例如拒绝服务攻击、

非授权访问远程机器攻击等.我们从42个属性中选取34

张晨等:一种不确定数据流聚类算法 2179

个数值型属性.

? 真实数据集2:Forest Covertype 数据集[18],含581 012个元组,从全部54个属性中选取10个数值型属性. UMicro 与EMicro 所针对的不确定数据流模型不同.EMicro 算法仅考虑存在级不确定性,而不考虑属性级不确定性;UMicro 算法仅考虑属性级不确定性,而不考虑存在级不确定性,二者无法运行在同一不确定性数据集合上.因此,本文采取一种折衷的方法:即从同一确定性数据集合D 开始分别构造不确定数据集D 1和D 2,D 1仅含存在级不确定性,D 2仅含属性级不确定性.换句话说,对于任一D 中的元组X ,转变到D 1之中的元组时描述为(X ,p ),p 在[0,1]之间随机选取;转变到D 2之中的元组时,元组的期望值仍为X ,方差是(1?p )X .易知,若p 值较大,则在D 1和D 2中对应元组的不确定性均较小;反之若p 值较小,则在D 1和D 2中对应元组的不确定性均较大.同时,拟在将来工作中考虑如何基于同一数据集进一步分析两种算法的性能优劣.

现有方法采用距离平方和SSQ 描述聚类结果的质量,但是该度量仅考虑距离因素,无法描述存在概率对聚类结果的影响.因此,本文采用平均簇质量AQ 作为度量基准,即AQ =avg (Q i ).

EMicro 与UMicro 采用相同的离线聚类算法,详见文献[2,3,19].其基本思想是:把任意核心微簇C i 看作是一个落在其概率中心且权重为w (C i )的虚拟点,再采用加权k -means 算法对这些虚拟点进行聚类,以生成聚类结果.除特别标明,EMicro 算法中的参数设置如下:缓冲比α=3%,衰减速率比λratio =1,收纳半径阈值τ =3.UMicro 算法的参数设置为:权重比阈值ρ=1/50,误差参数μ=0.5,衰减系数λ=0.1,收纳半径阈值τ =3. 4.2 聚类效果

图3分别比较了EMicro 和UMicro 在网络入侵检测数据集和森林数据集上的聚类结果质量.横轴是数据流量,纵轴是平均质量.可以看出,EMicro 的性能指标远优于UMicro,其主要原因是,EMicro 在分配新元组到现有微簇的过程中同时考虑了距离因素和概率因素.尽管该方法并非以最小化SSQ 为目标,但在很多情况下,EMicro 的

SSQ 指标也会优于UMicro,见表1.原因是UMicro 算法引入了误差维度,导致单个元组的可能范围变大,从而增大了SSQ 计算过程中的簇内距离,进而降低了聚类质量.

(a) Network intrusion detection dataset (b) Forest covertype dataset

(a) 网络入侵检测数据集 (b) 森林覆盖类型数据集

Fig.3 Quality comparison between EMicro and UMicro

图3 EMicro 与UMicro 的聚类质量比较 Table 1 SSQ comparison between EMicro and UMicro

表1 EMicro 与UMicro 的SSQ 的比较

(a) Network intrusion detection dataset

0.5×105

1×105 2×105 3×105 4×105

UMicro-SSQ 2.95E+11 1.38E+11 1.38E+117.19E+109.18E+10 EMicro-SSQ

1.69E+11 9.65E+108.19E+109.97E+10

2.42E+10

(b) Forest covertype dataset

1.0×105 2×105 3×105 4×105

5×105 UMicro-SSQ 5.21E+09 6.07E+09 2.7543+09 3.76E+09 2.54E+09 EMicro-SSQ

3.91E+09 1.31E+09 5.97E+08

3.30E+08

1.19E+07

1 2 4 6 8

Progression of stream (points *5E+4)

0.300.25

0.200.150.100.050.00

A v e r a g e q u a l i t y o f c l u s t e r s

Umicro EMicro

1 2 3 4 5

Progression of stream (points *1E+5)

0.70.60.50.40.3

A v e r a g e q u a l i t y o f c l u s t e r s

Umicro EMicro

2180

Journal of Software 软件学报 V ol.21, No.9, September 2010

4.3 时间复杂度

时间复杂度是数据流算法的重要指标,影响EMicro 与UMicro 时间开销的主要部分为在线统计微簇信息和存储快照的频率.为了比较两个算法的效率,我们设置相同的快照频率,然后比较在线微聚类部分的性能.

图4展示了EMicro 在不同数据集上的处理结果,横轴表示数据流量,纵轴表示处理时间. UMicro 与确定数据相比,由于需要增加一套维度来描述误差信息,因此会加大每个维度上的计算开销;同时,维度较低带来的开销下降大于计算概率因素带来的性能消耗.实验结果显示,EMicro 与UMicro 算法的执行时间都会随数据流长度呈线性增长,可以达到每秒数千点的处理速度,但EMicro 算法更快. EMicro

(a) Network intrusion detection dataset (b) Forest covertype dataset

(a) 网络入侵检测数据集 (b) 森林覆盖类型数据集

Fig.4 Time comparison between EMicro and UMicro

图4 EMicro 与UMicro 的运行时间比较

图5显示了基于模拟数据的测试结果.模拟数据集可以获得任意的维度,并对初始化的微簇个数进行调整.首先,数据集的微簇个数从200变化到1 600,并固定数据流的长度和维度,图5(a)显示,EMicro 的处理时间随簇的个数呈近线性增长.其次,改变数据集的维度,从10变化到80,并固定数据流的长度和簇个数,图5(b)显示,

EMicro 的处理时间随维度线性增长.因此,算法的可扩展性较强.

(a) Time vs. number of micro clusters (b) Time vs. dimensions

(a) 处理时间与微簇个数的对比 (b) 处理时间与数据集维度的对比

Fig.5 The scalability of EMicro 图5 EMicro 算法的可扩展性

4.4 离群点处理机制与参数影响

最后测试离群点处理机制的影响.我们使用Syndrift(ε)ε∈[0.05,0.3]数据集,ε越大,说明数据流进化的速度越快,离群点出现的机会越多.EMicro-Merge 与EMicro-Buffer 分别代表使用异常处理机制前后的聚类质量,实验

200 400 800 1600

Number of micro clusters

350

30025020015010050

T i m e (s )

SynDrift B400K-D40

SynDrift B400K-D20 SynDrift B400K-D10

10 20 40 80

Dimensions

500400300200100

T i m e (s )

SynDrift B400K-C400 SynDrift B400K-C800 SynDrift B400K-C1600

501001502002501

Progression of stream (points *1E+5)T i m e (s )

Umicro

Emicro

100

200300400

Progression of stream (points * 1E+5)

T i m e (s )

Umicro

Emicro

张晨等:一种不确定数据流聚类算法

2181

结果如图6所示.可以看出,使用离群点处理机制能显著改善聚类结果质量.

影响EMicro 聚类质量的两个主要参数是缓冲比α和衰减速率比λratio ,通过实验比较,可以为两者的设置提供一个合理的参考值.我们在数据集Syndrift 中设置了不同的α和λratio 来考察它们与平均概率簇质量AQ 和SSQ 的关系.我们先固定住λratio =1,分别设置α为2%,3%,5%,10%和20%.见表2,开始阶段,SSQ 和平均概率簇质量AQ 随α增大而增大,但AQ 增长最多的是在α从3%变化到5%.这说明当缓冲比α变大时,离群点在缓冲微簇中可以有更长的考察时间,致使提升为核心微簇的可能性变大,从而使得平均概率簇质量AQ 不断增大.但平均概率簇质量增大是以增大SSQ 为代价的,所以不同应用中可根据需要来设置α取得SSQ 和AQ 的折衷.当达到最大值后,AQ 的值有所下降.这是因为将过多的微簇用于离群点的监测,加快了核心微簇的频繁变动,导致聚类的性能与质量有所下降.这也进一步说明在离群点比例不是很高的情况下,过度地分配资源给缓冲微簇是不必要的.

Table 2 Accuracy impact of buffer-ratios

表2 缓冲比对准确性的影响

α=2% α=3% α=5% α=10% α=20% SSQ AQ SSQ AQ SSQ AQ SSQ AQ SSQ AQ 13.928 307.72

18.712 352.95 23.204466.11

28.241310.5

50.421 311.72

最后固定α=3%,分别设置λratio 为0.7,0.8,0.9,1,1.1,1.2和1.3.从图7中可以看出,当λratio <1时有利于相对稳定的Syndrift(ε=0.05)数据集.但当λratio >1时,则更加有利于进化特性比较明显Syndrift(ε=0.3)数据集.

Fig.6 Accuracy impact of abnormal processing mechanism Fig.7 Accuracy impacts of decay-ratio

图6 异常处理机制对准确性的影响图7 衰减速率比对准确性的影响

5 结论与展望

本文提出一种针对不确定数据流的聚类算法EMicro,各元组具有存在级不确定性.该算法同时考虑元组间的距离因素与不确定性因素,更全面地描述了聚类结果质量.EMicro 算法的另一亮点在于提供了对离群点处理的充分支持.该算法在内存中保留了两份缓冲区,分别对应正常的微簇与潜在离群点的微簇,并提供了两个缓冲区的管理策略.实验结果表明,与现有算法相比,本文提出的EMicro 算法在聚类质量、处理速度等方面均有优势.未来拟扩展该项技术,以解决滑动窗口模型下的聚类问题. References

[1] Babcock B, Babu S, Datar M, Motwani R, Widom J. Models and issues data stream systems. In: Proc. of the 21st ACM SIGACT-

SIGMOD-SIGART Symp. on Principles of Database Systems. Madison: ACM, 2002. 1?16.

[2] Aggarwal CC, Han JW, Yu PS. A framework for clustering evolving data streams. In: Proc. of the 29th Int’l Conf. on Very Large

Data Bases. Berlin: Morgan Kaufmann Publishers, 2003. 81?92.

[3] Aggarwal CC, Yu PS. A framework for clustering uncertain data streams. In: Proc. of the 24th Int’l Conf. on Data Engineering.

Cancún: IEEE, 2008. 150?159.

[4] Callaghan LO, Mishra N, Meyerson A, Guha S, Motwani R. Streaming-Data algorithms for high-quality clustering. In: Proc. of the

18th Int’l Conf. on Data Engineering. San Jose: IEEE, 2002. 685?694.

0.05 0.1 0.15 0.2 0.25 0.3

Drift parameter ε10008006004002000

A v e r a g e q u a l i t y o f c l u s t e r s

EMicro-Merge EMicro-Buffer

0.7 0.8 0.9 1 1.1 1.2 1.3

Decay-Ratios λ

6005004003002001000

A v e r a g e q u a l i t y o f c l u s t e r s

Syndrift (ε=0.3)

Syndrift (ε=0.05) 700

2182 Journal of Software软件学报 V ol.21, No.9, September 2010

[5] Zhu WH, Yin J, Xie YH. Arbitrary shape cluster algorithm for clustering data stream. Journal of Software, 2006,17(3):379?387 (in

Chinese with English abstract). https://www.wendangku.net/doc/4a15250287.html,/1000-9825/17/379.htm [doi: 10.1360/jos170379]

[6] Datar M, Gionis A, Indyk P, Motwani R. Maintaining stream statistics over sliding windows. In: Proc. of the 13th Annual ACM-

SIAM Symp. on Discrete Algorithms. San Francisco: ACM, 2002. 635?644.

[7] Babcock B, Datar M, Motwani R, Callaghan LO. Maintaining variance and k-medians over data stream windows. In: Proc. of the

22nd ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. San Diego: ACM, 2003. 234?243.

[8] Cao F, Estery M, Qian WN, Zhou AY. Density-Based clustering over an evolving data stream with noise. In: Proc. of the 6th SIAM

Int’l Conf. on Data Mining. Bethesda: SIAM, 2006. 326?337.

[9] Kriegel HP, Pfeifle M. Density-Based clustering of uncertain data. In: Proc. of the 11th ACM SIGKDD Int’l Conf. on Knowledge

Discovery and Data Mining. Chicago: ACM, 2005. 672?677.

[10] Kriegel HP, Pfeifle M. Hierarchical density-based clustering of uncertain data. In: Proc. of the 5th IEEE Int’l Conf. on Data Mining.

Houston: IEEE Computer Society, 2005. 689?692.

[11] Ngai WK, Kao B, Chui CK, Cheng R, Chau M, Yip KY. Efficient clustering of uncertain data. In: Proc. of the 6th IEEE Int’l Conf.

on Data Mining. Hong Kong: IEEE Computer Society, 2006. 436?445.

[12] Zhang T, Ramakrishnan R, Livny M. Birch: An efficient data clustering method for very large databases. In: Proc. of the 1996

ACM SIGMOD Int’l Conf. on Management of Data. Montreal: ACM, 1996. 103?114.

[13] Aggarwal CC. On high dimension projected clustering of uncertain data streams. In: Proc. of the 25th Int’l Conf. on Data

Engineering. Shanghai: IEEE, 2009. 1152?1154.

[14] Zhang C, Gao M, Zhou AY. Tracking high quality clusters over uncertain data streams. In: Proc. of the 1st Workshop on

Management and Mining of Uncertain Data (MOUND 2009). Joint with ICDE 2009. Shanghai: IEEE, 2009. 1641?1648.

[15] Cormode G, McGregor A. Approximation algorithms for clustering uncertain data. In: Proc. of the 22nd ACM SIGACT-SIGMOD-

SIGART Symp. on Principles of Database Systems. Vancouver: ACM, 2008. 191?200.

[16] Kanagal B, Deshpande A. Online filtering, smoothing and probabilistic modeling of streaming data. In: Proc. of the 24th Int’l Conf.

on Data Engineering. Cancún: IEEE, 2008. 1160?1169.

[17] Ré C, Letchner J, Balazinska M, Suciu D. Event queries on correlated probabilistic streams. In: Proc. of the ACM SIGMOD Int’l

Conf. on Management of Data. Vancouver: ACM, 2008. 715?728.

[18] Newman DJ, Hettich S, Blake CL, Merz CJ. UCI repository of machine learning databases. https://www.wendangku.net/doc/4a15250287.html,/ml/

[19] Aggarwal CC, Han JW, Wang JY, Yu PS. A framework for projected clustering of high dimensional data streams. In: Proc. of the

13th Int’l Conf. on Very Large Data Bases. Toronto: Morgan Kaufmann Publishers, 2004. 852?863.

附中文参考文献:

[5] 朱蔚恒,印鉴,谢益煌.基于数据流的任意形状聚类算法.软件学报,2006,17(3):379?387. https://www.wendangku.net/doc/4a15250287.html,/1000-9825/17/379.

htm [doi: 10.1360/jos170379]

张晨(1980－),男,上海人,博士生,主要研究领域为数据挖掘,数据流挖掘,不确定数据管理.

周傲英(1965－),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为数据库,数据挖掘,XML数据管理,Web搜索,P2P计算和系统

金澈清(1977－),男,博士,副教授,主要研

究领域为数据流管理,不确定数据管理,移

动数据管理.

MATLAB实现FCM 聚类算法

本文在阐述聚类分析方法的基础上重点研究FCM 聚类算法。FCM 算法是一种基于划分的聚类算法，它的思想是使得被划分到同一簇的对象之间相似度最大，而不同簇之间的相似度最小。最后基于MATLAB实现了对图像信息的聚类。第 1 章概述聚类分析是数据挖掘的一项重要功能，而聚类算法是目前研究的核心，聚类分析就是使用聚类算法来发现有意义的聚类，即“物以类聚” 。虽然聚类也可起到分类的作用，但和大多数分类或预测不同。大多数分类方法都是演绎的，即人们事先确定某种事物分类的准则或各类别的标准，分类的过程就是比较分类的要素与各类别标准，然后将各要素划归于各类别中。确定事物的分类准则或各类别的标准或多或少带有主观色彩。为获得基于划分聚类分析的全局最优结果，则需要穷举所有可能的对象划分，为此大多数应用采用的常用启发方法包括：k-均值算法，算法中的每一个聚类均用相应聚类中对象的均值来表示；k-medoid 算法，算法中的每一个聚类均用相应聚类中离聚类中心最近的对象来表示。这些启发聚类方法在分析中小规模数据集以发现圆形或球状聚类时工作得很好，但当分析处理大规模数据集或复杂数据类型时效果较差，需要对其进行扩展。而模糊C均值(Fuzzy C-means, FCM)聚类方法，属于基于目标函数的模糊聚类算法的范畴。模糊C均值聚类方法是基于目标函数的模糊聚类算法理论中最为完善、应用最为广泛的一种算法。模糊c均值算法最早从硬聚类目标函数的优化中导出的。为了借助目标函数法求解聚类问题，人们利用均方逼近理论构造了带约束的非线性规划函数，以此来求解聚类问题，从此类内平方误差和WGSS(Within-Groups Sum of Squared Error)成为聚类目标函数的普遍形式。随着模糊划分概念的提出，Dunn [10] 首先将其推广到加权WGSS 函数，后来由Bezdek 扩展到加权WGSS 的无限族，形成了FCM 聚类算法的通用聚类准则。从此这类模糊聚类蓬勃发展起来，目前已经形成庞大的体系。第 2 章聚类分析方法 2-1 聚类分析聚类分析就是根据对象的相似性将其分群，聚类是一种无监督学习方法，它不需要先验的分类知识就能发现数据下的隐藏结构。它的目标是要对一个给定的数据集进行划分，这种划分应满足以下两个特性：①类内相似性：属于同一类的数据应尽可能相似。②类间相异性：属于不同类的数据应尽可能相异。图2.1是一个简单聚类分析的例子。

数据挖掘中的聚类分析方法

计算机工程应用技术本栏目责任编辑：贾薇薇数据挖掘中的聚类分析方法黄利文（泉州师范学院理工学院，福建泉州３６２０００）摘要：聚类分析是多元统计分析的重要方法之一，该方法在许多领域都有广泛的应用。本文首先对聚类的分类做简要的介绍，然后给出了常用的聚类分析方法的基本思想和优缺点，并对常用的聚类方法作比较分析，以便人们根据实际的问题选择合适的聚类方法。关键词：聚类分析；数据挖掘中图分类号：ＴＰ３１１文献标识码：Ａ文章编号：１００９－３０４４（２００８）１２－２０５６４－０２ＣｌｕｓｔｅｒＡｎｌａｙｓｉｓＭｅｔｈｏｄｓｏｆＤａｔａＭｉｎｉｎｇＨＵＡＮＧＬｉ－ｗｅｎ（ＳｃｈｏｏｌｏｆＳｃｉｅｎｃｅ，ＱｕａｎｚｈｏｕＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｑｕａｎｚｈｏｕ３６２０００，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｃｌｕｓｔｅｒａｎａｌｙｓｉｓｉｓｏｎｅｏｆｔｈｅｉｍｐｏｒｔａｎｔｍｅｔｈｏｄｓｏｆｍｕｌｔｉｖａｒｉａｔｅｓｔａｔｉｓｔｉｃａｌａｎａｌｙｓｉｓ，ａｎｄｔｈｉｓｍｅｔｈｏｄｈａｓａｗｉｄｅｒａｎｇｅｏｆａｐｐｌｉｃａ－ｔｉｏｎｓｉｎｍａｎｙｆｉｅｌｄｓ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎｏｆｔｈｅｃｌｕｓｔｅｒｉｓｉｎｔｒｏｄｕｃｅｄｂｒｉｅｆｌｙ，ａｎｄｔｈｅｎｇｉｖｅｓｓｏｍｅｃｏｍｍｏｎｍｅｔｈｏｄｓｏｆｃｌｕｓｔｅｒａｎａｌｙｓｉｓａｎｄｔｈｅａｄｖａｎｔａｇｅｓａｎｄｄｉｓａｄｖａｎｔａｇｅｓｏｆｔｈｅｓｅｍｅｔｈｏｄｓ，ａｎｄｔｈｅｓｅｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｗｅｒｅｃｏｍｐａｒｅｄａｎｄａｎｓｌｙｚｅｄｓｏｔｈａｔｐｅｏｐｌｅｃａｎｃｈｏｓｅｓｕｉｔａｂｌｅｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｓａｃｃｏｒｄｉｎｇｔｏｔｈｅａｃｔｕａｌｉｓｓｕｅｓ．Ｋｅｙｗｏｒｄｓ：ＣｌｕｓｔｅｒＡｎａｌｙｓｉｓ；ＤａｔａＭｉｎｉｎｇ１引言聚类分析是数据挖掘中的重要方法之一，它把一个没有类别标记的样本集按某种准则划分成若干个子类，使相似的样品尽可能归为一类，而不相似的样品尽量划分到不同的类中。目前，该方法已经被广泛地应用于生物、气候学、经济学和遥感等许多领域，其目的在于区别不同事物并认识事物间的相似性。因此，聚类分析的研究具有重要的意义。本文主要介绍常用的一些聚类方法，并从聚类的可伸缩性、类的形状识别、抗“噪声”能力、处理高维能力和算法效率五个方面对其进行比较分析，以便人们根据实际的问题选择合适的聚类方法。２聚类的分类聚类分析给人们提供了丰富多彩的分类方法，这些方法大致可归纳为以下几种［１，２，３，４］：划分方法、层次方法、基于密度的聚类方法、基于网格的聚类方法和基于模型的聚类方法。２．１划分法（ｐａｒｔｉｔｉｏｎｇｉｎｇｍｅｔｈｏｄｓ）给定一个含有ｎ个对象（或元组）的数据库，采用一个划分方法构建数据的ｋ个划分，每个划分表示一个聚簇，且ｋ≤ｎ。在聚类的过程中，需预先给定划分的数目ｋ，并初始化ｋ个划分，然后采用迭代的方法进行改进划分，使得在同一类中的对象之间尽可能地相似，而不同类的中的对象之间尽可能地相异。这种聚类方法适用于中小数据集，对大规模的数据集进行聚类时需要作进一步的改进。２．２层次法（ｈｉｅｔａｒｃｈｉｃａｌｍｅｔｈｏｄｓ）层次法对给定数据对象集合按层次进行分解，分解的结果形成一颗以数据子集为节点的聚类树，它表明类与类之间的相互关系。根据层次分解是自低向上还是自顶向下，可分为凝聚聚类法和分解聚类法：凝聚聚类法的主要思想是将每个对象作为一个单独的一个类，然后相继地合并相近的对象和类，直到所有的类合并为一个，或者符合预先给定的终止条件；分裂聚类法的主要思想是将所有的对象置于一个簇中，在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者符合预先给定的终止条件。在层次聚类法中，当数据对象集很大，且划分的类别数较少时，其速度较快，但是，该方法常常有这样的缺点：一个步骤（合并或分裂）完成，它就不能被取消，也就是说，开始错分的对象，以后无法再改变，从而使错分的对象不断增加，影响聚类的精度，此外，其抗“噪声”的能力也较弱，但是若把层次聚类和其他的聚类技术集成，形成多阶段聚类，聚类的效果有很大的提高。２．３基于密度的方法（ｄｅｎｓｉｔｙ－ｂａｓｅｄｍｅｔｈｏｄｓ）该方法的主要思想是只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对于给定的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法就可以用来滤处＂噪声＂孤立点数据，发现任意形状的簇。２．４基于网格的方法（ｇｒｉｄ－ｂａｓｅｄｍｅｔｈｏｄｓ）这种方法是把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作都在这个网格结构上进行。用这种方法进行聚类处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。２．５基于模型的方法（ｍｏｄｅｌ－ｂａｓｅｄｍｅｔｈｏｄ）基于模型的方法为每个簇假定一个模型，寻找数据对给定模型的最佳拟合。该方法经常基于这样的假设：数据是根据潜在的概收稿日期：２００８－０２－１７作者简介：黄利文（１９７９－），男，助教。

数据挖掘聚类算法课程设计报告

数据挖掘聚类问题(Plants Data Set)实验报告 1.数据源描述 1.1数据特征本实验用到的是关于植物信息的数据集，其中包含了每一种植物(种类和科属)以及它们生长的地区。数据集中总共有68个地区，主要分布在美国和加拿大。一条数据(对应于文件中的一行)包含一种植物(或者某一科属)及其在上述68个地区中的分布情况。可以这样理解，该数据集中每一条数据包含两部分内容，如下图所示。图1 数据格式例如一条数据:abronia fragrans,az,co,ks,mt,ne,nm,nd,ok,sd,tx,ut,wa,wy。其中abronia fragrans是植物名称(abronia是科属，fragrans是名称)，从az一直到wy 是该植物的分布区域，采用缩写形式表示，如az代表的是美国Arizona州。植物名称和分布地区用逗号隔开，各地区之间也用逗号隔开。 1.2任务要求聚类。采用聚类算法根据某种特征对所给数据集进行聚类分析，对于聚类形成的簇要使得簇内数据对象之间的差异尽可能小，簇之间的差距尽可能大。 2.数据预处理 2.1数据清理所给数据集中包含一些对聚类过程无用的冗余数据。数据集中全部数据的组织结构是：先给出某一科属的植物及其所有分布地区，然后给出该科属下的具体植物及其分布地区。例如： ①abelmoschus,ct,dc,fl,hi,il,ky,la,md,mi,ms,nc,sc,va,pr,vi ②abelmoschus esculentus,ct,dc,fl,il,ky,la,md,mi,ms,nc,sc,va,pr,vi ③abelmoschus moschatus,hi,pr 上述数据中第①行给出了所有属于abelmoschus这一科属的植物的分布地区，接下来的②③两行分别列出了属于abelmoschus科属的两种具体植物及其分布地区。从中可以看出后两行给出的所有地区的并集正是第一行给出的地区集

数据挖掘算法综述

数据挖掘方法综述 [摘要]数据挖掘（DM，DataMining）又被称为数据库知识发现（KDD,Knowledge Discovery in Databases）,它的主要挖掘方法有分类、聚类、关联规则挖掘和序列模式挖掘等。 [关键词]数据挖掘分类聚类关联规则序列模式 1、数据挖掘的基本概念数据挖掘从技术上说是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、人们事先不知道的、但又是潜在的有用的信息和知识的过程。这个定义包括好几层含义: 数据源必须是真实的、大量的、含噪声的、发现的是用户感兴趣的知识, 发现的知识要可接受、可理解、可运用, 并不要求发现放之四海皆准的知识, 仅支持特定的发现问题, 数据挖掘技术能从中自动分析数据进行归纳性推理从中发掘出潜在的数据模式或进行预测, 建立新的业务模型帮助决策者调整策略做出正确的决策。数据挖掘是是运用统计学、人工智能、机器学习、数据库技术等方法发现数据的模型和结构、发现有价值的关系或知识的一门交叉学科。数据挖掘的主要方法有分类、聚类和关联规则挖掘等 2、分类分类（Classification）又称监督学习（Supervised Learning）。监

督学习的定义是：给出一个数据集D，监督学习的目标是产生一个联系属性值集合A和类标（一个类属性值称为一个类标）集合C的分类/预测函数，这个函数可以用于预测新的属性集合（数据实例）的类标。这个函数就被称为分类模型（Classification Model），或者是分类器（Classifier）。分类的主要算法有：决策树算法、规则推理、朴素贝叶斯分类、支持向量机等算法。决策树算法的核心是Divide-and-Conquer的策略，即采用自顶向下的递归方式构造决策树。在每一步中，决策树评估所有的属性然后选择一个属性把数据分为m个不相交的子集，其中m是被选中的属性的不同值的数目。一棵决策树可以被转化成一个规则集，规则集用来分类。规则推理算法则直接产生规则集合，规则推理算法的核心是Separate-and-Conquer的策略，它评估所有的属性-值对（条件），然后选择一个。因此，在一步中，Divide-and-Conquer策略产生m条规则，而Separate-and-Conquer策略只产生1条规则，效率比决策树要高得多，但就基本的思想而言，两者是相同的。朴素贝叶斯分类的基本思想是：分类的任务可以被看作是给定一个测试样例d后估计它的后验概率，即Pr（C=c j︱d），然后我们考察哪个类c j对应概率最大，便将那个类别赋予样例d。构造朴素贝叶斯分类器所需要的概率值可以经过一次扫描数据得到，所以算法相对训练样本的数量是线性的，效率很高，就分类的准确性而言，尽管算法做出了很强的条件独立假设，但经过实际检验证明，分类的效果还是

PAM聚类算法的分析与实现

毕业论文（设计）论文（设计）题目：PAM聚类算法的分析与实现系别：专业：学号：姓名：指导教师：时间：

毕业论文（设计）开题报告系别:计算机与信息科学系专业:网络工程学号姓名高华荣论文（设计）题目PAM聚类算法的分析与实现命题来源□√教师命题□学生自主命题□教师课题选题意义(不少于300字): 随着计算机技术、网络技术的迅猛发展与广泛应用，人们面临着日益增多的业务数据，这些数据中往往隐含了大量的不易被人们察觉的宝贵信息，为了得到这些信息，人们想尽了一切办法。数据挖掘技术就是在这种状况下应运而生了。而聚类知识发现是数据挖掘中的一项重要的内容。在日常生活、生产和科研工作中，经常要对被研究的对象经行分类。而聚类分析就是研究和处理给定对象的分类常用的数学方法。聚类就是将数据对象分组成多个簇，同一个簇中的对象之间具有较高的相似性，而不同簇中的对象具有较大的差异性。在目前的许多聚类算法中，PAM算法的优势在于：PAM算法比较健壮，对“噪声”和孤立点数据不敏感；由它发现的族与测试数据的输入顺序无关；能够处理不同类型的数据点。研究综述(前人的研究现状及进展情况，不少于600字): PAM（Partitioning Around Medoid,围绕中心点的划分）算法是是划分算法中一种很重要的算法，有时也称为k-中心点算法，是指用中心点来代表一个簇。PAM算法最早由Kaufman和Rousseevw提出，Medoid的意思就是位于中心位置的对象。PAM算法的目的是对n个数据对象给出k个划分。PAM算法的基本思想：PAM算法的目的是对成员集合D中的N个数据对象给出k个划分，形成k个簇，在每个簇中随机选取1个成员设置为中心点，然后在每一步中，对输入数据集中目前还不是中心点的成员根据其与中心点的相异度或者距离进行逐个比较，看是否可能成为中心点。用簇中的非中心点到簇的中心点的所有距离之和来度量聚类效果，其中成员总是被分配到离自身最近的簇中，以此来提高聚类的质量。由于PAM算法对小数据集非常有效，但对大的数据集合没有良好的可伸缩性，就出现了结合PAM的CLARA（Cluster LARger Application）算法。CLARA是基于k-中心点类型的算法，能处理更大的数据集合。CLARA先抽取数据集合的多个样本，然后用PAM方法在抽取的样本中寻找最佳的k个中心点，返回最好的聚类结果作为输出。后来又出现了CLARNS（Cluster Larger Application based upon RANdomized

数据流聚类算法D-Stream

Density-Based Clustering for Real-Time Stream Data 基于密度的实时数据流聚类(D-Stream) 翻译by muyefei E-mail: muyefei@https://www.wendangku.net/doc/4a15250287.html, 注释：版权归作者所有，文档仅用于交流学习，可以用大纲视图查看文档结构摘要：现有的聚类算法比如CluStream是基于k-means算法的。这些算法不能够发现任意形状的簇以及不能处理离群点。而且，它需要预先知道k值和用户指定的时间窗口。为了解决上述问题，本文提出了D-Stream算法，它是基于密度的算法。这个算法用一个在线部分将数据映射到一个网格，在离线部分计算网格的密度然后基于密度形成簇。算法采用了密度衰减技术来捕获数据流的动态变化。为了探索衰减因子、数据密度以及簇结构之间的关系，我们的算法能够有效的并且有效率地实时调整簇。而且，我们用理论证明了移除那些属于离群点的稀疏网格是合理的，从而提高了系统的时间和空间效率。该技术能聚类高速的数据流而不损失聚类质量。实验结果表明我们的算法在聚类质量和效率是有独特的优势，并且能够发现任意形状的簇，以及能准确地识别实时数据流的演化行为。关键词流数据挖掘基于密度的聚类D-Stream 分散的网格 1 介绍实时聚类高维数据流是困难的但很重要。因为它在各个领域应用到。比如... 聚类是一项关键的数据挖掘任务。挖掘数据流有几项关键的挑战：（1）单遍扫描（2）将数据流视为数据一个很长的向量在很多应用中捉襟见肘，用户更加关注簇的演化行为。近来，出现了许多数据流聚类方法。比如STREAM、CluStream以及扩展（在多数据流，分布式数据流，并行数据流上的扩展）等。 CluStream以及扩展的算法有以下一些缺陷： 1、只能发现球形簇，不能发现任意形状的簇。 2、不能够识别噪声和离群点。 3、基于k-means的算法需要多次扫描数据（其实CluStream利用两阶段方法和微簇解决了该问题）。基于密度的聚类算法介绍。基于密度的方法可以发现任意形状的簇，可以处理噪声，对原始数据集只需一次扫描。而且，它不需要像k-means算法那样预先设定k值。文本提出了D-Stream,一种基于密度的数据流聚类框架。它不是简单用基于密度的算法替代k-means的数据流算法。它有两项主要的技术挑战：首先，我们不大愿意将数据流视为静态数据很长的一个序列，因为我们对数据流演化的时间特征更加感兴趣。为了捕获簇的动态变化，我们提出了一个新颖的方案，它可以将衰减

1基于网格的数据流聚类算法

3)国家自然科学基金(60172012)。刘青宝　博士生,副教授,主要研究方向为数据仓库技术和数据挖掘;戴超凡　博士,副教授,主要研究方向为数据仓库技术和数据挖掘;邓　苏　博士,教授,主要研究方向指挥自动化、信息综合处理与辅助决策;张维明　博士生导师,教授,主要研究方向为军事信息系统、信息综合处理与辅助决策。计算机科学2007Vol 134№13 　基于网格的数据流聚类算法3) 刘青宝　戴超凡　邓　苏　张维明 (国防科学技术大学信息系统与管理学院　长沙410073) 　摘　要　本文提出的基于网格的数据流聚类算法,克服了算法CluStream 对非球形的聚类效果不好等缺陷,不仅能在噪声干扰下发现任意形状的类,而且有效地解决了聚类算法参数敏感和聚类结果无法区分密度差异等问题。关键词　聚类,数据流,聚类参数,相对密度　 G rid 2based Data Stream Clustering Algorithm L IU Qing 2Bao DA I Chao 2Fan DEN G Su ZHAN G Wei 2Ming (College of Information System and Management ,National University of Defense Technology ,Changsha 410073) 　 Abstract With strong ability for discovering arbitrary shape clusters and handling noise ,grid 2based data stream cluste 2ring algorithm efficiently resolves these problem of being very sensitive to the user 2defined parameters and difficult to distinguish the density distinction of clusters.K eyw ords Clustering ,Data stream ,Clustering parameter ,Relative density 随着计算机和传感器技术的发展和应用,数据流挖掘技术在国内外得到广泛研究。它在网络监控、证券交易分析、电信记录分析等方面有着巨大的应用前景。特别在军事应用中,为了获得及时的战场态势信息,大量使用了各种传感器,对这些传感器数据流的分析处理已显得极为重要。针对数据流数据持续到达,且速度快、规模大等特点,数据流挖掘技术的研究重点是设计高效的单遍数据集扫描算法[12]。数据流聚类问题一直是吸引许多研究者关注的热点问题,已提出多种一次性扫描的方法和算法,如文[1～4]等等,但它们的聚类结果通常是球形的,不能支持对任意形状类的聚类[5]。本文提出的基于网格的数据流聚类算法,在有限内存条件下,以单遍扫描方式,不仅能在噪声干扰下发现任意形状的类,而且有效地解决了基于绝对密度聚类算法所存在的高密度聚类结果被包含在相连的低密度聚类结果中的问题。本文第1节简要介绍数据流聚类相关研究,并引出基于网格的数据流聚类算法的思路及其与相关研究的异同;第2节给出基于网格的数据流聚类算法所使用到的基本概念;第3节给出一个完整的基于网格的数据流聚类算法,详细解析算法的执行过程;第4节进行算法性能分析对比;最后总结本文的主要工作和贡献,并指出需要进一步研究和改进的工作。 1　相关研究在有限内存约束下,一般方法很难对数据流进行任意形状的聚类。第一个增量式聚类挖掘方法是文[6]提出的In 2crementalDBSCAN 算法,它是一个用于数据仓库环境(相对稳定的数据流)的有效聚类算法,可以在有噪声的数据集中发现任意形状的类。但是,它为了形成任意形状的类,必须用类中的所有点来表示,要求获得整个数据流的全局信息,这在内存有限情况下是难以做到的。而且,它采用全局一致的绝对密度作参数,使得聚类结果对参数值非常敏感,设置的细微不同即可能导致差别很大的聚类结果。 Aggarwal 在2003年提出的一个解决数据流聚类问题的框架CluStream [1]。它使用了两个过程来处理数据流聚类问题:首先,使用一个在线的micro 2cluster 过程对数据流进行初级聚类,并按一定的时间跨度将micro 2cluster 的结果按一种称为pyramid time f rame 的结构储存下来。同时,使用另一个离线的macro 2cluster 过程,根据用户的具体要求对micro 2cluster 聚类的结果进行再分析。但它采用距离作为度量参数,聚类结果通常是球形的,不能支持对任意形状类的聚类。而且,它维护的是micro 2cluster 的聚类特征向量(CF 2x ;CF 1x ;CF 2t ;CF 1t ;n ),这在噪声情况下,会产生干扰误差。 2006年,Feng Cao 等人在文[5]中提出了针对动态进化数据流的DenStream 算法。它相对CluStream 有很大的改进,继承了IncrementalDBSCAN 基于密度的优点,能够支持对有噪声的动态进化(非稳定)的数据流进行任意形状的聚类。但由于采用全局一致的绝对密度作参数,使得聚类结果对参数值非常敏感。同时,与CluStream 算法相比,它只能提供对当前数据流的一种描述,不能反映用户指定时间窗内的流数据的变化情况。朱蔚恒等在文[13]中提出的基于密度与空间的ACluS 2tream 聚类算法,通过引入有严格空间的意义聚类块,在对数据流进行初步聚类的同时,尽量保留数据的空间特性,有效克服了CluStream 算法不能支持对任意形状聚类的缺陷。但它在处理不属于已有聚类块的新数据点时,使用一种类似“抛硬币”的方法来猜测是否为该点创建一个新的聚类块,误差较大。而且它以绝对密度做参考,所以在聚类结果中无法区分密度等级不同的簇[7]。本文提出的基于网格的数据流聚类算法GClustream

各种聚类算法及改进算法的研究

论文关键词：数据挖掘；聚类算法；聚类分析论文摘要：该文详细阐述了数据挖掘领域的常用聚类算法及改进算法，并比较分析了其优缺点，提出了数据挖掘对聚类的典型要求，指出各自的特点，以便于人们更快、更容易地选择一种聚类算法解决特定问题和对聚类算法作进一步的研究。并给出了相应的算法评价标准、改进建议和聚类分析研究的热点、难点。上述工作将为聚类分析和数据挖掘等研究提供有益的参考。 1 引言随着经济社会和科学技术的高速发展，各行各业积累的数据量急剧增长，如何从海量的数据中提取有用的信息成为当务之急。聚类是将数据划分成群组的过程，即把数据对象分成多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。它对未知数据的划分和分析起着非常有效的作用。通过聚类，能够识别密集和稀疏的区域，发现全局的分布模式，以及数据属性之间的相互关系等。为了找到效率高、通用性强的聚类方法人们从不同角度提出了许多种聚类算法，一般可分为基于层次的，基于划分的，基于密度的，基于网格的和基于模型的五大类。 2 数据挖掘对聚类算法的要求(1)可兼容性：要求聚类算法能够适应并处理属性不同类型的数据。(2)可伸缩性：要求聚类算法对大型数据集和小数据集都适用。(3)对用户专业知识要求最小化。(4)对数据类别簇的包容性：即聚类算法不仅能在用基本几何形式表达的数据上运行得很好，还要在以其他更高维度形式表现的数据上同样也能实现。(5)能有效识别并处理数据库的大量数据中普遍包含的异常值，空缺值或错误的不符合现实的数据。(6)聚类结果既要满足特定约束条件，又要具有良好聚类特性，且不丢失数据的真实信息。(7)可读性和可视性：能利用各种属性如颜色等以直观形式向用户显示数据挖掘的结果。(8)处理噪声数据的能力。(9)算法能否与输入顺序无关。 3 各种聚类算法介绍随着人们对数据挖掘的深入研究和了解，各种聚类算法的改进算法也相继提出，很多新算法在前人提出的算法中做了某些方面的提高和改进，且很多算法是有针对性地为特定的领域而设计。某些算法可能对某类数据在可行性、效率、精度或简单性上具有一定的优越性，但对其它类型的数据或在其他领域应用中则不一定还有优势。所以，我们必须清楚地了解各种算法的优缺点和应用范围，根据实际问题选择合适的算法。 3.1 基于层次的聚类算法基于层次的聚类算法对给定数据对象进行层次上的分解，可分为凝聚算法和分裂算法。 (1)自底向上的凝聚聚类方法。这种策略是以数据对象作为原子类，然后将这些原子类进行聚合。逐步聚合成越来越大的类，直到满足终止条件。凝聚算法的过程为：在初始时，每一个成员都组成一个单独的簇，在以后的迭代过程中，再把那些相互邻近的簇合并成一个簇，直到所有的成员组成一个簇为止。其时间和空间复杂性均为O(n2)。通过凝聚式的方法将两簇合并后，无法再将其分离到之前的状态。在凝聚聚类时，选择合适的类的个数和画出原始数据的图像很重要。 [!--empirenews.page--] (2)自顶向下分裂聚类方法。与凝聚法相反，该法先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终结条件。其主要思想是将那些成员之间不是非常紧密的簇进行分裂。跟凝聚式方法的方向相反，从一个簇出发，一步一步细化。它的优点在于研究者可以把注意力集中在数据的结构上面。一般情况下不使用分裂型方法，因为在较高的层很难进行正确的拆分。 3.2 基于密度的聚类算法很多算法都使用距离来描述数据之间的相似性，但对于非凸数据集，只用距离来描述是不够的。此时可用密度来取代距离描述相似性，即基于密度的聚类算法。它不是基于各种各样的距离，所以能克服基于距离的算法只能发现“类圆形”的聚类的缺点。其指导思想是：只要一个区域中的点的密度（对象或数据点的数目）大过某个阈值，就把它加到与之相近的聚类中去。该法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而可发现任意形状的簇，并可用来过滤“噪声”数据。常见算法有DBSCAN，DENCLUE 等。[1][2][3]下一页 3.3 基于划分的聚类算法给定一个N个对象的元组或数据库，根据给定要创建的划分的数目k，将数据划分为k个组，每个组表示一个簇类（<=N）时满足如下两点：(1)每个组至少包含一个对象；(2)每个对

数据挖掘考试题精编版

数据挖掘考试题公司内部编号：（GOOD-TMMT-MMUT-UUPTY-UUYY-DTTI-

数据挖掘考试题一．选择题 1. 当不知道数据所带标签时，可以使用哪种技术促使带同类标签的数据与带其他标签的数据相分离( ) A.分类 B.聚类 C.关联分析 D.主成分分析 2. ( )将两个簇的邻近度定义为不同簇的所有点对邻近度的平均值，它是一种凝聚层次聚类技术。 A.MIN(单链) B.MAX(全链) C.组平均 D.Ward方法 3.数据挖掘的经典案例“啤酒与尿布试验”最主要是应用了( )数据挖掘方法。 A 分类 B 预测 C关联规则分析 D聚类 4.关于K均值和DBSCAN的比较，以下说法不正确的是( ) A.K均值丢弃被它识别为噪声的对象，而DBSCAN一般聚类所有对象。 B.K均值使用簇的基于原型的概念，DBSCAN使用基于密度的概念。 C.K均值很难处理非球形的簇和不同大小的簇，DBSCAN可以处理不同大小和不同形状的簇 D.K均值可以发现不是明显分离的簇，即便簇有重叠也可以发现，但是DBSCAN 会合并有重叠的簇 5.下列关于Ward’s Method说法错误的是：( ) A.对噪声点和离群点敏感度比较小 B.擅长处理球状的簇

C.对于Ward方法，两个簇的邻近度定义为两个簇合并时导致的平方误差 D.当两个点之间的邻近度取它们之间距离的平方时，Ward方法与组平均非常相似 6.下列关于层次聚类存在的问题说法正确的是：( ) A.具有全局优化目标函数 B.Group Average擅长处理球状的簇 C.可以处理不同大小簇的能力 D.Max对噪声点和离群点很敏感 7.下列关于凝聚层次聚类的说法中，说法错误的事：( ) A.一旦两个簇合并，该操作就不能撤销 B.算法的终止条件是仅剩下一个簇 C.空间复杂度为()2m O D.具有全局优化目标函数 8.规则{牛奶，尿布}→{啤酒}的支持度和置信度分别为：( ) 9.下列( )是属于分裂层次聚类的方法。 A.Min B.Max C.Group Average D.MST 10.对下图数据进行凝聚聚类操作，簇间相似度使用MAX计算，第二步是哪两个簇合并：( ) A.在{3}和{l,2}合并 B.{3}和{4,5}合并 C.{2,3}和{4,5}合并

数据挖掘分类算法介绍

数据挖掘分类算法介绍 ----------------------------------------------------------------------------------------------------------------------------- 分类是用于识别什么样的事务属于哪一类的方法，可用于分类的算法有决策树、bayes分类、神经网络、支持向量机等等。决策树例1 一个自行车厂商想要通过广告宣传来吸引顾客。他们从各地的超市获得超市会员的信息，计划将广告册和礼品投递给这些会员。但是投递广告册是需要成本的，不可能投递给所有的超市会员。而这些会员中有的人会响应广告宣传，有的人就算得到广告册不会购买。所以最好是将广告投递给那些对广告册感兴趣从而购买自行车的会员。分类模型的作用就是识别出什么样的会员可能购买自行车。自行车厂商首先从所有会员中抽取了1000个会员，向这些会员投递广告册，然后记录这些收到广告册的会员是否购买了自行车。数据如下：

在分类模型中，每个会员作为一个事例，居民的婚姻状况、性别、年龄等特征作为输入列，所需预测的分类是客户是否购买了自行车。使用1000个会员事例训练模型后得到的决策树分类如下：

※图中矩形表示一个拆分节点，矩形中文字是拆分条件。 ※矩形颜色深浅代表此节点包含事例的数量，颜色越深包含的事例越多，如全部节点包含所有的1000个事例，颜色最深。经过第一次基于年龄的拆分后，年龄大于67岁的包含36个事例，年龄小于32岁的133个事例，年龄在39和67岁之间的602个事例，年龄32和39岁之间的229个事例。所以第一次拆分后，年龄在39和67岁的节点颜色最深，年龄大于67岁的节点颜色最浅。 ※节点中的条包含两种颜色，红色和蓝色，分别表示此节点中的事例购买和不购买自行车的比例。如节点“年龄>=67”节点中，包含36个事例，其中28个没有购买自行车，8个购买了自行车，所以蓝色的条比红色的要长。表示年龄大于67的会员有74.62%的概率不购买自行车，有23.01%的概率购买自行车。在图中，可以找出几个有用的节点： 1. 年龄小于32岁，居住在太平洋地区的会员有7 2.75%的概率购买自行车； 2. 年龄在32和39岁之间的会员有68.42%的概率购买自行车； 3. 年龄在39和67岁之间，上班距离不大于10公里，只有1辆汽车的会员有66.08%的概率购买自行车；

机器学习聚类算法实现

《人工智能与机器学习》实验报告年级__ xxxx班____________ 专业___________xxxxx____ _____ 学号____________6315070301XX___________ 姓名_____________gllh________________ 日期___________2018-5-12 __

实验五聚类算法实现一、实验目的 1、了解常用聚类算法及其优缺点 2、掌握k-means聚类算法对数据进行聚类分析的基本原理和划分方法 3、利用k-means聚类算法对已知数据集进行聚类分析实验类型：验证性计划课间：4学时二、实验内容 1、利用python的sklearn库函数对给定的数据集进行聚类分析 2、分析k-means算法的实现流程 3、根据算法描述编程实现，调试运行 4、对所给数据集进行验证，得到分析结果三、实验步骤 1、k-means算法原理 2、k-means算法流程 3、k-means算法实现 4、对已知数据集进行分析四、实验结果分析 1.利用python的sklearn库函数对给定的数据集进行聚类分析：其中数据集选取iris鸢尾花数据集 import numpy as np from sklearn.datasets import load_iris iris = load_iris() def dist(x,y):

return sum(x*y)/(sum(x**2)*sum(y**2))**0.5 def K_means(data=iris.data,k=3,ping=0,maxiter=100): n, m = data.shape centers = data[:k,:] while ping < maxiter: dis = np.zeros([n,k+1]) for i in range(n): for j in range(k): dis[i,j] = dist(data[i,:],centers[j,:]) dis[i,k] = dis[i,:k].argmax() centers_new = np.zeros([k,m]) for i in range(k): index = dis[:,k]==i centers_new[i,:] = np.mean(data[index,:],axis=0) if np.all(centers==centers_new): break centers = centers_new ping += 1 return dis if __name__ == '__main__': res = K_means() print(res) （1）、首先求出样本之间的余弦相似度： sum(x*y)/(sum(x**2)*sum(y**2))**0.5 （2）、设置k类别数为3，最大迭代次数为100 K_means(data=iris.data,k=3,ping=0,maxiter=100):

数据挖掘聚类算法课程设计报告范本

数据挖掘聚类算法课程设计报告

2.1数据清理所给数据集中包含一些对聚类过程无用的冗余数据。数据集中全部数据的组织结构是：先给出某一科属的植物及其所有分布地区，然后给出该科属下的具体植物及其分布地区。例如：abelmoschus,ct,dc,fl,hi,il,ky,la,md,mi,ms,nc,sc,va,pr,vi abelmoschus esculentus,ct,dc,fl,il,ky,la,md,mi,ms,nc,sc,va,pr,vi abelmoschus moschatus,hi,pr 上述数据中第行给出了所有属于abelmoschus这一科属的植物的分布地区，接下来的两行分别列出了属于abelmoschus 科属的两种具体植物及其分布地区。从中能够看出后两行给出的所有地区的并集正是第一行给出的地区集合。在聚类过程中第行数据是无用的，因此要对其进行清理。 2.2数据变换本实验是依据植物的分布区域进行聚类，所给数据集中的分布区域是字符串形式，不适合进行聚类，因此将其变换成适合聚类的数值形式。具体思想如下：数据集中总共包含68个区域，每一种植物的分布区域是这68个区域中的一部分。本实验中将68个区域看成是数据对象的68个属性，这68个属性是二元类型的变量，其值只能去0或者1。步骤如下： 1.把68个区域按一定顺序存放在字符串数组(记为str)中(顺序能够自己定，确定后不能改变)。

K 均值聚类算法(原理加程序代码)

K-均值聚类算法 1.初始化：选择c 个代表点,...,,321c p p p p 2.建立c 个空间聚类表：C K K K ...,21 3.按照最小距离法则逐个对样本X 进行分类： ),(),,(min arg J i i K x add p x j ?= 4.计算J 及用各聚类列表计算聚类均值，并用来作为各聚类新的代表点（更新代表点） 5.若J 不变或代表点未发生变化，则停止。否则转2. 6.),(1∑∑=∈=c i K x i i p x J δ 具体代码如下： clear all clc x=[0 1 0 1 2 1 2 3 6 7 8 6 7 8 9 7 8 9 8 9;0 0 1 1 1 2 2 2 6 6 6 7 7 7 7 8 8 8 9 9]; figure(1) plot(x(1,:),x(2,:),'r*') %%第一步选取聚类中心，即令K=2 Z1=[x(1,1);x(2,1)]; Z2=[x(1,2);x(2,2)]; R1=[]; R2=[]; t=1; K=1;%记录迭代的次数 dif1=inf; dif2=inf; %%第二步计算各点与聚类中心的距离 while (dif1>eps&dif2>eps) for i=1:20 dist1=sqrt((x(1,i)-Z1(1)).^2+(x(2,i)-Z1(2)).^2); dist2=sqrt((x(1,i)-Z2(1)).^2+(x(2,i)-Z2(2)).^2); temp=[x(1,i),x(2,i)]'; if dist1

数据挖掘主要算法

朴素贝叶斯：有以下几个地方需要注意： 1. 如果给出的特征向量长度可能不同，这是需要归一化为通长度的向量（这里以文本分类为例），比如说是句子单词的话，则长度为整个词汇量的长度，对应位置是该单词出现的次数。 2. 计算公式如下：其中一项条件概率可以通过朴素贝叶斯条件独立展开。要注意一点就是的计算方法，而由朴素贝叶斯的前提假设可知， = ，因此一般有两种，一种是在类别为ci的那些样本集中，找到wj出现次数的总和，然后除以该样本的总和；第二种方法是类别为ci的那些样本集中，找到wj出现次数的总和，然后除以该样本中所有特征出现次数的总和。 3. 如果中的某一项为0，则其联合概率的乘积也可能为0，即2中公式的分子为0，为了避免这种现象出现，一般情况下会将这一项初始化为1，当然为了保证概率相等，分母应对应初始化为2（这里因为是2类，所以加2，如果是k类就需要加k，术语上叫做laplace 光滑, 分母加k的原因是使之满足全概率公式）。朴素贝叶斯的优点：对小规模的数据表现很好，适合多分类任务，适合增量式训练。缺点：对输入数据的表达形式很敏感。决策树：决策树中很重要的一点就是选择一个属性进行分枝，因此要注意一下信息增益的计算公式，并深入理解它。信息熵的计算公式如下:

其中的n代表有n个分类类别（比如假设是2类问题，那么n=2）。分别计算这2类样本在总样本中出现的概率p1和p2，这样就可以计算出未选中属性分枝前的信息熵。现在选中一个属性xi用来进行分枝，此时分枝规则是：如果xi=vx的话，将样本分到树的一个分支；如果不相等则进入另一个分支。很显然，分支中的样本很有可能包括2个类别，分别计算这2个分支的熵H1和H2,计算出分枝后的总信息熵H’=p1*H1+p2*H2.，则此时的信息增益ΔH=H-H’。以信息增益为原则，把所有的属性都测试一边，选择一个使增益最大的属性作为本次分枝属性。决策树的优点：计算量简单，可解释性强，比较适合处理有缺失属性值的样本，能够处理不相关的特征；缺点：容易过拟合（后续出现了随机森林，减小了过拟合现象）； Logistic回归： Logistic是用来分类的，是一种线性分类器，需要注意的地方有： 1. logistic函数表达式为：其导数形式为： 2. logsitc回归方法主要是用最大似然估计来学习的，所以单个样本的后验概率为：到整个样本的后验概率：

各种聚类算法的比较

各种聚类算法的比较聚类的目标是使同一类对象的相似度尽可能地小；不同类对象之间的相似度尽可能地大。目前聚类的方法很多，根据基本思想的不同，大致可以将聚类算法分为五大类：层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法和用于高维度的聚类算法。摘自数据挖掘中的聚类分析研究综述这篇论文。 1、层次聚类算法 1.1聚合聚类 1.1.1相似度依据距离不同：Single-Link:最近距离、Complete-Link：最远距离、Average-Link：平均距离 1.1.2最具代表性算法 1）CURE算法特点：固定数目有代表性的点共同代表类优点：识别形状复杂，大小不一的聚类，过滤孤立点 2）ROCK算法特点：对CURE算法的改进优点：同上，并适用于类别属性的数据 3）CHAMELEON算法特点：利用了动态建模技术 1.2分解聚类 1.3优缺点优点：适用于任意形状和任意属性的数据集；灵活控制不同层次的聚类粒度，强聚类能力缺点：大大延长了算法的执行时间，不能回溯处理 2、分割聚类算法 2.1基于密度的聚类 2.1.1特点将密度足够大的相邻区域连接，能有效处理异常数据，主要用于对空间数据的聚类

1）DBSCAN：不断生长足够高密度的区域 2）DENCLUE：根据数据点在属性空间中的密度进行聚类，密度和网格与处理的结合 3）OPTICS、DBCLASD、CURD：均针对数据在空间中呈现的不同密度分不对DBSCAN作了改进 2.2基于网格的聚类 2.2.1特点利用属性空间的多维网格数据结构，将空间划分为有限数目的单元以构成网格结构； 1）优点：处理时间与数据对象的数目无关，与数据的输入顺序无关，可以处理任意类型的数据 2）缺点：处理时间与每维空间所划分的单元数相关，一定程度上降低了聚类的质量和准确性 2.2.2典型算法 1）STING：基于网格多分辨率，将空间划分为方形单元，对应不同分辨率2）STING+：改进STING，用于处理动态进化的空间数据 3）ＣＬＩＱＵＥ：结合网格和密度聚类的思想，能处理大规模高维度数据4）WaveCluster：以信号处理思想为基础 2.3基于图论的聚类 2.3.1特点转换为组合优化问题，并利用图论和相关启发式算法来解决，构造数据集的最小生成数，再逐步删除最长边 1）优点：不需要进行相似度的计算 2.3.2两个主要的应用形式 1）基于超图的划分 2）基于光谱的图划分 2.4基于平方误差的迭代重分配聚类 2.4.1思想逐步对聚类结果进行优化、不断将目标数据集向各个聚类中心进行重新分配以获最优解