工程硕士学位论文
ri=ri∪(
ri ={ ipi，(
3.3.4 路径完整
在识别用户会话过程中的另一个问题是确定访问日志中是否有重要的请求没有被记录，有一些原因会导致路径的不完整，例如用户在浏览的过程中使用的“后退”按钮，这就使得日志所记录的有关用户浏览的页面少于用户实际所浏览的页面数量，这就是路径缺失，若引用日志不完整，可以使用站点的拓扑结构代替。通过这种方法将遗漏的页面请求添加到用户的会话文件中。
在路径补充中遵循的一个原则就是在用户的一次会话的页面集中，除了起始页面外，每个页面同它上一个页面存在链接关系。
3.3.5事务识别
用户会话是Web日志挖掘中唯一具备自然事务特征的元素，但是，可能它对于某些挖掘算法来说粒度太粗，需要利用分割算法将其转化为更小的事务。 事务识别就是将用户会话分割为更小的事务，也就是从用户会话中次前进浏览的第一页到回退前一页组成的路径，所以我们可以结合网站结构来分割事务，分割好的事务构成事务数据库，可以在此基础上挖掘关则。
常用的事务分割方法有：引用长度(Reference Length)、最大向前路径(Maximal Forwardpath)、时间窗口(Time Window)等[33]。其中引用长度法以浏览时间为依据，把网页分为辅助页和内容页，以此来分割用户会话。最大向前路径法以Web日志访问序列中的访问链的最大向前深度来决定事务。时间窗口法则仅仅通过时间差T来分割事务，同一个事务中的任意两个页面的最大访问时间差不能超过T。
3.4 试验数据（Test Data）
下面取自徐州市政府网站Web服务器上的部分数据，测试上面的用户识别及会话识别技术。为简化表格,X 代表“Mozilla/ 4. 0 ( compatible ; MSIE6. 0 ; Windows NT 5.1) ”,Y 代表“Mozilla/ 4. 0 ( compatible ; MSIE6. 0 ; Win2dows NT
26
3 数据预处理
5. 0) ”, 这里WindowsNT 5. 0 代表的是Windows2000 操作系统,Windows NT 5. 1 代表的是Windows XP操作系统。Date均为2008.12.01，Url也用字母代替。
表3-3 原始日志记录
Table 3-3 Primitive log record 序号 1 2 3 4 5 6 7 8 9 10 IP地址 121.233.43.40 121.233.43.40 218.12.194.18 121.233.43.40 218.12.194.18 202.84.17.181 121.233.43.40 202.84.17.181 58.218.78.194 218.12.194.18 Date/Time 00:00:27 00:00:28 00:00:31 00:00:31 00:00:32 00:00:32 00:00:32 00:00:33 00:00:34 00:00:34 Url index.html a.html index.html d.html k.html index.html m.html q.html w.html s.html Refer index.html a.html index.html d.html index.html k.html Agent X X X X X Y X Y X X 将上面讨论的Web 日志预处理的几个过程中的相关算法作用于表2 中的日志记录,得到的结果如表5 所示
表3-4 经过数据预处理后的用户会话记录
Table 3-4 User session record after data pre-processing 序号 1 IP地址/Agent 121.233.43.40/X Date/Time 00:00:27 00:00:28 00:00:31 00:00:32 2 218.12.194.18/X 00:00:31 00:00:32 00:00:34 3 202.84.17.181/Y 00:00:32 00:00:33 4 58.218.78.194/X 00:00:34 Url index.html a.html d.html m.html index.html k.html s.html index.html q.html w.html Refer index.html a.html d.html index.html k.html index.html 3.5 小结（Summary）
通过对Web 日志挖掘的数据预处理部分进行研究，分析了数据预处理的各个阶段需要解决的问题和采用的解决方法，Web 日志挖掘的数据预处理的结果影响到挖掘算法产生的规则和模式，因此预处理过程也是Web 日志挖掘质量保
27
工程硕士学位论文
证的关键。
本章介绍了Web日志预处理的基本概念和方法，介绍了Web日志数据预处理的五个阶段：数据清理、用户识别、会话识别、路径补充和事务识别，并对各个阶段的任务和处理方法进行了分析。
28
4 基于模糊相似矩阵的Web日志的动态聚类
4 基于模糊相似矩阵的Web日志的动态聚类 4 Dynamic Cluster Based on Fuzzy Similarity Matrix Web Log
聚类（clustering）是指将数据对象分成多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。聚类不需预先定义好类，它是无指导学习，它对未知数据的划分和分析起着非常有效的作用。通过聚类，能够识别密集和稀疏的区域，发现全局的分布模式，以及数据属性之间的相互关系等。聚类的应用非常广泛，在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征；在保险行业，利用数据挖掘技术，提高保险公司的成本控制、风险预测和防范能力是非常有意义的。
4.1 常用的聚类算法比较与分析（Comparison and Analysis of Commonly Used Clustering Algorithms）
为了找到效率高、通用性强的聚类方法人们从不同角度提出了许多种聚类算法，一般可分为分裂（划分）方法，层次方法，基于密度的方法，基于网格的方法和基于模型的五大类[34]。
表4-1 聚类算法的分类
Table 4-1 Cluster algorithm classification 类别 算法 分裂（划分）法 K-MEANS算法（K-平均）、K-MEDOIDS算法（K-中心点）、CLARANS算法（基于选择的方法） 层次法 BIRCH算法（平衡迭代归约和聚类）、CURE算法（代表聚类）、CHAMELEON算法（动态模型） 基于密度 的方法 基于网络 的方法 基于模型 的方法 DBSCAN算法（基于高密度连接区域）、OPTICS算法（对象排序识别）、DENCUE算法（密度分布函数） STING算法（统计信息网格）、CLIQUE算法（聚类高维空间）、WAVE-CLUSTER算法（小波变换） 统计学方法、神经网络方法
29
工程硕士学位论文
4.1.1 基于分裂（划分）的聚类算法
给定一个有N个元组或记录的数据集，分裂法构造K个分组，每一个分组就代表一个聚类，K (1)、K-MEANS 算法（K-平均）。该算法首先随机地选择k 个对象，每个对象初始地代表了一个类的平均值或中心，对剩余的每个对象，根据其与各个类中心的距离，将它赋给最近的类；然后重新计算每个类的平均值。聚类结果与数据的输入顺序也有明显的关系，对于“噪声”和孤立点数据也是敏感的，其时间复杂度为O(nkt)。 (2)、K-MEDOIDS 算法（K-中心点）。该算法首先首先为每个簇随意选择一个代表对象，剩余的对象根据其与代表对象的距离分配给最近的一个簇，然后反复地用非代表对象来替代代表对象，以改进聚类的质量。 (3)、CLARANS算法（基于选择的方法）。它在搜索的过程中随机性的选取一个样本，在替换了一个中心点后得到的聚类结果被称为当前聚类结果的邻居，搜索的邻居点数目被用户定义的一个参数加以限制。如果找到一个比它更好的邻居，则把中心点移到该邻居节点上，否则把该点作为局部最小量。该算法的计算复杂度大约是O (n2)。 4.1.2 基于层次的聚类算法 基于层次的聚类算法是将数据对象进行层次分解，直到满足某种条件为止，具体分解是自底向上或者自顶向下形成，分层聚类的方法可以进一步分为凝聚的和分裂的方法，分层聚类方法对样本的输入次序敏感，而且一旦一个步骤(合并或分裂) 完成，它就不能被撤销，因此在合并或分裂时必须慎重。目前基于此的算法有： (1)、BIRCH 算法：BIRCH 算法引言两个概念：聚类特征和聚类特征树(CF) 两个参数，聚类特征是对给定子聚类的统计汇总，聚类特征树是高度平衡的树，它存储了层次聚类的聚类特征。通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算，故该算法通过一次扫描就可以进行较好的聚类，计算复杂度是O(n)。 (2)、CURE 算法：CURE 算法把每个数据点看成一簇，然后再以一个特定的收缩因子向中心“收缩”它们，即合并两个距离最近的代表点的簇。每个类有多于一个的代表点使得CURE 算法可以适应非球形的几何形状，类的收缩或凝聚可以有助于控制孤立点的影响，但参数的设置对聚类结果有显著的影响，CURE 算法的复杂度是O(n)。 30