基于后缀树的知识点间关联规则挖掘算法.pdfVIP

第 26卷第 1期 杭 州 电 子 科 技 大 学 学 报 Vo1．26，No．1 加06年02月 J~mal of Ha h0Il Dianzi University F曲． 基于后缀树的知识点间关联规则挖掘算法 董云耀 ，李 笑 (杭州电子科技大学计算机学院，浙江杭州310018) 摘要 ：在个性化的网络学习中，对知识点间的关联规则进行挖掘是一个关键的问题。该文提出了 一 种基于后缀树的知识点间关联规则挖掘算法，该算法通过对 web日志数据构造后缀树进行序列 挖掘，动态地挖掘最大频繁序列，进而发现有意义的知识点间的关联规则。 关键词：后缀树；关联规则 ；数据挖掘 中图分类号 ：TP311 文献标识码：A 文章编号：1001—9146(2006)01—00O9—05 O 引 言 当前社会提倡终身教育与素质教育，教育要为挖掘和发展学生的个性服务 。个性化网络学习系统 是建立在对学习者学习情况分析的基础上。首先系统需要有每门课程的知识点，需要知道每门课程的 所有知识点及知识点间的关系。知识点可以由有经验的教师给出，当然知识点间的关联关系也可以由 教师给出，但如果能获得学生的理解模式，也就是说知识点之间的关联规则是建立在学生对知识点的认 识规律的基础上，则这些关联规则更适应学生学习规律 。这正是个性化网络学习系统所需要的。 1 相关工作 1．1 网络 日志 本课题采用分析挖掘 日志数据[]来获得知识点问的关联规则。网络 日志是本课题的重要数据源。 网络学习系统本身作为网络教育的支撑平台是以大型网站的形式对学生提供服务。在服务器端，服务 器web日志会记录请求的详细信息，网站管理员可以根据需要定制所需记录的所有信息，这样可以获得 学生请求访 问的页面序列。 在网络学习系统中，每个页面就是一个资源，每个页面包含各 自的主知识点，页面的访 问序列就反 应了学生学习知识点的先后顺序，也就是知识点间的关联规则。本课题的知识点间的关联规则的挖掘 就是建立在此机制上。每条记录具体记录了用户请求的时间，也就是说 日志文件中的序列是有顺序的。 它反映了请求资源的一种顺序，将资源的请求序列转换成知识点的相应序列，对此知识点序列进行挖 掘，来获得知识点间关联规则，即前驱、后继关系。 收稿 日期：2005—09一l1 作者简介：董云耀 (1961～)，男，浙江桐乡人，副教授 ，计算机网络与信息系统 10 杭 州 电 子 科 技 大 学 学 报 2006 1．2 对网络 日志的传统挖掘算法 网络 日志是重要的数据资源，国内外有许多研究机构在研究网络 日志的挖掘方法。 (1)Apriori算法，在关联规则挖掘的诸算法中，Apriori算法应用最为广泛[引·。Apriori关联规则挖 掘算法虽然能够有效地挖掘静态事务数据库中的关联规则，但存在两个问题：Apriori算法每生成一个k 一 频繁项集，都需要扫描整个事务数据库，因此，在查找最大频繁项集上花费的时间代价太大；Apriori算 法不能有效地实现增量数据的挖掘。本文提出的MFS挖掘算法能有效地解决这两个方面的问题。 (2)利用概率统计挖掘知识点间关联规则，在文献 4中假设p1，p2是网站的两页面，P(pl／p2)代表 用户在已访问p2后又访问p1的概率，p(p2／p1)代表用户在已访问p1后又访问p2的概率。p1和p2之 间的关系概率取 p(pl／p2)和p(p2／p1)中的较小者，若该关系概率小于系统设定的峰值，则 pl和p2间 的关系就不存在。该方法势必要建立一个矩阵，该矩阵的维是网站的页面，矩阵的数据是P(i／j)，i，i代 表相对应的单元。该方法采用一刀切的模式，对所有页面两两配对计算关系概率，这样计算速度慢，且 只能计算两个页面的关系，没有充分利用 日志数据来简化计算量和计算复杂度。 2 后缀树挖掘算法 在本课题中采用后缀树方法寻找 日志序列中的频繁序列，这个算法可以很好的弥补以上两种算法 的不足之处 。 2．1 最大频繁子序列 一 个用户会话是用户在一个时间段 内用户浏览的页面序