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卷