聚类初始中心点选取研究

第３３卷第４期　２０１０年ｌ２月　南京师大学报（自然科学版）　ＪＯＵＲＮＡＬ　ＯＦ　ＮＡＮＪＩＮＧ　ＮＯＲＭＡＬ　ＵＮＩＶＥＲＳＩＴＹ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　Ｖｏｌ＿３３　Ｎｏ．４　Ｄｅｃ，２０１０　聚类初始中心点选取研究　杨天霞，王治和，王　华，王凌云　（西北师范大学数学与信息科学学院，甘肃兰州７３００７０）　［摘要］　研究了利用已发现的频繁序列模式对序列数据库进行再聚类再发现的问题，针对已有的Ｋ一均值聚类　算法随机选取初始中心点而导致聚类结果不稳定性的缺点，提出了一种基于Ｈｕｆｆｍａｎ思想的初始中心点选取算　法——Ｋ—ＳＰＡＭ（Ｋ—ｍｅａｎｓ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｓｅｑｕｅｎｃｅ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ　ｂａｓｅｄ　Ｏｆｆ　ｔｈｅ　Ｈｕｆｆｍａｎ　Ｍｅｔｈｏｄ）算法．该算法能够在一　定程度上减少陷入局部最优的可能，而且对序列间相似度的计算采用一种高效的“与”、“或”运算，可极大提高　算法的执行效率．　［关键词］　Ｋ一均值，序列模式，Ｈｕｆｆｍａｎ树，聚类，初始中心　［中图分类号］ＴＰ３９１　［文献标识码］Ａ　［文章编号］１００１－４６１６（２０１０）０４－０１６１－０５　Ｒｅｓｅａｒｃｈ　ｏｆ　Ｃｌｕｓｔｅｒｉｎｇ　Ｉｎｉｔｉａｌ　Ｃｅｎｔｅｒ　Ｓｅｌｅｃｔｉｏｎ　Ｙａｎｇ　Ｔｉａｎｘｉａ，Ｗａｎｇ　Ｚｈｉｈｅ，Ｗａｎｇ　Ｈｕａ，Ｗａｎｇ　Ｌｉｎｇｙｕｎ　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ，Ｎｏｒｔｈｗｅｓｔ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｌａｎｚｈｏｕ　７３００７０，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｐａｐｅｒ　ｓｔｕｄｉｅｄ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｒｅｃｌｕｓｔｅｒｉｎｇ　ａｎｄ　ｒｅｄｉｓｃｏｖｅｒｉｎｇ　ｉｎ　ｔｈｅ　ｓｅｑｕｅｎｃｅ　ｄａｔａｂａｓｅ　ｏｎ　ｔｈｅ　ｂａｓｉｓ　ｏｆ　ｔｈｅ　ｒｅｓｕｌｔｓ　ｏｆ　ｓｅｑｕｅｎｔｉａｌ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ．Ａｉｍｉｎｇ　ａｔ　ｔｈｉｓ　ｓｈｏｒｔｃｏｍｉｎｇ　ｔｈａｔ　ｉｔ　ｃｏｕｌｄ　ｌｅａｄ　ｔｏ　ｔｈｅ　ｉｎｓｔａｂｉｌｉｔｙ　ｏｆ　ｃｌｕｓｔｅｒｉｎｇ　ｒｅｓｕｌｔｓ　ｔｏ　ｓｅｌｅｃｔ　ｒａｎｄｏｍｌｙ　ｔｈｅ　ｉｎｉｔｉｌ　ｆｏｃａｌａ　ｐｏｉｎｔｓ　ｉｎ　ｔｈｅ　ｅｘｉｓｔｉｎｇ　Ｋ—ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ，ａｎ　ｉｎｉｔｉａｌ　ｃｅｎｔｅｒ　ｓｅｌｅｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｎａｍｅｄ　Ｋ—ＳＰＡＭ（Ｋ—ｍｅａｎｓ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｓｅｑｕｅｎｃｅ　ｐａｔｔｅｎ　ｒｍｉｎｉｎｇ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　Ｈｕｆｉｎａｎ　Ｍｅｔｆｈｏｄ）ａｌｇｏｒｉｔｈｍ　ｗａｓ　ｐｒｏｐｏｓｅｄ．　Ｉｔ　ｗａｓ　ｂａｓｅｄ　ｏｎ　Ｈｕｆｆｍａｎ　ｉｄｅａ．Ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｃｏｕｌｄ　ｒｅｄｕｃｅ　ｐｒｏｂａｂｉｌｉｔｙ　ｏｆ　ｌｏｃａｌ　ｏｐｔｉｍｕｍ　ｔｏ　ａ　ｃｅｒｔａｉｎ　ｅｘｔｅｎｔ．Ｍｏｒｅｏｖｅｒ，ａ　ｈｉｇｈｌｙ　ｅｆｉｃｉｅｎｔ“ａｎｄ”ａｎｄ“ｏｒ”ｏｐｅｒｆａｔｏｒｓ　ｗｅｒｅ　ａｄｏｐｔｅｄ　ｔｏ　ｃａｌｃｕｌａｔｅ　ｓｉｍｉｌａｒｉｔｙ　ｂｅｔｗｅｅｎ　ｐａｉｒｓ　ｏｆ　ｓｅｑｕｅｎｃｅｓ．Ｔｏ　ｄｏ　ＳＯ　ｃｏｕｌｄ　ｇｒｅａｔｌｙ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｅｘｅｃｕｔｉｏｎ　ｅｆｉｃｉｆｅｎｃｙ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ．　Ｋｅｙ　ｗｏｒｄｓ：Ｋ—ｍｅａｎｓ，ｓｅｑｕｅｎｔｉｌ　ｐａｔａｔｅｒｎｓ，Ｈｕｆｆｍａｎ　ｔｒｅｅ，ｃｌｕｓｔｅｒｉｎｇ，ｉｎｉｔｉａｌ　ｃｅｎｔｅｒ　自１９９５年Ａｇｒａｗａｌ和Ｓｒｉｋａｎｔ两位学者提出序列模式的概念以来…，有关序列模式的挖掘得到了广泛的　关注，国内外很多学者对其展开了研究，使得序列模式的挖掘效率得到了极大的提高．序列模式挖掘的主要　任务是找出随着时间或是特定顺序经常发生的模式，关于其挖掘算法已经有很多研究．序列模式发现作为重　要的ＫＤＤ分支，在交易数据分析、疾病分析、Ｗｅｂ日志分析等领域已经展开了较为广泛的研究和应用．　ＭａｃＱｕｅｅｎ　Ｊ　Ｂ在１９６７年提出了Ｋ一均值聚类算法　，它是到目前为止应用于科学和工业领域中诸多　算法中一种极有影响力的技术．算法首先随机选取ｋ个点作为初始聚类中心，然后计算各个数据对象到各　聚类中心的距离，把数据对象归到离它最近的那个聚类中心所在的类；再对调整后的新类计算新的聚类中　心，如果相邻两次的聚类中心没有明显变化，聚类准则函数收敛，说明数据对象调整结束．该算法的一个特　点是在每次迭代中都要考察每个样本的分类是否正确，若不正确，就要调整．在全部数据调整完后，再修改　聚类中心，进人下一次迭代．如果在一次迭代算法中，所有的数据对象被正确分类，则不会有调整，聚类中　心也不会有任何变化，这标志着准则函数已经收敛，至此算法结束．　然而后个初始聚类中心点的选取对聚类结果具有较大的影响，因为在该算法中是随机地任意选取ｋ　个点作为初始聚类中心，初始地代表一个簇．ｋ个中心点选取的不同将直接影响算法的迭代次数和执行效　率．本文提出了一种基于Ｈｕｆｆｍａｎ树构造思想的初始中心点选取方法，该方法解决了随机选取初始中心点　收稿日期：２０１０－０６　１０．　基金项目：西北师范大学２００６—２０１０年度重点学科基金（２００７Ｃ０４）．　通讯联系人：杨天霞，硕士研究生，研究方向：数据挖掘．Ｅ—ｍａｉｌ：ｙｔｘｌｕｃｋ＠１６３．ｃｏｒｎ　一１６１—　南京师大学报（自然科学版）　第３３卷第４期（２０１０年）　容易陷入局部最优，以及Ｋ一均值聚类算法对初始聚类中心有严重的依赖性，随机选择初始中心点容易导　致聚类结果不稳定的问题．同时，本文对序列问相似度的计算采用相似性度量Ｊａｃｃａｒｄ系数定义序列间的　相似性，使得算法执行效率大大提高．　１基本知识　定义１　序列（Ｓｅｑｕｅｎｃｅ）：是项集的有序表，记作＜Ｓ　，Ｓ：，…，Ｓ　＞，其中Ｓ　（１≤ｋ≤ｎ）是项集．　定义２¨　序列包含（Ｓｅｑｕｅｎｃｅ　Ｃｏｎｔａｉｎ）：给定两个序列Ａ＝｛０，，０　，…，口　｝和Ｂ：｛ｂ　，ｂ　，…，ｂ　｝，　如果存在一组整数ｌ≤ｉ　＜ｉ：＜…＜ｉ　≤凡，使得０。　ｂ　０：　ｂ　…，。　日包含．不包含在任何其它序列中的序列称为最大序（ｍａｘｉｍａｌ　ｓｅｑｕｅｎｃｅ）．　ｂ…则称序列Ａ被序列　定义３＿１　序列Ｓ的支持数是包含５的客户序列数目．如果序列的支持数大于等于用户给定的最小支　持度阈值（ｍｉｎｓｕｐ），则称Ｓ是一个频繁序列．　定义４　序列Ｓ。和Ｓ　之问的相似度定义　ｆ（Ｓ…Ｓ）＝　等非常相似．　，　（１）　其中，Ｓ。．Ｐ表示序列５。所支持的序列模式的集合，Ｓ　．Ｐ表示序列ｓ　所支持的序列模式的集合．显然，０≤　５　，Ｓ：）≤１．当　５　，５　）＝０时，表示序列Ｓ　和序列Ｓ　支持完全不同的序列模式，可以认为Ｓ。和ｓ　之　间没有任何的相似性；当　ｓ。，Ｓ　）＝１时，表示序列Ｓ　和序列Ｓ　支持完全相同的序列模式，可认为Ｓ　和ｓ　２基于Ｈｕｆｆｍａｎ树构造思想的序列聚类挖掘算法　本文提出的基于Ｈｕｆｆｍａｎ树构造思想的Ｋ．均值序列模式聚类挖掘算法是在已挖掘出的频繁序列模　式的基础上对序列数据库中的序列再次聚类．由于序列数据的特殊性以及经典的Ｋ．均值聚类算法存在的　Ｏ　一０　些不足，本文对Ｋ一均值算法如何选取　个初始中心点做了改进，对序列间相似性的计算采用了位图中　的“与”和“或”运算，大大提高了算法的执行效率．　２．１预处理阶段　对原始序列数据库用ＳＰＡＭ算法　挖掘出全部频繁序列模　式，再根据序列一模式的支持关系构造如表１所示的序列一模　式支持关系表．其中，Ｓ。，Ｓ　，…，Ｓ　表示数据序列，Ｐ　，Ｐ　，…，Ｐ　表示序列模式，若Ｓ　支持（包含）Ｐ　，则对应的属性值为１，否则　为０．每个数据序列可由一个ｍ维向量来描述它对序列模式的　支持信息．　２．２相异度　Ｓｌ　Ｓ２　－●●　表１序列一模式支持关系　Ｔａｂｌｅ　１　Ｓｅｑｕｅｎｃｅ・ｐａｔｔｅｒｎ　ｓｕｐｐｏｒｔ　ｒｅｌａｔｉｏｎｓｈｉｐ　０　１　Ｓ　Ｏ　使用Ｈｕｆｆｍａｎ思想来选取ｋ个初始中心是基于对象问相似性的，本文采用序列间的相似度函数　Ｓ，，　ｓ　）＝　，用相异度矩阵来存放对象之间的相似性，相异度矩阵是一个对象一对象结构．　由序列模式挖掘结果得到序列一模式支持关系表后，要计算序列Ｊｓ　和Ｓ　之间的相似度，此时只需将．ｓ。　和５，的ｍ个属性分别做传统的“与”、“或”操作即可，可极大提高算法的运行效率．　对应的相异度函数和相异度矩阵定义为：　ｄ（Ｓ　，Ｓ　）＝１一＿厂（５　，ｓ２），　和　０　ａ（２，１）０　０　ｄ（３，１）ｄ（３，２）ｄ（ｎ，１）ｄ（ｎ，２）ｄ（ｎ，３）　一ｌ６２—　杨天霞，等：聚类初始中心点选取研究　其中ｄ（ｉ　）表示对象ｉ和对象Ｊ．之间的差异，通常ｄ（　，　）为一个非负数，且有ｄ（ｉ，　）＝ｄ（ｊ，ｉ）以及ｄ（ｉ，ｉ）　＝０．当对象ｉ和对象．　彼此非常“接近”或非常相似时，该数据接近０；相反该数值越大，就表示对象ｉ和对　象　越不相似．　２．２　初始中心点的选取　２．２．１　Ｈｕｆｆｍａｎ算法思想　步骤１　根据给定的／２个权值｛Ｗ。，　，…，　｝构造／２棵二叉树的集合Ｆ＝｛　，　，…，　｝，其中每颗　二叉树　中只有一个带权为　的根结点，其左右子树均空；　步骤２　在Ｆ中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树　的根节点的权值为其左右子树上根结点的权值之和；　步骤３　在Ｆ中删除这两棵树，同时将新得到的二叉树加入Ｆ中；　步骤４　重复步骤２和步骤３，直到　中只含有一棵树为止，这棵树便是Ｈｕｆｆｍａｎ树．　２．２．２　Ｋ．ＳＰＡＭ算法初始中心点选取　由于序列数据本身的特殊性，在对序列数据库使用Ｋ一均值聚类算法进行再聚类时，对初始中心点的　选取上不能直接采用Ｈｕｆｆｍａｎ树的构造思想，需要对Ｈｕｆｆｍａｎ思想做一些改动．　①在本文的算法中，伽　指的是前一阶段所构造的序列一模式表中描述．ｓ　对应的ｍ维向量．根据　Ｈｕｆｆｍａｎ思想，基于数据相异度，将数据样本构造成一棵树．根据算法的实际需要，在构造树的时候作了改　变：在构造树时，不用左右子树根结点权值之和作为新的二叉树根结点权值，而是用左右两个根结点Ｗ—ｌｅｆｔ　和Ｗ—ｒｉｇｈｔ的按位与的结果Ｗ—ｒｅｓｕｌｔ作为新二叉树的根结点权值，将Ｗ—ｌｅｆｔ和Ｗ—ｒｉｇｈｔ两个结点删除即可．由　于Ｗ—ｒｅｓｕｌｔ代表了Ｗ—ｌｅｆｔ和Ｗ—ｒｉｇｈｔ共同支持的序列模式，能够表示它们的相似性，所以用Ｗ—ｒｅｓｕｌｔ来表示新　树的根结点很有意义．　②将构造出来的Ｈｕｆｆｍａｎ树，按构造结点的逆序找到ｋ一１个结点，根据图论知识可知，去掉这ｋ一１　个结点可将该树分为　个子树，这ｋ个子树的根结点即为初始的ｋ个聚类中心点．　２．３　Ｋ．ＳＰＡＭ算法描述　设序列数据库中有ｎ个数据对象（序列数据），对其按ＳＰＡＭ算法进行频繁序列模式挖掘，假设挖掘出　了ｍ个频繁序列模式，那么每个原序列数据对象就是ｍ维，现要对该／２个数据对象进行聚类，聚类数为ｋ．　Ｋ—ＳＰＡＭ算法伪代码描述：　输入：数据预处理后的序列一模式支持关系矩阵Ｍ，以及用户要求的聚类数数目ｋ．　输出：聚类的集合。　Ｓｔｅｐ　１：ｄｏ．　Ｓｔｅｐ　２：对矩阵Ｍ中的ｎ个对象Ｓ　＝｛ｓ　，ｓ　，…，ｓ　｝，选取相异度最小的两点Ｐ，ｑ；ｄ　＝ｍｉｎ｛ｄ　，ｉ，　∈　１，２，…，ｎ｝，计算Ｐ和ｑ按位与的结果作为新点放入Ｓ　．　Ｓｔｅｐ　３：从Ｓ　中删除ｐ和ｇ得到Ｓ　＝｛Ｓ　，５　，…，　｝．　Ｓｔｅｐ　４：计算．ｓ　中序列问的相异度，得到相异度矩阵．　Ｓｔｅｐ　５：ｗｈｉｌｅ　Ｓ　中的对象个数大于１．　Ｓｔｅｐ　６：至此构造出了关于　个对象的一棵树，记为Ｇ　．ｄｅｌｅｔｅ　Ｇ　中逆序构造出来的七一１个点，得到ｋ　个子树，ｋ个子树的根节点Ｃ。，ｃ　，…，Ｃ　即为算法的ｋ个初始中心点．　Ｓｔｅｐ　７：ｄｏ．　Ｓｔｅｐ　８：分别计算／２个数据对象与中心点的距离，并赋给最近的簇．　Ｓｔｅｐ　９：计算ｋ个簇的中心值．　Ｓｔｅｐ　１０：ｗｈｉｌｅ各簇中心值仍发生明显变化．　３　实验分析　实验环境为ＰｅｎｔｉｕｍＩＶ／Ｉｎｔｅｌ　１．７３　ＧＨｚ　ＰＣ，５１２　ＭＢ内存，Ｗｉｎｄｏｗｓ　ＸＰ操作系统和Ｍｉｃｒｏｓｏｆｔ　Ｖｉｓｕａｌ　Ｃ＋＋６．０．实验数据集采用：　（１）ＵＣＩ数据库中的３个数据集Ｉｒｉｓ　Ｐｌａｎｔｓ数据集、Ｗｉｎｅ　ｒｅｃｏｇｎｉｔｉｏｎ数据集和Ｂａｌａｎｃｅ　Ｓｃａｌｅ　Ｗｅｉｇｈｔ＆　一１　６３—　南京师大学报（自然科学版）　第３３卷第４期（２０１０年）　Ｄｉｓｔａｎｃｅ数据集ｌ６　；　（２）使用ＩＢＭ数据生成器产生交易数据库Ｄ１Ｃ５Ｔ３Ｎ０１０５［７　３．　３．１　Ｋ－ＳＰＡＭ算法稳定性实验及结果分析　本节所选的３个数据集类别个数都是３，将Ｋ一均值聚类结果与Ｋ．ＳＰＡＭ算法聚类结果进行对比，以下　是聚类结果的正确率计算公式：　＋　＋　７一　ｍ　！：　３　：　’　其中ｍ是测试的次数，　表示第　次测试中类ｌ的正确率，类似地　表示第　次测试中类２的正确率，同　样　表示第　次测试中类３的正确率．当一次测试时这３个值越大，那么这次测试的平均正确率也就越大．　相反，如果这３个值越小，那么平均正确率也就越小．　在上式的求和计算中对３个类的正确率分别进行　计算，然后求出每次聚类的平均值．限于篇幅，文中只　给出２０次聚类测试后平均正确率对比表（见表２）．　从表２可以明显看出，Ｋ—ＳＰＡＭ算法在聚类结果　表２聚类结果对比　Ｔａｂｌｅ　２　Ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｃｌｕｓｔｅｒｉｎｇ　ｒｅｓｕｌｔｓ　Ｍｅａｎ　Ａｃｃｕｒａｃｙ　Ｒａｔｅ　Ｍｅａｎ　Ａｃｃｕｒａｃｙ　Ｒａｔｅ　ｏｆ　Ｋ一均值　ｏｆ　Ｋ—ＳＰＡＭ　正确性方面要优于Ｋ－均值聚类算法，而正确性的提高　在一定程度也会提高算法的稳定性．Ｋ—ＳＰＡＭ算法在　选取初始中心点时采用Ｈｕｆｆｍａｎ方法，所有每次选取　的中心点都比较稳定，不会出现大的偏差．Ｋ一均值聚类　算法由于采用随机方法选取初始中心点，所以每次聚类初始中心点都有可能不同，还可能会差别很大，从　而导致这种算法聚类结果的正确性会受很大影响，进而影响到算法的稳定性．　３．２　Ｋ—ＳＰＡＭ算法运行效率实验及分析　实验数据集采用ＩＢＭ数据生成器产生交易数据　库Ｄ１Ｃ５Ｔ３Ｎ０１０５，数据库包含５０００条交易记录，１　０２４　表３　ＳＰＡＭ算法挖掘序列模式结果　最小支持度序列模式数０．０５　０．０８　０．１０　０．１２　０．１５　０．２０　４２６　２３５　１４１　９５　５２　３４　Ｔａｂｌｅ　３　ＳＰＡＭ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｍｉｎｉｎｇ　ｓｅｑｕｅｎｔｉａｌ　ｐａｔｔｅｒｎ　ｒｅｓｕｌｔｓ　条数据序列，然后利用现有的经典序列模式挖掘算法　ＳＰＡＭ针对不同的支持度挖掘出频繁序列模式如表３　所示．　实验一：分析聚类数目对算法迭代次数的影响，　以最小支持度０．１０时的挖掘结果作为输入，聚类数　目分别取ｋ＝３、６、９、１２、１５，如图１所示．从实验一可　以明显看出，Ｋ．ＳＰＡＭ算法由于采用了Ｈｕｆｆｍａｎ的思　想选取了初始聚类中心点，所以算法很快收敛于最优　值，迭代次数明显少于Ｋ．均值聚类算法．　文献『３］最先提出了基于已发现序列模式对数据　库中序列进行聚类的ＰＯＰＣ（Ｐａｔｔｅｒｎ—Ｏｒｉｅｎｔｅｄ　Ｐａｒｔｉａｌ　Ｃｌｕｓｔｅｒｉｎｇ）算法，它采用的是一种层次聚类方法．　实验二：分析序列模式数目对算法性能的影响，　固定聚类数目ｋ＝９，以不同最小支持度下的挖掘结果　作为输入，实验结果如图２所示．　实验三：分析聚类数目对算法性能的影响，以最　小支持度０．１０时的挖掘结果作为输入，分别取聚类　数目ｋ＝３、６、９、１２、１５，如图３所示．　一ｌ６４一　杨天霞，等：聚类初始中心点选取研究　最小支持度／％　聚类个数ｋ　图２不同最小支持度下两种算法执行时间比较　图３不同聚类数目下两种算法执行效率比较　Ｆｉｇ．２　Ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｔｈｅ　ｅｘｅｃｕｔｉｏｎ　ｔｉｍｅ　ｏｆ　ｔｗｏ　ａｌｇｏｒｉｔｈｍｓ　Ｆｉｇ．３　Ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｔｈｅ　ｅｆｉｆｃｉｅｎｃｙ　ｏｆ　ｔｗｏ　ａｌｇｏｒｉｔｈｍｓ　ｕｎｄｅｒ　ｕｎｄｅｒ　ｄｉｆｆｅｒｅｎｔ　ｍｉｎｉｍｕｍ　ｓｕｐｐｏｒｔ　ｄｉｆｅｒｅｎｔ　ｃｌｕｓｔｅｒｉｎｇ　ｎｕｍｂｅｒ　从实验二和实验三可看出，本文的Ｋ—ＳＰＡＭ算法的执行效率要明显优于ＰＯＰＣ算法．在实验二中，当　最小支持度很小时，ＰＯＰＣ算法的运行时间明显大于Ｋ．ＳＰＡＭ算法，这是由于最小支持度小，挖掘出的序　列模式数相反会很大，从而导致ＰＯＰＣ算法的初始聚类数目增多，使相应的迭代次数也急剧增加，以及在　每次迭代中相异度矩阵的计算量增大，最终导致执行时间明显高于Ｋ—ＳＰＡＭ算法的执行时间．而Ｋ—ＳＰＡＭ　算法由于是Ｋ一均值算法的改进，继承了它简单易行的优点，其次是采用了Ｈｕｆｆｍａｎ思想能够使算法在执　行过程中很快收敛于最优值，减少迭代次数，再次是算法中对序列间相异度的计算采用了“与”、“或”运　算，极大地提高了算法的执行效率．　４结语　本文重点研究了在已挖掘的频繁序列模式的基础上，再利用划分聚类的Ｋ一均值算法对序列数据进行　聚类研究．文中利用Ｈｕｆｆｍａｎ树的构造思想，对Ｋ一均值算法随机选取初始中心点会导致聚类结果的不稳　定性缺点提出了一种新的解决算法Ｋ．ＳＰＡＭ．Ｋ—ＳＰＡＭ算法实现了对包含相似模式的序列数据进行聚类，　通过对聚类初始中心点的选取采用Ｈｕｆｆｍａｎ思想，减少了Ｋ一均值算法的迭代次数，提高了聚类的稳定性．　并通过实验对Ｋ．ＳＰＡＭ和Ｋ．均值算法的聚类结果进行比较，进一步证实了Ｋ—ＳＰＡＭ算法的优点．　［参考文献］　［１］Ａｇｒａｗａｌ　Ａ，Ｓｒｉｋａｎｔ　Ｒ．Ｍｉｎｉｎｇ　ｓｅｑｕｅｎｔｉａｌ　ｐａｔｔｅｒｎｓ［Ｃ］／／Ｔａｉｐｅｉ：Ｐｒｏｃ　ｏｆｔｈｅ　１１　ｓｔ　Ｉｎｔ　Ｃｏｎｆ　ｏｎ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，１９９５：３—１４．　［２］　Ｋａｕｆｉｎａｎ　Ｌ，Ｒｏｕｅｅｅｕｗ　Ｐ　Ｊ．Ｆｉｎｄｉｎｇ　Ｇｒｏｕｐｓ　ｉｎ　Ｄａｔａ：Ａｎ　Ｉｎｔｒｏｄｕｃｔｉｏｎ　ｔｏ　Ｃｌｕｓｔｅｒ　Ａｎａｌｙｓｉｓ［Ｍ］．Ｎｅｗ　Ｙｏｒｋ：Ｊｏｈｎ　Ｗｉｌｅｙ＆　Ｓｏｎｓ，１９９０．　［３］　Ｍｏｒｚｙ　Ｔ，Ｗｏｊｃｉｅｅｈｏｗｓｋｉ　Ｍ，Ｚａｋｒｚｅｗｉｅｚ　Ｍ．Ｓｃａｌａｂｌｅ　ｈｉｅｒａｒ—ｃｈｉｃａｌ　ｃｌｕｓｔｅｒｉｎｇ　ｍｅｔｈｏｄ　ｆｏｒ　ｓｅｑｕｅｎｃｅｓ　ｏｆ　ｃａｔｅｇｏｒｉｃａｌ　ｖａｌｕｅｓ　［Ｃ］／／Ｐｒｏｅ　ｏｆ　ｔｈｅ　５ｔｈ　Ｐａｃｉｉｆｃ—Ａｓｉａ　Ｃｏｎｆｅｒｅｎｃｅ　Ｏｉｌ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ（ＰＡ　ＫＤＤ），Ｌｅｃｔｕｒｅ　Ｎｏｔｅｓ　ｉｎ　Ｃｏｍ—　ｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　２０３５．Ｎｅｗ　Ｙｏｒｋ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，２００１：２８２—２９３．　［４］　Ａｙｒｅｓ　Ｊ，Ｇｅｈｒｋｅｅｔａｌ　Ｊ．ＳｅｑｕｅｎｔｉＭ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ　ｕｓｉｎｇ　ａ　ｂｉｔｍａｐ　ｒｅｐｒｅｓｅｎｔａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　８ｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔ　Ｃｏｎｆ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．Ｅｄｍｏｎｔｏｎ，２００２：４２９－４３５．　［５］严蔚敏，吴伟民．数据结构［Ｍ］．北京：清华大学出版社，２００７：１４４—１４５．　［６］ＵＣＩ数据集［ＤＢ／ＯＬ］．［２００８－０３—１３］．ｈｔｔｐ：／／ｄｏｗｎｌｏａｄ．ｃｓｄｎ．ｎｅｔ／ｓｏｕｒｃｅ／３７８９２６．　［７］ＩＢＭ　Ａｌｍａｄｅｎ　Ｒｅｓｅａｒｃｈ　Ｃｅｎｔｅｒ．Ｑｕｅｓｔ　Ｄａｔａ　Ｍｉｎｉｎｇ　Ｐｒｏｊｅｃｔ［ＤＢ／ＯＬ］．（１９９６－０３—１２）［２００７－０５—２６］．ｈｔｔｐ：／／ｗｗｗ．ａｌｍａｄｅｎ．　ｉｂｍ．ｅｏｍ／ｅｓ／ｑｕｅｓｔ／ｓｙｎｄａｔａ．ｈｔｍ１．　［责任编辑：丁蓉］　一１６５—