基于多镜像站点的分布式Web使用聚类

提出了一种适用于多镜像站点环境下的分布式Web使用聚类局部挖掘算法LUC和全局挖掘算法GUC,较好地解决了Web访问信息的异地存储、分布式算法通讯量等因素给模式分析过程带来的困难.将给出的算法用Java语言加以实现,并对算法性能进行了研究.结果证明,该算法是有效的,可以用来高效、准确地在多镜像站点环境下发现Web用户群体模式.

团购合买资源类别：文库，文档格式：PDF，文档页数：7，文件大小：846KB

D0I:10.13374/i.issnl00113.2007.09.047 第29卷第9期北京科技大学学报 Vol.29 No.9 2007年9月 Journal of University of Science and Technology Beijing Sep·2007 基于多镜像站点的分布式Wb使用聚类张克君2)杨炳儒)赵耿)曲文龙 1)北京电子科技学院，北京1000702)北京科技大学信息工程学院，北京100083 摘要提出了一种适用于多镜像站点环境下的分布式Wb使用聚类局部挖掘算法LUC和全局挖掘算法GUC,较好地解决了Wb访问信息的异地存储，分布式算法通讯量等因素给模式分析过程带来的困难.将给出的算法用Jaa语言加以实现，并对算法性能进行了研究·结果证明，该算法是有效的，可以用来高效、准确地在多镜像站点环境下发现Wb用户群体模式. 关键词镜像站点；Wb:聚类：用户事务聚类：分布式数据挖掘分类号TP31 聚类是一种无示例学习，它把不同的对象按照本文给出了一种适用于多镜像站点环境下的分相似性聚集成不同的类别，从而使人们可以更加系布式Wb使用聚类全局/局部挖掘算法GUC/ 统地研究各类事物的发展规律，Wb使用聚类主要 LUC,用于准确、高效地发现Wb用户群体模式是从网站的使用信息中得到具有相似访问兴趣的用其中，局部聚类算法LUC使用模糊k均值法对用户事务聚类，对Wb使用信息进行有效的聚类，可户事务进行软划分，相对于硬划分方法更符合客观以改善网站的质量，提高电子商务的效率，更好地实实际：全局聚类算法GUC在全局划分整合过程中现Web个性化服务-2] 提出并使用了共识链方法，用以提高整合划分的效目前，Wb使用聚类的研究还主要是针对集中率；在聚类过程中，局部站点可能产生一些不相称的式数据源进行挖掘，然而，众多站点为提高用 “噪声”质心，这些质心会歪曲全局划分结果，因而使户的访问效率，广泛采用了多镜像技术.所谓镜像用质心过滤方法来降低聚类“噪声”，提高全局聚类站点，就是把一个互联网上的网站数据镜像在异地结果的准确度其他服务器，并保持这些服务器数据的同步更新，用户访问这些服务器即可获得主服务器上同样的数 1 分布式Web使用聚类算法GUC基据.多镜像技术的出现，使得挖掘所用的数据源本思想服务器日志水平分布在不同的镜像站点上，这 GUC(distributed global user transactions clus- 为Wb使用挖掘技术带来了新的应用环境；在这种 tering algorithm)算法基本思想是采用分布式计算环境下进行Wb使用聚类挖掘，必然需要适合的分技术解决多镜像站点环境下的Wb用户事务聚类布式挖掘算法来获取全局模式知识，目前已有学者问题.首先，在局部站点上独立的局部聚类算法获在分布式聚类算法研究方面做了一些工作-)]，通得代表局部事务数据聚类的质心，由于所有局部站过对局部分布的数据进行本地独立地聚类，然后对点上的事务数据处于相同的维度空间，所以获得的多个局部的划分进行合并.文献[5]中，生成的模型局部质心可以提供关于全局事务聚类质心的信息，参数被发送到一个中心站点，在中心站点上生成“虚然后，只发送划分后的聚类质心到全局站点形成一拟对象”，然后利用EM算法来获取全局模式，文献个质心集合，最后，利用质心集合的有限知识来发 [6]在局部站点首先使用DBSCAN算法进行聚类，现全局事务划分，该步骤可以看成是如何在所有聚然后将每个局部站点的代表发送到一个中心站点，类质心上达成一个全局共识的问题，可通过下文提在中心站点上再次使用DBSCAN算法来发现全局出的共识链方法来完成，整合来自各局部站点的有模式限的质心信息后，获得代表全局事务数据划分的全收稿日期：2006-07-20修回日期：2006-09-16 局聚类质心，在整个处理过程中，局部站点间不需基金项目：国家自然基金资助项目(N。,70431002):国家科技成果重要共享聚类标签或站点上事务数据对象的属性门. 点推广计划项目(No.2003EC00001) 作者简介：张克君(1972一)，男，博士研究生；杨炳儒(1943一)男，局部站点在聚类过程中是可能产生一些不相称教授，博士生导师的“噪声”质心，在质心合并时，这些不相称的质心

基于多镜像站点的分布式 Web 使用聚类张克君12）杨炳儒2）赵耿1）曲文龙2） 1）北京电子科技学院北京100070 2）北京科技大学信息工程学院北京100083 摘要提出了一种适用于多镜像站点环境下的分布式 Web 使用聚类局部挖掘算法 LUC 和全局挖掘算法 GUC较好地解决了 Web 访问信息的异地存储、分布式算法通讯量等因素给模式分析过程带来的困难．将给出的算法用 Java 语言加以实现并对算法性能进行了研究．结果证明该算法是有效的可以用来高效、准确地在多镜像站点环境下发现 Web 用户群体模式．关键词镜像站点；Web；聚类；用户事务聚类；分布式数据挖掘分类号 TP31 收稿日期：2006-07-20 修回日期：2006-09-16 基金项目：国家自然基金资助项目（No．70431002）；国家科技成果重点推广计划项目（No．2003EC00001）作者简介：张克君（1972—）男博士研究生；杨炳儒（1943—）男教授博士生导师聚类是一种无示例学习它把不同的对象按照相似性聚集成不同的类别从而使人们可以更加系统地研究各类事物的发展规律．Web 使用聚类主要是从网站的使用信息中得到具有相似访问兴趣的用户事务聚类．对 Web 使用信息进行有效的聚类可以改善网站的质量提高电子商务的效率更好地实现 Web 个性化服务［1—2］．目前Web 使用聚类的研究还主要是针对集中式数据源进行挖掘［3—4］．然而众多站点为提高用户的访问效率广泛采用了多镜像技术．所谓镜像站点就是把一个互联网上的网站数据镜像在异地其他服务器并保持这些服务器数据的同步更新用户访问这些服务器即可获得主服务器上同样的数据．多镜像技术的出现使得挖掘所用的数据源 ———服务器日志水平分布在不同的镜像站点上这为 Web 使用挖掘技术带来了新的应用环境；在这种环境下进行 Web 使用聚类挖掘必然需要适合的分布式挖掘算法来获取全局模式知识．目前已有学者在分布式聚类算法研究方面做了一些工作［5—6］通过对局部分布的数据进行本地独立地聚类然后对多个局部的划分进行合并．文献［5］中生成的模型参数被发送到一个中心站点在中心站点上生成“虚拟对象”然后利用 EM 算法来获取全局模式．文献［6］在局部站点首先使用 DBSCAN 算法进行聚类然后将每个局部站点的代表发送到一个中心站点在中心站点上再次使用 DBSCAN 算法来发现全局模式．本文给出了一种适用于多镜像站点环境下的分布式 Web 使用聚类全局／局部挖掘算法 GUC／ LUC用于准确、高效地发现 Web 用户群体模式．其中局部聚类算法 LUC 使用模糊 k—均值法对用户事务进行软划分相对于硬划分方法更符合客观实际；全局聚类算法 GUC 在全局划分整合过程中提出并使用了共识链方法用以提高整合划分的效率；在聚类过程中局部站点可能产生一些不相称的 “噪声”质心这些质心会歪曲全局划分结果因而使用质心过滤方法来降低聚类“噪声”提高全局聚类结果的准确度． 1 分布式 Web 使用聚类算法 GUC 基本思想 GUC （distributed global user transactions clustering algorithm）算法基本思想是采用分布式计算技术解决多镜像站点环境下的 Web 用户事务聚类问题．首先在局部站点上独立的局部聚类算法获得代表局部事务数据聚类的质心由于所有局部站点上的事务数据处于相同的维度空间所以获得的局部质心可以提供关于全局事务聚类质心的信息．然后只发送划分后的聚类质心到全局站点形成一个质心集合．最后利用质心集合的有限知识来发现全局事务划分该步骤可以看成是如何在所有聚类质心上达成一个全局共识的问题可通过下文提出的共识链方法来完成．整合来自各局部站点的有限的质心信息后获得代表全局事务数据划分的全局聚类质心．在整个处理过程中局部站点间不需要共享聚类标签或站点上事务数据对象的属性［7］．局部站点在聚类过程中是可能产生一些不相称的“噪声”质心．在质心合并时这些不相称的质心第29卷第9期 2007年 9月北京科技大学学报 Journal of University of Science and Technology Beijing Vol．29No．9 Sep．2007 DOI:10．13374／j．issn1001－053x．2007．09．047

第9期张克君等：基于多镜像站点的分布式Wb使用聚类 .965 会歪曲全局划分结果，为了过滤或排除这些不相称其中，s(i=1,2,…,n)为n个会话，p(i=1,2 的质心，本文给出了一种质心过滤方法，这种方法 …,m)为m页面，v∈{0,1}(=1,2，…，n;j=1, 可以让全局站点有效地分析质心合并过程，而不是 2,,m)而0为对于p:的加权值，可以根据盲目地合并所有划分. s对p:的访问时间和p:本身的内容综合计算. GUC方法适用于许多已存在可以标记出“重心”的聚类算法，即能够产生代表每一个聚类中所有数据净化会话识别用户会话文件数据的聚类质心的算法，这类聚类算法的典型例子有k均值聚类算法、EM算法[8).图1描述了GUC 访问日志用户识别路径补充事务识别增量算法的全过程日志日志日志结构化处理 (镜像站点1) (镜像站点2) (镜像站点m) 站点文件站点结构务增量数据预处理及数据预处理及数据预处理及事务识别事务识别事务识别图2局部Wb日志挖掘预处理的具体过程 t Fig-2 Local Web log mining preprocessing 应用模糊k均值应用模糊k.均值应用模糊k均值或硬k均值算法或硬k均值算法或硬k均值算法在式(1)中，从每个s对应的行中取出可，视对局部数据子集进行聚类成局部聚类〈vl,v2,…,v)为一个m维向量，则SF就是这样质心，合并它们成全局质心集合的n个向量的集合，将集合中的每个向量以及指定最后的全局划分的类数目作为GUC聚类算法的输入，图1GC算法的全过程 3局部聚类算法LUC Fig.1 Preprocessing of GUC algorithm 通过对经典聚类算法的分析可知，划分聚类算 2 面向用户事务聚类的局部数据预法产生的每一个聚类结果都有一个代表着该类的特征的质心，在分布式环境下采用数据挖掘技术时，处理各分布式站点间的信息传递对挖掘算法的效率影响数据预处理是进行Wh使用挖掘的一个关键巨大，站点间传递信息量同算法效率成反比，因而，环节.其目的是将Web日志转化为可靠、完整、准在局部站点上的聚类算法选择上采用划分聚类算确且具有某种意义的数据形式，以满足Wb使用挖法，以求利用传递代表聚类的质心信息来缩减站点掘过程中模式发现算法实施的需要，对Wb日志间的信息量，进行预处理的结果直接影响到挖掘算法产生的规则均值聚类算法是最常用划分聚类算法，给定和模式的效率、准确度.可以说数据预处理过程是聚类数目k和目标函数F,k均值聚类算法把一个 Wb使用挖掘质量保证的关键. n个对象或元组的数据库划分成k个类，使得目标预处理包括数据净化、用户识别、会话识别和路函数在此划分下达到最优，k均值算法是把每个径补充处理、事务识别等步骤)，处理过程如图2所待辨识的对象严格地划分到某个类中，具有非此即示，采用文献[10]介绍的预处理方法，预处理的结彼的性质，因此也被称为硬k一均值聚类算法，例：果为一矩阵：考虑二维空间中的五个数据对象E1、E2、E3、E4和 SF= E5(如图3所示)，假定它们之间的空间临近距离作为彼此类似的度量，应用硬k均值算法能够产生两 pi p2 。ee Pm 个聚类，如图4所示， s1Kv11,201)〈v12,01) ·(U1m,201m 然而Wb用户事务是具有模糊性的，严格地将〈v21,D2)〈v22,022 ·〈v2m,202m》某个事务划分为某一类是不准确的，本文给出了一种模糊k均值算法来对用户事务进行软划分，模糊 SnL(Unl,wnD 《Un2,0nD k均值算法为一个数据集中的每一个对象指定一 (1) 个成员资格的度量，也就是说一个对象是怎样被分 0 s未访问pj 配到一个聚类的.对图3中所示的数据集，应用模 1 s:访问了pj (2) 糊k均值算法能够产生两个类，如图5所示

会歪曲全局划分结果．为了过滤或排除这些不相称的质心本文给出了一种质心过滤方法．这种方法可以让全局站点有效地分析质心合并过程而不是盲目地合并所有划分． GUC 方法适用于许多已存在可以标记出“重心”的聚类算法即能够产生代表每一个聚类中所有数据的聚类质心的算法．这类聚类算法的典型例子有 k—均值聚类算法、EM 算法［8］．图1描述了 GUC 算法的全过程．图1 GUC 算法的全过程 Fig．1 Preprocessing of GUC algorithm 2 面向用户事务聚类的局部数据预处理数据预处理是进行 Web 使用挖掘的一个关键环节．其目的是将 Web 日志转化为可靠、完整、准确且具有某种意义的数据形式以满足 Web 使用挖掘过程中模式发现算法实施的需要．对 Web 日志进行预处理的结果直接影响到挖掘算法产生的规则和模式的效率、准确度．可以说数据预处理过程是 Web 使用挖掘质量保证的关键．预处理包括数据净化、用户识别、会话识别和路径补充处理、事务识别等步骤［9］处理过程如图2所示．采用文献［10］介绍的预处理方法预处理的结果为一矩阵： SF＝ p1 p2 … pm s1 s2  sn 〈v11w11〉〈v12w12〉 … 〈v1mw1m〉〈v21w21〉〈v22w22〉 … 〈v2mw2m〉   …  〈v n1wn1〉〈v n2wn2〉 … 〈v nmwnm〉（1） vij＝ 0 si 未访问 pj 1 si 访问了 pj （2）其中si （ i＝12…n）为 n 个会话pi （ i＝12 …m）为 m 页面vij∈｛01｝（ i＝12…n；j＝1 2…m）．而 wij为 si 对于 pi 的加权值可以根据 si 对 pi 的访问时间和 pi 本身的内容综合计算．图2 局部 Web 日志挖掘预处理的具体过程 Fig．2 Local Web log mining preprocessing 在式（1）中从每个 si 对应的行中取出 vij视〈vi1vi2…vim〉为一个 m 维向量则SF 就是这样的 n 个向量的集合．将集合中的每个向量以及指定的类数目作为 GUC 聚类算法的输入． 3 局部聚类算法 LUC 通过对经典聚类算法的分析可知划分聚类算法产生的每一个聚类结果都有一个代表着该类的特征的质心．在分布式环境下采用数据挖掘技术时各分布式站点间的信息传递对挖掘算法的效率影响巨大站点间传递信息量同算法效率成反比．因而在局部站点上的聚类算法选择上采用划分聚类算法以求利用传递代表聚类的质心信息来缩减站点间的信息量． k—均值聚类算法是最常用划分聚类算法给定聚类数目 k 和目标函数 Fk—均值聚类算法把一个 n 个对象或元组的数据库划分成 k 个类使得目标函数在此划分下达到最优．k—均值算法是把每个待辨识的对象严格地划分到某个类中具有非此即彼的性质因此也被称为硬 k—均值聚类算法．例：考虑二维空间中的五个数据对象 E1、E2、E3、E4和 E5（如图3所示）假定它们之间的空间临近距离作为彼此类似的度量应用硬 k—均值算法能够产生两个聚类如图4所示．然而 Web 用户事务是具有模糊性的严格地将某个事务划分为某一类是不准确的．本文给出了一种模糊 k—均值算法来对用户事务进行软划分模糊 k—均值算法为一个数据集中的每一个对象指定一个成员资格的度量也就是说一个对象是怎样被分配到一个聚类的．对图3中所示的数据集应用模糊 k—均值算法能够产生两个类如图5所示．第9期张克君等：基于多镜像站点的分布式 Web 使用聚类 ·965·

,966 北京科技大学学报第29卷算法1模糊k均值聚类算法 E3 输入：包含具有p个特征的n个数据对象的数据集，聚类数量k,模糊值m>1. E4 输出：输入数据的k个划分 (1)一个n×k大小的U成员资格矩阵； (2)数据对象集内随机生成k个聚类中心位图3数据集中的数据对象置，或随机选择k个数据对象作为初始聚类质心， Fig.3 Objects of data set 记为C1,c2,…,C; (3)对所有的聚类质心=1,2，…，k和数据聚类2 对象i=1,2,,n,按照式(3)计算距离度量聚类1 E2 E3 di.=lxi-cjl2: (4)计算模糊成员资格矩阵U: E4 -1 d>0 1 d=0 图4k均值聚类的例子 (5)计算新的聚类质心： Fig.4 Example of hard k means clustering 聚类1 1≤≤k: (u） El E2 E3 =1 (6)重复步骤(3)到(5)，直到两次连续的迭带聚类2 产生的变化小于给定阈值： (7)保存聚类质心℃及聚类数量k于局部站点图5模糊聚类的例子局部站点通过模糊k均值聚类算法产生局部 Fig.5 Example of fuzzy k means clustering 划分后，接下来的工作就是对产生的局部划分进行整合，获取全局聚类结果，数据对象相似性度量的选择非常重要，这里选用的衡量标准是用欧几里德距离来度量数据对象间 4划分的整合的不同，如果每一个数据对象具有p维，也就是说对每一个分布式站点进行聚类后，产生了一个 p个属性，那么数据对象x:和x间的距离可以用下描述局部事务数据聚类的质心集合，由于所有局部式度量：站点上的事务数据具有相同的维度空间，所以获得 dr.x.= 的局部质心可以提供关于全局事务聚类质心的信息.该质心集合可以表示为C1,其中k为聚 (3) 类数目，全部的m个局部站点会产生m个质心集模糊k均值所采用的准则目标函数为平方差合{C1,华1，{C2j华1，，{Cm华1·接下来的问函数：题就是利用产生的质心集合的有限知识来获取全局 min (U,V)= (4) 事务划分，这个可以看成是如何在所有聚类质心上 (U,V) 达成一个全局共识的问题，其中，U包含聚类成员资格，对模糊算法用u∈ 获取全局共识的办法是将全部质心组织成k [0,1],m>1,对硬均值算法用u∈{0,1；V= 个共识链(consensus-chain),每个共识链包含m个 (v1,v2,…,ve)∈R甲，y:指第i个p维的聚类中心； (局部站点的数量)质心{c峰，c,…,c%,其中每一个 m≥1是一个用来控制U的模糊度的额外说明；质心来自不同站点，且1≤n≤k,组织策略是组织 D(x,v:)=D是xk同第i个聚类的偏差，并且相似的质心到每一个共识链中，最终目的是获得全 Da=‖x-:‖. 局最优化的配置*：

图3 数据集中的数据对象 Fig．3 Objects of data set 图4 k－均值聚类的例子 Fig．4 Example of hard k－means clustering 图5 模糊聚类的例子 Fig．5 Example of fuzzy k－means clustering 数据对象相似性度量的选择非常重要．这里选用的衡量标准是用欧几里德距离来度量数据对象间的不同．如果每一个数据对象具有 p 维也就是说 p 个属性那么数据对象 xi 和xj 间的距离可以用下式度量： dij（ xixj）＝ ∑ p k＝1 （ xik— xjk） 2 1 2＝‖xi—xj‖2 （3）模糊 k—均值所采用的准则目标函数为平方差函数： min （ UV） Jm（ UV）＝ ∑ c i＝1 ∑ N k＝1 u m ikDik（ xkvi）（4）其中U 包含聚类成员资格对模糊算法用 uik ∈ ［01］m ＞1对硬均值算法用 uik ∈｛01｝；V ＝（v1v2…vc）∈R cpvi 指第 i 个 p 维的聚类中心； m≥1是一个用来控制 U 的模糊度的额外说明； Dik（ xkvi）＝Dik 是 xk 同第 i 个聚类的偏差并且 Dik＝‖xk—vi‖2 2．算法1 模糊 k—均值聚类算法．输入：包含具有 p 个特征的 n 个数据对象的数据集聚类数量 k模糊值 m＞1．输出：输入数据的 k 个划分．（1）一个 n×k 大小的 U 成员资格矩阵；（2）数据对象集内随机生成 k 个聚类中心位置或随机选择 k 个数据对象作为初始聚类质心记为 c1c2…ck；（3）对所有的聚类质心 j＝12…k 和数据对象 i ＝12…n按照式（3）计算距离度量 dij＝‖xi—cj‖2；（4）计算模糊成员资格矩阵 U： uij＝ ∑ k l＝1 dij dil 2 m—1 —1 dij ＞0 1 dij ＝0 （5）计算新的聚类质心： cj＝ ∑ n i＝1 （ uij） m xi ∑ n i＝1 （ uij） m 1≤ j≤k；（6）重复步骤（3）到（5）直到两次连续的迭带产生的变化小于给定阈值；（7）保存聚类质心 cj 及聚类数量 k 于局部站点．局部站点通过模糊 k—均值聚类算法产生局部划分后接下来的工作就是对产生的局部划分进行整合获取全局聚类结果． 4 划分的整合对每一个分布式站点进行聚类后产生了一个描述局部事务数据聚类的质心集合．由于所有局部站点上的事务数据具有相同的维度空间所以获得的局部质心可以提供关于全局事务聚类质心的信息．该质心集合可以表示为｛Cij｝k j＝1其中 k 为聚类数目．全部的 m 个局部站点会产生 m 个质心集合｛C1j｝k j＝1｛C2j｝k j＝1…｛Cmj｝k j＝1．接下来的问题就是利用产生的质心集合的有限知识来获取全局事务划分这个可以看成是如何在所有聚类质心上达成一个全局共识的问题．获取全局共识的办法是将全部质心组织成 k 个共识链（consensus—chain）每个共识链包含 m 个（局部站点的数量）质心｛c n 1c n 2…c n m｝其中每一个质心来自不同站点且1≤ n≤k．组织策略是组织相似的质心到每一个共识链中最终目的是获得全局最优化的配置 ψ∗： ·966· 北京科技大学学报第29卷

第9期张克君等：基于多镜像站点的分布式Wb使用聚类 .967. 共识链中， cost (consensus-chain(n) 4.1距离矩阵 (5) 距离矩阵用来存储任意两个局部站点之间的聚类质心间的欧几里德距离。如果每个局部站点上有 cost(consensus-chain(n))= ,D(i)(6) C个聚类，那么距离矩阵的维数为CXC 其中，D严()=号空 d(c哈，c),j≠i,d(,)表示 4.2局部共识链矩阵局部共识链矩阵存储着任意两个被选择局部站共识链中的质心向量间的欧几里德距离，点之间的已匹配质心的对应关系，也就是第1个被共识链创建后，就可以用共识链中质心的加权选择站点的某个质心与第2个被选择站点质心相匹算术平均值来代表全局质心，质心的权重由局部站配，如果每个局部站点上有C个聚类，那么局部共点事务数据量的大小决定，如果用图的非邻接顶点识链矩阵的维数为CX2. 表示每个聚类的质心，用聚类之间的欧几里德距离 4.3全局共识链矩阵作为图的加权边，那么发现目标函数（式(6）)的全局全局共识链矩阵利用来自局部共识链矩阵的信最优值问题转化为完全m一划分匹配问题，这是典息来构建.全局共识链矩阵的行表示一个共识链. 型的NP一完全问题，因此还需要另外的解决方法，如果存在个M局部站点，每个局部站点上有C个由于目标函数（式(5）)的优化是困难的，因而采用启聚类，那么全局共识链矩阵的维数为C×M. 发式算法将质心分配到k个共识链中. 对于给定的一对局部站点，首先计算两者间的随机选择两个局部站点，应用最小权重完全双所有质心间的距离，获得一个CXC距离矩阵，每向匹配规则山（图6），以使目标函数（式(5）)达到个元素(i,)表示一个站点的第i个质心到另一个全局最优，将两站点的聚类质心分配到k个共识站点的第j个质心的距离，最小距离元素指出两个链，这样每一个共识链包含了两个质心匹配对.接局部站点间的第1对匹配质心，下一个最小距离指下来，随机挑选一个已经包含在共识链中的站点和出了两个局部站点间的第2对匹配质心.以此类一个新站点，再次使目标函数最优，将新站点的质心推，直到所有质心匹配完毕，如果一个局部站点上添加到与之相匹配的共识链中，反复使用上述方的两个质心都与另一个局部站点上的某一个质心匹法，将剩余未分配的局部站点的质心陆续添加到k 配，会产生冲突，为解决这个问题，约定若最近的质心已经被其他质心所匹配，那么该质心同下一个次近距离且没有被匹配的质心相匹配，这样，两个站点之间的质心一一对应举例说明全局共识链矩阵的形成过程（如图7 所示)：考虑四个局部站点S1、S2、S3和S4,每个站图6双向匹配例子（数值表示权重，粗线表示双向匹配关系）点产生三个聚类，图7(a)显示了三个局部共识链矩 Fig-6 Example of bipartite matching.The numbers on the edges are weights,and the thick lines show the mincost bipartite match- 阵之间的传递关系，图7(b)显示了三个局部共识链 ing 矩阵构成的全局共识链矩阵， S2 4 SI S2 S3 S4 1 2 3 1 2 2 3 3 1 3 (a)三个局部共识链矩阵之间的传递关系 (b)三个局部共识链矩阵板成的全局共识链矩阵图7三个局部链矩阵构成全局链矩阵的例子 Fig-7 Example of the formation of a global chain matrix from three local chain matrices 全局链矩阵的每一行为一个共识链，它表示了配，全局共识链生成算法（算法2）的输入是局部站局部站点间的质心匹配关系，如果全局共识链矩阵点的质心集合，质心数量不是事务数据对象数量的在形成过程中没有遇到冲突，则称之为质心完全匹函数，所以算法执行时间是常量，匹配完成后，共识

ψ∗＝argmin ψ⊂ f ∑ k n＝1 cost（consensus—chain（ n））（5） cost（consensus—chain（ n））＝ ∑ m i＝1 D n （ i）（6）其中D n （ i）＝ 1 2 ∑ m j＝1 d（ c n i c n j ）j≠ id（··）表示共识链中的质心向量间的欧几里德距离．共识链创建后就可以用共识链中质心的加权算术平均值来代表全局质心质心的权重由局部站点事务数据量的大小决定．如果用图的非邻接顶点表示每个聚类的质心用聚类之间的欧几里德距离作为图的加权边那么发现目标函数（式（6））的全局最优值问题转化为完全 m—划分匹配问题这是典型的 NP—完全问题因此还需要另外的解决方法．由于目标函数（式（5））的优化是困难的因而采用启发式算法将质心分配到 k 个共识链中．随机选择两个局部站点应用最小权重完全双向匹配规则［11］（图6）以使目标函数（式（5））达到全局最优将两站点的聚类质心分配到 k 个共识链这样每一个共识链包含了两个质心匹配对．接下来随机挑选一个已经包含在共识链中的站点和一个新站点再次使目标函数最优将新站点的质心添加到与之相匹配的共识链中．反复使用上述方法将剩余未分配的局部站点的质心陆续添加到 k 图6 双向匹配例子（数值表示权重粗线表示双向匹配关系） Fig．6 Example of bipartite matching．The numbers on the edges are weightsand the thick lines show the min-cost bipartite matching 共识链中． 4∙1 距离矩阵距离矩阵用来存储任意两个局部站点之间的聚类质心间的欧几里德距离．如果每个局部站点上有 C 个聚类那么距离矩阵的维数为 C×C． 4∙2 局部共识链矩阵局部共识链矩阵存储着任意两个被选择局部站点之间的已匹配质心的对应关系也就是第1个被选择站点的某个质心与第2个被选择站点质心相匹配．如果每个局部站点上有 C 个聚类那么局部共识链矩阵的维数为 C×2． 4∙3 全局共识链矩阵全局共识链矩阵利用来自局部共识链矩阵的信息来构建．全局共识链矩阵的行表示一个共识链．如果存在个 M 局部站点每个局部站点上有 C 个聚类那么全局共识链矩阵的维数为 C× M．对于给定的一对局部站点首先计算两者间的所有质心间的距离．获得一个 C× C 距离矩阵每个元素（ ij）表示一个站点的第 i 个质心到另一个站点的第 j 个质心的距离．最小距离元素指出两个局部站点间的第1对匹配质心下一个最小距离指出了两个局部站点间的第2对匹配质心．以此类推直到所有质心匹配完毕．如果一个局部站点上的两个质心都与另一个局部站点上的某一个质心匹配会产生冲突．为解决这个问题约定若最近的质心已经被其他质心所匹配那么该质心同下一个次近距离且没有被匹配的质心相匹配．这样两个站点之间的质心一一对应．举例说明全局共识链矩阵的形成过程（如图7 所示）：考虑四个局部站点 S1、S2、S3和 S4每个站点产生三个聚类图7（a）显示了三个局部共识链矩阵之间的传递关系图7（b）显示了三个局部共识链矩阵构成的全局共识链矩阵．图7 三个局部链矩阵构成全局链矩阵的例子 Fig．7 Example of the formation of a global chain matrix from three local chain matrices 全局链矩阵的每一行为一个共识链它表示了局部站点间的质心匹配关系．如果全局共识链矩阵在形成过程中没有遇到冲突则称之为质心完全匹配．全局共识链生成算法（算法2）的输入是局部站点的质心集合．质心数量不是事务数据对象数量的函数所以算法执行时间是常量．匹配完成后共识第9期张克君等：基于多镜像站点的分布式 Web 使用聚类 ·967·

.968 北京科技大学学报第29卷链就包含了相似类型的质心， (3)对每个共识链，对该链中的质心进行算术全局聚类质心通过所有局部站点中事务数据数加权平均值计算（按照质心对应的聚类的数据对象量进行加权平均获得，例如，有四局部站点，每个站的数量)，每个共识链中获得的质心算术平均值代点上有三个聚类，若第1个站点的第1个聚类（包含表一个全局聚类的质心， 100个数据对象)，与第2个站点的第2个聚类（包 (4)计算每一个数据对象到各全局聚类质心的含200个数据对象)匹配，同时也与第3个站点的第距离，匹配该数据对象到最近的聚类质心 2个聚类（包含50个数据对象）、第4个站点的第1 局部站点数据对象的聚类任务在本地执行，只个聚类（包含100个数据对象）相匹配，设第i站点有聚类质心在处理器间传递，这样可以避免处理器的第j个聚类的质心为c,则全局意义上的聚类为：间传递大量的数据，算法速度的提高是可以预料的· _100c11+200c22+50c32+100c42 第1步的时间复杂度为O(mkt),其中m是局部 100+200+50+100 (7) 站点的数目，n是某个局部站点数据对象的数目，k 全局聚类质心创建后，利用距离矩阵，所有的数是聚类的数目，t是迭代的次数，m《n,k《n;第2 据对象就可以匹配到最近的全局聚类质心. 步时间复杂度为m2k2/4,所以该步骤执行时间为算法2全局共识链生成算法常量：第3步的执行时间是常量；第4步时间复杂度输入：局部站点的聚类质心为O(n),其中n为全局数据对象的数量，所以算输出：全局共识链矩阵法总的时间复杂为O(nt),通常t《n,所以理论上 (1)对局部站点进行编号从1到M,C为每个算法具有较高的效率. 局部站点上的聚类集合，初始化全局共识链矩阵为 4.5质心过滤零，=1，J=2; 在聚类过程中，局部站点可能产生一些不相称 (2)while(=M); 的“噪声”质心，在质心合并时这些质心会歪曲全局 (3): 划分结果，所以需要对这些不相称的质心进行过滤 (4)选择站点I和站点，计算质心间的距离，或排除并存储到距离矩阵的相应位置(ow,col)处；如果共识链中的质心彼此间具有相同的距离， (5)求得距离矩阵中的最小值，并记录其位置那么它们显然是相似的，可以用一个指标来衡量一值(row,col)到局部共识链矩阵；个共识链中质心间的协调程度（简称协调度），表示 (6)w hile(局部共识链矩阵未填充完整)；为： (7){; (8) (⑧)发现距离矩阵中下一个最小值，记录位置 (row,col)到局部链矩阵；其中，A是一个共识链中活动质心的数量，d(j)是 (9): 第j个活动质心到其他活动质心的距离和，tot-d= (10)f(=1): d(1)+d(2)+…+d(A),CH-i表示第i个全局 (11)用局部共识链矩阵中的对应关系构建全聚类的共识链. 局共识链矩阵的前两列；质心过滤使用如下规则：初始设定所有质心是 (12)else: 活动的，即准备参与到整合过程，用共识链中的所 (13)用局部共识链矩阵填充全局共识链矩阵有质心可以得到协调度H,如果排除链中的一个质的第J列，且利用全局共识链矩阵的第Ⅰ列来传递心会使协调度H变化量高于给定阈值，将该质心变关系；成非活动的，直到没有选择满足条件，计算全局质 (14)I=1+1,J=J+1: 心时不使用非活动质心，即过滤掉非活动质心，对 (15). 构造时产生冲突的共识链进行质心过滤，有利于提 4.4分布式Web用户事务聚类算法GUC 高全局质心的准确度，如果在一个共识链中所有的算法3多镜像站点环境下的分布式Wb用户质心确实相同，那么默认的协调度H=1, 事务聚类算法GUC· (1)利用模糊均值或硬k均值算法在每个 5实验与分析局部站点上进行本地聚类用Java语言实现所给出的GUC算法及文献 (2)调用共识链算法构建全局共识链矩阵， [5]的算法，采用4台内存为256MB的PIV1.8G

链就包含了相似类型的质心．全局聚类质心通过所有局部站点中事务数据数量进行加权平均获得．例如有四局部站点每个站点上有三个聚类若第1个站点的第1个聚类（包含 100个数据对象）与第2个站点的第2个聚类（包含200个数据对象）匹配同时也与第3个站点的第 2个聚类（包含50个数据对象）、第4个站点的第1 个聚类（包含100个数据对象）相匹配设第 i 站点的第 j 个聚类的质心为 cij则全局意义上的聚类为： cgi＝ 100c11＋200c22＋50c32＋100c42 100＋200＋50＋100 （7）全局聚类质心创建后利用距离矩阵所有的数据对象就可以匹配到最近的全局聚类质心．算法2 全局共识链生成算法．输入：局部站点的聚类质心．输出：全局共识链矩阵．（1）对局部站点进行编号从1到 MC 为每个局部站点上的聚类集合初始化全局共识链矩阵为零I＝1J＝2；（2） while（ J！＝ M）；（3）｛；（4）选择站点 I 和站点 J计算质心间的距离并存储到距离矩阵的相应位置（rowcol）处；（5）求得距离矩阵中的最小值并记录其位置值（rowcol）到局部共识链矩阵；（6） while（局部共识链矩阵未填充完整）；（7）｛；（8）发现距离矩阵中下一个最小值记录位置（rowcol）到局部链矩阵；（9）｝；（10） if（ I＝1）；（11）用局部共识链矩阵中的对应关系构建全局共识链矩阵的前两列；（12） else；（13）用局部共识链矩阵填充全局共识链矩阵的第 J 列且利用全局共识链矩阵的第 I 列来传递关系；（14） I＝I＋1J＝J＋1；（15）｝． 4∙4 分布式 Web 用户事务聚类算法 GUC 算法3 多镜像站点环境下的分布式 Web 用户事务聚类算法 GUC．（1）利用模糊 k—均值或硬 k—均值算法在每个局部站点上进行本地聚类．（2）调用共识链算法构建全局共识链矩阵．（3）对每个共识链对该链中的质心进行算术加权平均值计算（按照质心对应的聚类的数据对象的数量）．每个共识链中获得的质心算术平均值代表一个全局聚类的质心．（4）计算每一个数据对象到各全局聚类质心的距离匹配该数据对象到最近的聚类质心．局部站点数据对象的聚类任务在本地执行只有聚类质心在处理器间传递这样可以避免处理器间传递大量的数据算法速度的提高是可以预料的．第1步的时间复杂度为 O（ mnkt）其中 m 是局部站点的数目n 是某个局部站点数据对象的数目k 是聚类的数目t 是迭代的次数m≪ nk≪ n；第2 步时间复杂度为 m 2k 2／4所以该步骤执行时间为常量；第3步的执行时间是常量；第4步时间复杂度为 O（ n）其中 n 为全局数据对象的数量．所以算法总的时间复杂为 O（ nt）通常 t≪ n所以理论上算法具有较高的效率． 4∙5 质心过滤在聚类过程中局部站点可能产生一些不相称的“噪声”质心在质心合并时这些质心会歪曲全局划分结果所以需要对这些不相称的质心进行过滤或排除．如果共识链中的质心彼此间具有相同的距离那么它们显然是相似的．可以用一个指标来衡量一个共识链中质心间的协调程度（简称协调度）表示为： H（CH— i）＝ 1 lb ∑ A j＝1 d（ j） tot— d lb d（ j） tot— d （8）其中A 是一个共识链中活动质心的数量d（ j）是第 j 个活动质心到其他活动质心的距离和tot— d＝ d（1）＋ d（2）＋…＋ d（ A ）CH— i 表示第 i 个全局聚类的共识链．质心过滤使用如下规则：初始设定所有质心是活动的即准备参与到整合过程．用共识链中的所有质心可以得到协调度 H如果排除链中的一个质心会使协调度 H 变化量高于给定阈值将该质心变成非活动的直到没有选择满足条件．计算全局质心时不使用非活动质心即过滤掉非活动质心．对构造时产生冲突的共识链进行质心过滤有利于提高全局质心的准确度．如果在一个共识链中所有的质心确实相同那么默认的协调度 H＝1． 5 实验与分析用 Java 语言实现所给出的 GUC 算法及文献［5］的算法．采用4台内存为256MB 的 PIV1∙8G ·968· 北京科技大学学报第29卷

第9期张克君等：基于多镜像站点的分布式Wb使用聚类 .969. 兼容机模拟多镜像站点环境，站点运行在Windows 600 Server2000OS上，实验数据来自美国加利福尼亚 ◆一本文GUC聚类算法 500 ■一文献[5】聚类算法大学Irvine分校的UCIkdd数据仓库的具有448个 ★一一次性应用模糊k均值算法 400 URL的WWW服务器日志文件，提取其中的70000 ●一一次性应用硬k.均值算法条记录，预处理得到3128个用户事务 300 首先测试GUC算法准确性.为了验证方便，测 200 试时先设计了五个大小为0.4,0.8,1.2,1.6和 100 2.0MB不同的测试用例.首先用手工方法对这些数 0 0.4MB0.8MB1.2MB1.6MB2.0MB 据进行分析，得到一定数目的相似用户事务集合测试用例大小在测试GUC算法（局部LUC采用模糊k均值算法)及文献[5]算法时，每个用例被均匀分割部署在图9用户事务聚类执行时间测试环境中，然后进行聚类；另外，将每个用例直接 Fig.9 Runtime of user transaction clustering 使用k均值算法进行聚类，最后得到与手工聚类数目相同的结果.将这些结果与手工得到的结果比较 6 结论得到图8所示准确度曲线.图8表明，GUC算法获本文提出了一个基于多镜像站点的分布式得用户事务聚类的准确率在92%左右，比文献[5] Web用户事务聚类算法，与传统的Weh使用聚类算法的准确度要高。同时可以发现，针对同一个用方法相比，它具有以下特点：(1)该算法是一种分布例模糊k均值聚类算法要比硬k均值聚类算法在式聚类算法；(2)在局部站点聚类过程中引入适合于聚类准确度上要高，其原因是Wb用户事务具有模对用户事务进行软划分的模糊k一均值聚类方法：糊性，把每个待辨识的对象严格地划分到某个类中 (③)通过共识链方法利用有限的质心集合快速生成是不太准确的，针对Wb站点访问这种现实世界的全局划分；(4)采用质心过滤方法来降低聚类“噪声” 情况，有必要使用具有软划分特性的模糊聚类算法提高全局聚类结果的准确度，实验表明，本文提出 ■本文GUC聚类算法口一次性应用模糊k均值算法的Wb用户事务聚类算法GUC比已有的相关分布 ■文献[们聚类算法口一次性应用硬k均值算法 100 式聚类算法准确性高，算法运行时间短、扩展性比较 80 好，能够有效地解决多镜像站点环境下的Wb用户 60 事务聚类知识发现问题 0 参考文献 0.4MB 0.8MB 1.2MB 1.6MB 2.0MB [1]Mobasher B,Cooley R.Creating adaptive Web sites through us 测试用例 agebased clustering of URLs//Processing of the 1999 IEEE Knowledge and Data Eng.Exchange Workshop (KDEX'99). 图8聚类算法准确度比较曲线 New York:1999:32 Fig.8 Accuracy of clustering algorithms [2]Ozer M.User segmentation of online music services using fuzzy 其次，测试GUC算法的效率及可扩展性，测试 clustering.Omega.2001.29(2):193 [3]Manco G.Ortale R,Sacca D.Similarity-based clustering of web 时采用上述五个用例，记录采用GUC算法、文 transactions//Proceedings of the 2003 ACM Symposium on Ap 献[5]算法和一次性应用k均值算法在上述五种情 plied Computing.Melbourne,2003:1212 况下的执行时间，得到图9所示的曲线图，结果表 [4]Runkler T A.Bezdek JC.Web Mining with relational clustering. 明：对于用户事务聚类，在任何一个测试用例里， Int J Approximate Reasoning.2003(32):217 GUC算法的执行时间远小于集中式k一均值算法， [5]Ghosh J,Meruqu S.Distributed clustering with limited knowl- edge sharing//Proceedings of the 5th International Conference on 这是由于GUC算法使用了分布式处理；GUC算法 Advances in Pattern Recognition (ICAPR).2003:48 比文献[5]算法的执行效率要高；此外，随着测试数 [6]Januzaj E.Kriegel H P,Pfeifle M.Towards effective and effi- 据量的增加，GUC算法执行时间曲线上升趋势比较 cient distributed clustering /Proceeding of International Work- 慢，说明GUC算法随着操作数据量的增加运行时 shop on Clustering Large Data Sets.3rd IEEE International Con 间增加很少，具有较好的扩展性 ference on Data Mining (ICDM).2003:49 [7]Prodip Hore.Distributed Clustering for Scaling Classic Algorithms [Dissertation].University of South Florida.2004:3

兼容机模拟多镜像站点环境站点运行在 Windows Server2000OS 上．实验数据来自美国加利福尼亚大学 Irvine 分校的 UCIkdd 数据仓库的具有448个 URL 的 WWW 服务器日志文件提取其中的70000 条记录预处理得到3128个用户事务．首先测试 GUC 算法准确性．为了验证方便测试时先设计了五个大小为 0∙40∙81∙21∙6 和 2∙0MB不同的测试用例．首先用手工方法对这些数据进行分析得到一定数目的相似用户事务集合．在测试 GUC 算法（局部 LUC 采用模糊 k—均值算法）及文献［5］算法时每个用例被均匀分割部署在测试环境中然后进行聚类；另外将每个用例直接使用 k—均值算法进行聚类最后得到与手工聚类数目相同的结果．将这些结果与手工得到的结果比较得到图8所示准确度曲线．图8表明GUC 算法获得用户事务聚类的准确率在92％左右比文献［5］算法的准确度要高．同时可以发现针对同一个用例模糊 k—均值聚类算法要比硬 k—均值聚类算法在聚类准确度上要高其原因是 Web 用户事务具有模糊性把每个待辨识的对象严格地划分到某个类中是不太准确的针对 Web 站点访问这种现实世界的情况有必要使用具有软划分特性的模糊聚类算法．图8 聚类算法准确度比较曲线 Fig．8 Accuracy of clustering algorithms 其次测试 GUC 算法的效率及可扩展性．测试时采用上述五个用例记录采用 GUC 算法、文献［5］算法和一次性应用 k—均值算法在上述五种情况下的执行时间得到图9所示的曲线图．结果表明：对于用户事务聚类在任何一个测试用例里 GUC 算法的执行时间远小于集中式 k—均值算法这是由于 GUC 算法使用了分布式处理；GUC 算法比文献［5］算法的执行效率要高；此外随着测试数据量的增加GUC 算法执行时间曲线上升趋势比较慢说明 GUC 算法随着操作数据量的增加运行时间增加很少具有较好的扩展性．图9 用户事务聚类执行时间 Fig．9 Runtime of user transaction clustering 6 结论本文提出了一个基于多镜像站点的分布式 Web 用户事务聚类算法．与传统的 Web 使用聚类方法相比它具有以下特点：（1）该算法是一种分布式聚类算法；（2）在局部站点聚类过程中引入适合于对用户事务进行软划分的模糊 k—均值聚类方法；（3）通过共识链方法利用有限的质心集合快速生成全局划分；（4）采用质心过滤方法来降低聚类“噪声” 提高全局聚类结果的准确度．实验表明本文提出的 Web 用户事务聚类算法 GUC 比已有的相关分布式聚类算法准确性高算法运行时间短、扩展性比较好能够有效地解决多镜像站点环境下的 Web 用户事务聚类知识发现问题．参考文献［1］ Mobasher BCooley R．Creating adaptive Web sites through usage-based clustering of URLs ∥ Processing of the 1999 IEEE Knowledge and Data Eng．Exchange Workshop （KDEX’99） New York1999：32 ［2］ Ozer M．User segmentation of online music services using fuzzy clustering．Omega200129（2）：193 ［3］ Manco GOrtale RSacca D．Similarity-based clustering of web transactions∥Proceedings of the 2003 ACM Symposium on Applied ComputingMelbourne2003：1212 ［4］ Runkler T ABezdek J C．Web Mining with relational clustering． Int J Approximate Reasoning2003（32）：217 ［5］ Ghosh JMerugu S．Distributed clustering with limited knowledge sharing∥Proceedings of the5th International Conference on Advances in Pattern Recognition （ICAPR）2003：48 ［6］ Januzaj EKriegel H PPfeifle M．Towards effective and efficient distributed clustering ∥Proceeding of International Workshop on Clustering Large Data Sets3rd IEEE International Conference on Data Mining （ICDM）2003：49 ［7］ Prodip Hore．Distributed Clustering for Scaling Classic Algorithms ［Dissertation］．University of South Florida2004：3 第9期张克君等：基于多镜像站点的分布式 Web 使用聚类 ·969·

点击进入文档下载页（PDF格式）

已到末页，全文结束

点击下载（PDF格式）

浏览记录

基于多镜像站点的分布式Web使用聚类