[摘 要] 阐述了在电子商务系统中的研究和应用中，利用基于关联规则的多层次、超图分割聚类方法，对web网页和用户进行有效聚类。该方法借助网站层次图，可以根据实际需要，在各个层次上进行聚类分析，仅将高度相关的网页和用户聚在同一类，而将关联性较小的网页排除在聚类外。
[关键词] 聚类挖掘 电子商务 关联规则 超图
由于web具有方便、易用、高效的特点，电子商务显示出越来越强大的生命力，同时各种商业web站点也面临越来越激烈的竞争。
有效聚类web用户和网页对改进网站质量、完善电子商务中产品销售策略具有十分重要的意义。在电子商务中，浏览模式相似的用户具有相似的购买习惯，通过聚类挖掘，将这些用户聚集在同一类，可以制定相似的销售策略。根据浏览模式聚集在同一类中的网页，是大多数用户共同访问的网页，在这些网页之间建立超链接，以方便用户使用。
现有的基于浏览模式的web聚类挖掘研究方法中，只要用户请求了一个网页，便认为用户阅读了该网页，事实上有些被请求的网页用户并不关心，不会认真阅读的。通常一个实用网站包含大量的网页，现有的web聚类方法将每个网页当作一个被聚项，无论用户访问的频繁与否，总是归入一个类中，结果造成有些类中的网页之间几乎没有相关性。
鉴于以上考虑，本文提出了基于关联规则和超图分割的聚类web网页及用户的方法，不仅考虑了用户浏览网页的时间长短，还考虑了聚类层次（级别），将不相关网页项排除在聚类之外，使每个类中的网页具有较高的相关性。wWw.133229.cOm采用这种方法，可以优化web站点拓扑结构，指导企业调整营销策略，给客户提供动态的个性化的高效率服务。
一、建立电子商务网站的层次模型
建立电子商务网站的层次模型出于三点考虑。第一，网站中网页内容组织呈现树状结构。第二，在进行关联规则挖掘过程中，可能最下一级挖掘不出达到指定support的强规则，但是能从上级层次挖掘出达到指定support的强规则，或根据实际需要在某一个层次进行聚类分析。第三，对于电子商务网站，有些用户虽然访问了某网页，但是对其内容并不感兴趣，可能只是扫一眼就放弃。在此情况下，不应该认为用户认真阅读了该网页，所以应该记录网页的长度，通过计算用户的浏览时间和网页长度的比值来判断用户是否真正认真阅读了该页内容。
层次模型采用树状结构来描述，节点的数据域包含对应网页的层次名称（编号）和网页长度。树根应该取所研究的网站根目录（研究整个网站）或所研究的网站分支的最上层目录。在建立层次模型时，应根据网站的具体情况决定采用的方法。通常情况下，网页文件名能完全反映网页所在的层次，可以采用完全自动方法进行转换。
二、基于关联规则的聚类挖掘
1.预处理
在web站点中，服务器日志文件记录用户的访问方式、所访问的页面、访问时间、用户ip地址等信息，通过收集web日志所记录的用户浏览信息可以对网页和用户聚类。首先要对收集到的数据进行预处理，获得每个用户所访问的网页序列。将一个用户对某个特定网站的一次连续浏览（从登录该网站一直到离开该网站）所访问的网页序列称为一个用户浏览事务。如果用户中途访问了另一网站，而后又返回该网站，返回后所浏览的网页序列将组成另一个用户浏览事务。处理后的事务序列将具有如下的形式：
u_id（用户标志编号），p_id(页面编号)序列
2.挖掘关联规则并计算关联规则可信度的平均值
对经过预处理的浏览事务进行关联规则挖掘，挖掘出满足一定支持度的关联规则。关联规则是在挖掘出频繁网页集的基础上发现的，由于频繁网页集是大多数用户在一个事务，即一次网站访问中所共同浏览的页面，所以频繁网页集反映了这些网页或共同访问这些网页的用户之间存在一定的联系，如网页内容高度相关。在进行聚类时，应该首先考虑将频繁网页集中的网页聚合在一个类中。
通常挖掘频繁网页集的方法是在给定某一支持度的基础上进行的，满足该给定支持度的一个频繁网页集中的网页可能是另一个或另几个频繁网页集中的元素，那么将这些网页应该聚合到前一项目集还是后面的某一项目集？正确的选择应该是看这些网页和哪一项目集联系更为密切，可采用的方案有两种：提高支持度继续挖掘频繁网页集直到每一网页仅处于一个项目集或利用各频繁网页集中网页之间关联规则的可信度。进一步仔细分析，前一方案不可取，首先可能不存在一个支持度使每个网页仅位于一个频繁网页集中；其次即使存在这样一个支持度，再进行多次的频繁网页集挖掘代价也太高，实际中是不可行的。
相比之下，后一方案可行度高，在挖掘出满足指定支持度的频繁网页集的基础上，可以较为方便地计算出每一个频繁网页集中的每个关联规则的可信度。可信度的大小也反映了网页之间关联的密切程度。为此，计算每个频繁网页集中所有的关联规则的可信度，在此基础上计算其所有关联规则可信度的平均值，用可信度的平均值反映网页与不同的频繁网页集之间联系的密切程度。
3.利用超图进行网页聚类
超图是对图的扩充，允许一条边连接三个或三个以上的点。每条边带有权的超图称为加权超图，在挖掘出频繁网页集和关联规则的基础上，可以得到网站的加权超图。超图中的一个顶点代表一个网页，超图的边称为超边，超边连接的顶点是频繁网页集中的网页。每个超边的权取该边所对应的频繁网页集中所有关联规则可信度的平均值。
上图为超图的示意图，代表a，b和c所组成的频繁网页集的超边的权值，0.7是a，b和c三个网页所组成的所有关联规则可信度的平均值。
为了使聚集结果的每个类中的网页具有高度相关性，超图中仅包含出现在强关联规则中的网页。利用超图进行聚类的方法是逐步切割超边将超图进行分割，分割成多个子超图，分割的原则是被切割的超边的权值和尽可能小，从而保证将相互关联比较小的网页分割在不同的子图，而将关联比较密切的网页保留在同一子图内。分割过程继续进行直到被切割超边的权值和与留下的超边权值和的比值大于某一临界值，或所得到的子超图数目达到某指定值，分割过程结束，留下的各子超图便是聚类的结果。每一个子超图对应一个聚类，超图中的各顶点代表该聚类中所包含的网页。
4.事务和用户聚类
在将网页进行聚类的基础上，可以将浏览网站的事务和用户进行聚类。浏览事务聚类的原则是根据事务和网页聚类的相似度进行，将事务聚合在相似度最高的网页类中。事务和网页类的相似度可以按照如下公式计算：
|tj∩ci|/|ci|
其中，tj为一个事务，ci为一个聚类，|tj∩ci|为tj和ci中所包含的相同页面的数目，|ci|为ci中所包含的页面数目。
在记录网站用户标志的情况下，可以通过用户的浏览事务聚类将用户进行聚类，即将访问相似网页的用户聚在同一类。
5.聚类挖掘结果的可视化
聚类挖掘的结果是多维的，由于笛卡儿坐标系最多只有三个坐标，所以不能用通常的方法作图。而且这些多维的数据集一般不含有空间语义，数据集的各维之间没有空间连贯性，这也很难用传统的二维或三维图形直接表达多维空间。本文采用了一种通过主分量分析将多维空间坐标转换为三维坐标的挖掘结果可视化方法，实现聚类挖掘结果的可视化。根据生成的各个点之间的距离和簇的形状，我们可以有效地从大量数据中发现对我们有用的信息。
三、结论
阐述了在电子商务系统的研究和应用中，利用基于关联规则的多层次、超图分割聚类方法，对web网页和用户进行有效聚类。该方法借助网站层次图，可以根据实际需要，在各个层次上进行聚类分析；在挖掘出满足一定support的关联规则的基础上进行聚类，仅将高度相关的网页和用户聚在同一类，而将关联性较小的网页排除在聚类外。该方法对于改进网站质量、完善电子商务中产品销售策略具有十分重要的意义。
参考文献:
[1]pei j, han j, behazad m, et al. proceedings of the 1999 kdd workshop on web mining[c], kyoto: pkdd, 1999. 396-407
[2]cooley r, mobasher b, srivastava j. data preparation for mining world wide web browsing patterns [j]. knowledge and information system, 1999,1(1): 25-29
[3]karypis g, aggarwal r, kumar v, et al. multi-level hypergraph partitioning: applications in vlsi domain[r]. minnesota: university of minnesota, department of computer science, 1997.1-50
[4]刘子维等：一种聚类挖掘结果的可视化方法[j].计算机应用研究，2006，23（5）：75-76
