明 β+ 1对于所有测试数据集而言是小的 ,它小于 2。 原始的质心点算法采用互异矩阵代替了优先队列 ,并且还没
有保留最近邻居 。它的时间复杂度为 O (N3 ) , 空间复杂度为 O (N2 ) ,如果采用两阶段算法 ,那么时间复杂度就会变为 : O ( (N k′) 3 (β+ 1) 3 ( n / p + |δ| ) 2 ) + O ( k′3 ) , 空间复杂度为 O ( p3 (N / p) + |δ|2 )或 O ( k′2 )或者两者中较大的 。注意 , 在这个例子 中 ,受影响单元的平均数不是因子 ,这是因为全部的复杂度是由 于需要通过互异矩阵进行搜索需要二次的时间量 。经过简化 (没 有考虑 |δ |与 k′)时间复杂度为 O (N 3 p3 (N2 / p2 ) ) , 即 O (N 3 / p) ,获取因子为 p。空间复杂度为 O ( (N2 / p) ) (获取因子为 p) 。
关键词 聚类 层次聚类 谱系图 簇 POP
O N IM PRO VEM ENT AND ANALY S IS O F H IERARCH ICAL CL USTER ING AL GO R ITHM
Guo X iaojuan1 L iu X iaoxia1 L i Xiao ling2
2. 2 改进算法的实现及时空复杂度
这个算法如下所示 。通过对距离图中转折点的最近距离对 设置 δ,可以在第一阶段合并大量的簇 ,在第二阶段利用传统 HAC算法合并剩余的小量的簇 。
Input: Data (N ,M ) , p , δ
Output: Dendrogram / 3 第一阶段 3 / 将数据分配到 p个重叠单元中 ,为每个单元创建优先队列 P
2 改进算法及其分析过程
经验表明 ,除了谱系图的一些高层 ,所有低层聚类的簇既小 而且与其他簇也非常接近 。我们可称此特性为 90 - 10规则 ,它 难以被很小距离分开的小簇合并 。基于 90 - 10规则 ,我们提出 了快速 HAC算法 ,它能有效地减少已存在 HAC算法的时空复 杂性 。在本文中 , 90 - 10规则用来改进已存在簇方法的有效性 与正确性 。90 - 10规则就是能有效地丢弃不需要的层 ,聚集潜 在的层 。所对每个单元获取它的最近距离对 ,确定全部的最接近点对 (C1 , C2 ) If dist ( C1 , C2 ) < δ 合并 C1 和 C2 同时更新相应的 P队列 ; 更新所有受影响单元的 P队列 W hile ( dist( C1 , C2 ) > δ) / 3 第二阶段 3 / 利用传统聚类算法合并第一阶段剩余的簇 Return 谱系图
1 传统的层次凝聚算法 [2 ]及其局限性
空复杂性 ,例如 ,对于质心点算法 (优先队列法 ) ,其时间复杂性 为 : O (N 2 logN ) ,虽然可以将 HAC应用于大量数据中 ,一些技术 被用到诸如 B IRCH[3 ]和 CURE[4 ] , 但 它 们 都不 能 加 快 传 统 的 HAC算法 ,在使用最近点且保证正确性前提条件下减少计算 量 。2)用谱系图获得簇的有效性是有限的 。簇的有效性主要 用来决定在大型数据量中最优簇的数目 。并且 ,很多有效性方 法对谱系图的低层显示出转移模式 ,这就会导致评估不出不精 确的最优簇数 。
1 ( N orthw est U niversity , X iπan 710127, S haanxi, China) 2 ( China U n iversity of Geosciences, W uhan 430074, Hubei, China)
Abstract A p rom inent and useful class of algorithm is hierarchical agglomerative clustering (HAC) which iteratively agglomerates the clo2 sest pare until all data points belong to one cluster. However, HAC methods have several drawbacks, such as high time and memory comp lex2 ities when clustering, insufficient and inaccurate cluster validation, etc. Emp irical study show s that most HAC algorithm s follow a trend where, excep t for a number of top levels of the dendrogram , all lower level agglomerate clusters are very small in size and close in p roxim ity to other clusters. M ethods are p roposed to reduce the time and memory comp lexities significantly and to make validation very efficient and ac2 curate. Analysis and experiments all p rove the effectiveness of the p roposed method.
244
计算机应用与软件
2008年
2. 1 算法的基本思想
我们提出基于部分重叠划分 POP ( Partially Overlapp ing Par2 titioning)的改进 HAC算法 。下面来具体分析一下基于 POP的 一种新算法 ———两阶段算法 。两阶段算法 : 在 POP 基础上对 HAC算法提出一个新的两阶段算法 。第一个阶段 ,数据被分配 到 P个重叠的单元 ,这个重叠的区域称作 δ区域 ,其中 δ是分离 的距离 。对于质心点算法来讲 ,每个簇都用单一的代表点表示 , 如果一个簇的代表点落在 δ区域 ,那么每一个受影响的单元都 可捕获它并保存 ,否则 ,只有一个单元可以获取到它 。基于 POP 的思想 ,在每一次迭代过程中 ,从已发现的全部最近点对中为每 个单元找出最接近的点对 。如果所有这些最近点对的距离小于 δ,那么合并这些点对 ,并且更新被包含单元中的优先队列 。如 果最接近点对或合并的簇在 δ区内 ,那么所有受影响的单元都 会更新其优先队列 。当最远点对距离超出 δ时 ,每一阶段终止 。 第二个阶段利用传统的聚类算法合并第一阶段余下的簇 。这样 就以得到一个谱系图 。
Keywords Clustering HAC Dendrogram Cluster POP
0 引 言
随着数据挖掘研究领域技术的发展 ,作为数据挖掘主要方 法之一 的 聚 类 算 法 , 也 越 来 越 受 到 人 们 的 关 注 。数 据 挖 掘 (D ata M ining)又称知识发现 ( KDD ) ,其实是知识发现过程的 一个步骤. 它是从数据库 、数据仓库或其他信息库中便捷地抽 取出以前未知的 、隐含的 、有用的信息 ,所挖掘出来的知识可 应用于信息管理 、决策支持 、过程控制和其它许多应用 。所谓 聚类 ( Clustering) ,就是把大量的 d维数据样本 ( n个 )聚集成 k 个类 ( k, n) ,使同一类内样本的相似性最大 ,而不同类中样本 的相似性最小 。聚类分析作为数据挖掘中的一种分析方法 , 它可以作为一个单独的工具以发现数据库中数据分布的一些 深入的信息 。并且概括出每一类的特点 ,或者把注意力放在 某一个特定的类上以作进一步的分析 ;聚类分析也可以作为 数据挖掘算法中其他分析算法的一个预处理步骤 。目前已经 提出很多的聚类算法 [1 ] 。
2. 3 改进算法的分析
精确性分析 关于第一阶段使用 POP能够确保任意小于 δ 的距离对都能保留在至少一个单元中 ,第二阶段使用传统聚类 算法 ,两阶段算法能够保证正确的谱系图 。
复杂性分析 为简化这个分析 ,先假设每个单元有相同的 单元大小 ,相同的 δ域大小 。 | δ |主要是用来表明任意特殊单 元 δ域中的簇数 。最初由 Day和 Edelshrunner[5 ]提出的优先队列 算法的时间复杂度为 : O ( n2 logN ) , O (N2 ) ,相反 ,所提出的两阶段算 法 ,它的时间复杂度为 O ( (N - k′) 3 (β + 1) 3 ( n / p + |δ| ) )。 log ( n / p + |δ| )要远远大于 P, 并且 β是在每次迭代中受影响单元 的平均数 。空间复杂度是 : O ( p3 ( n / p + |δ| ) 2 )或者 O ( k′2 )或 是两者中较大的 。如果 δ设置为距离图中转折点的最近对距 离 ,那么 |δ|和 k′都是非常小的 ,因此 ,如果没有考虑 |δ|与 k′,时 间复杂度就变为 : O (N 3 (β+ 1) 3 (N / p) log (N / p) ) ,即 O ( (β+ 1) 3 (N 2 / p) log (N / p) ) (获取因子为 log(N /p) N 3 ( P /β + 1) ) , 空 间复杂度为 : O ( p3 (N 2 3 p2 ) ) ,即 O ( (N 2 / p) ) (获取因子为 p) 。 容器中所包含受影响单元的平均数为 β + 1,这个值主要依赖于 数据是如何分配的 :在最坏情况下 ,对于 M 维数据而言 , 每次聚 类受影响单元的最大可能数为 2M , 在最好情况下 , 每次聚类受 影响的仅仅是容器本身中的单元 , 那么这个值仅为 1。经验表
第 25卷第 6期 2008年 6月
计算机应用与软件 Computer App lications and Software
Vol125 No. 6 Jun. 2008