度阈值[3 ] 。
二 、关联规则算法
Ap riori 算法是一种最有影响的挖掘布尔关联 规则频繁项集的算法 ,算法使用频繁项集性质的先 验知识 :即频繁项集的所有非空子集都必须也是频 繁的 ,算法由两个步骤组成 :频繁 K 项集记做 L K 。 (一) 连接步 为找 L K ,通过 L K- 1 与自己连接产生候选 K 项 集的集合 ,该候选项集的集合记作 CK 。设 l 1 和 l2 是 l K- 1 中的项集 。记号 li [ j ]表示 li 的第 j 项 。执行 连接 l K- 1 l K- 1 ,其中 l K- 1 的元素是可连接的 ,如果 它们前 ( k - 2) 个项相同 。连接 l1 和 l2 产生的结果项 集是 l1 [ 1 ]l1 [ 2 ] …l1 [ k - 1 ]l2 [ k - 1 ] 。 (二) 剪枝步 CK 是 L K 的超集 : 它的成员可以是也可以不是 频繁的 ,但所有的频繁 K 项集都包含在 CK 中 。扫 描数据库 , 确定 CK 中每个候选的计数 , 从而确定
计算 :
co nfidence ( A ] B ) = P ( A | B )
=
s
u
p sLeabharlann port_count ( A u pport_count
(
∪
A)
B)
其中 ,support_co unt (A ∪B) 是包含项集 A ∪
B 的事务数 ,suppo rt_co unt ( A) 是包含项集 A 的事
— 47 —
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved.
第 9 卷 第 1 期
福建医科大学学报 (社会科学版)
2007 年 3 月
分以上记为 1 ;80～90 分记为 2 ;80 分以下记为 3 。 将每门课程编号 :如 :细胞生物学记为 A ;有机 化学记为 B ;医用物理学记为 C ……。则 A1 表示 : 细胞生物学在 90 分以上 ;B2 表示 :有机化学在 80 ～90 分 ; C3 表示 : 医用物理学在 80 分以下 ……。 这样 ,学生成绩库被转换成包含多个项的表 。由于 姓名和学分与分析目标无关 ,也予以剔除 。使用一 个转换程序 ,将原始表转换成如下形式 (表 2) :
严 华等 :关联规则在学生成绩分析中的应用
关联规则才是有实际意义的 。关联规则挖掘即是
在已知数据库 D 中产生支持度与置信度分别大于 给定的阈值的所有关联规则 。
(二) 关联规则的挖掘步骤
关联规则的挖掘是一个两步的过程[2] : (1) 找出 所有频繁项集 。项的集合称为项集 ,包含 K 个项的 项集称为 K 项集 。项集的出现频率是包含项集的 事务数 ,又称为支持度计数 。满足最小支持计数的 项集称为频繁项集 ; (2) 由频繁项集产生强关联规 则 ,这些规则必须满足最小支持度和最小置信度 。 一旦由数据库 D 中的事务找出频繁项集 ,由它 们产生强 关 联 规 则 是 很 容 易 的 。置 信 度 用 下 式
务数 。根据该式 ,关联规则可以产生 : (1) 对于每个
频繁项集 l ,产生 l 的所有非空子集 ; (2) 对于 l 的每
个非空 子 集
s
,如果
s u p port_count ( l) s u pport_count ( s)
≥min _ co nf ,
则输出规则 s ] (l - s) 。其中 min_co nf 是最小置信
随着计算机存储技术的飞速发展 ,各行各业都 收集了大量的数据 。但如果缺乏有效的分析工具 , 这些数据往往难得再被人们访问和利用 。如何从 这些数据中发现潜在的知识 ,日渐成为人们感兴趣 的话题 。数据挖掘是指从大量的数据中提取有用 的知识 ,在许多应用领域显示出巨大的潜力 。目前 常用的数据挖掘方法有 : 关联规则分析 、序列模式 分析 、分类分析 、聚类等 。 学习是一个循序渐进的过程 ,其与课程之间有 一定的关联和前后顺序关系 。如果基础课程没有 学好 ,肯定会影响到后续专业课程的学习 。但哪些 课程会影响到后续课程 ,以及哪些课程联系密切 , 还没有一种量化的分析 。此外 ,每学期安排课程的 多少 ,也会影响学生的学习效果 。本文使用关联规 则算法 ,对医科大学临床本科的学生成绩进行分 析 。通过对考试成绩进行挖掘分析 ,发现有几门课 程与将来专业课的成绩密切相关 ,教师可以应用这 些知识指导学生 ,如重要的基础课应安排较多的时 间 ,从而为将来专业课的学习打好基础 ; 针对关联 度较小的课程安排适当的时间 ,以便学生有效地安 排好自己的大学生活 。
(1. 福建医科大学 数理计算机教学部 ,福建 福州 350108 ;2. 福建医科大学 教务处 ,福建 福州 350108)
摘要 :采用关联规则的 ap riori 算法 ,对医科大学学生四年中各门课程的成绩进行分析 ,从而发现课程之间 的联系和基础课程对专业课程的影响 ,为教务部门安排课程提供参考 。 关键词 :数据挖掘 ;关联规则 ;成绩分析 中图分类号 :O29 文献标识码 :A 文章编号 :100924784 (2008) 0120046204
support (A ] B) = P (A ∪B) co nfidence (A ] B) = P (B| A) 支持度是对关联规则重要性的描述 ,而置信度 是对关联规则准确性的描述 。支持度高说明该关 联规则在所有事务中的代表性高 , 置信度高说明该 关联规则的可信度高 。有些关联规则置信度虽然 高 ,但是支持度低 ,说明该关联规则不具有代表性 。 为了挖掘出具有代表性的关联规则 , 规定了最小支 持度阈值和最小置信度阈值 , 只有支持度和置信度 都分别大于最小支持度阈值和最小置信度阈值的
第 9 卷 第 1 期 2008 年 3 月
福建医科大学学报 (社会科学版) Journal of Fujian Medical university (Social Science Editio n)
Vol. 9 ,No . 1 Mar. 2008
关联规则在学生成绩分析中的应用
严 华1 ,陈文菁2
表 1 学生成绩表
姓名
学号
陈 路 1100302001
王小玲 1100302002
…
…
细 胞 生物学
80 75 …
有机 化学
85 70 …
医 用 …
物理学
73
…
78 …
(一) 数据的整理 Ap rio ri 算法只能处理布尔变量 ,因此在应用算 法挖掘关联规则之前 , 需要先对原始数据进行处 理 ,把数值型数据转换为由项集组成的事务数据库 。 首先需要把关系数据库中的数值属性离散化 , 以便能应用到算法中 。离散的过程如下 :成绩在 90
收稿日期 :2008202228 作者简介 :严 华 (1967 - ) ,女 ,讲师 。
— 46 —
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved.
三 、利用关联规则算法分析成绩表
本文采用福建医科大学 2002 级临床本科学生 的成绩库 ,共 408 条数据 。原始表中包含了 4 年中 所有基础课和专业课 ,以及实习的成绩 。我们的目 的是要找出哪些基础课与专业课的成绩之间存在 较强的关联 ,有些无关的项可能会影响挖掘结果 。 因此 ,除去凭常识已知的与专业课程关联度不大的 课程 ,如政治经济学 、毛泽东思想等 。实习分用一 个总平均分表示 。经过筛选后 ,共选择 28 个课程作 为分析字段 ,部分数据显示如下 (表 1) 。
L K 。然而 CK可能很大 ,这样所涉及的计算量就很 大 。为了压缩 CK ,可以用散列技术 。 Ap rio ri 算法描述如下 : 输入 :交易数据库 D ,最小支持阈值 min_sup 输出 :D 中的频繁项集 L L1 = find_f requent_12itemset s (D) ; fo r ( k = 2 ; L K- 1 ≠ ; k + + ) { Ck = ap rio ri _ gen ( L K- 1 , min _ sup ) ;/ / 新 的 候 选集 for each t ransactio ns t ∈D {/ / 扫描 D 计数 Ct = subset (Ck ,t) ;/ / 事务 t 中包含的候选集 fo r each candidates c ∈Ct c. co unt + + ; } L k = {c ∈Ck | c. co unt Ε min_sup} } ret ur n L = ∪kL k
一 、关联规则的概念
若两个或多个变量取值之间存在某种规律性 , 就称为关联[1] 。最常见的关联规则是应用在超市购
物篮的分析 。通过数据分析可以了解顾客的购买 习惯 ,了解哪些商品频繁地被顾客同时购买 ,从而 帮助零售商有选择地安排货物 , 制定合理的销售 策略 。 (一) 基本概念 设 I = {i1 ,i2 , …im }是项的集合 ,设任务相关的 数据 D 是数据库事务的集合 ,其中每个事务 T 是项 的集合 ,使 T Α I。设 A 是一个项集 ,事务 T 包含 A 当且仅当 A Α T 。关联规则是形如 A ] B 的蕴涵 式 ,其中 A < I ,B < I ,并且 A ⌒B = 。规则 A ] B 在事务集 D 中成立 ,具有支持度 S ,其中 S 是 D 中 事务包含 A ∪B 的百分比 ,它是概率 P ( A ∪B) 。 规则 A ] B 在事务集中具有置信度 C ,如果 D 中包 含 A 的事务同时也包含 B 的百分比是 C。这是条 件概率 P (B| A)
表 2 离散化的数据
编号 细胞生物学 有机化学 医用物理学 …