7.6 基于源于关联规则挖掘概念的分类 • 3.CAEP（通过聚集显露模式分类）
• CAEP如何使用EP建立分类法？ • 在对一个新样本X分类时，对于每个类C，对出现在X X C X 中的类C的EP的区分能力聚集，得到C的得分，然后 对得分规格化。具有最大规格化 最大规格化得分的类决定X的类 最大规格化 标号。
知识库： 知识库
– 等价关系集R中所有可能的关系对U的划分 – 表示为：K = (U, R) 下近似： 下近似：
P（X）
P X = {Y ∈ U / P : Y ⊆ X }
上近似： 上近似：
P X = {Y ∈ U / P : Y I X ≠ ∅ }
7.7.4 粗糙集方法
U U1 U2 U3 U4 U5 U6 U7 U8 Headache Yes Yes Yes No No No No No Temp. Normal High Very-high Normal High Very-high High Very-high Flu No Yes Yes No No Yes Yes No
待分类案例 NO 基于案例的推理
训练样本集： 训练样本集：CBR存放 的样本或“案例”是复 杂的符号描述 符号描述。 符号描述 分类:（ 分类 （见右图)概念上 讲，这些训练案例可以 视为新案例的邻接者。
找到 NO YES 返回类似案例 返回该案例的解
7.7.3 遗传算法
1.编码与解码 2.适应度函数3.遗传操作 局限：初始值选择，交叉、变异概率选择 局限
7.7.3 遗传算法
• 用于分类： • 创建一个由随机产生的规则组成的初始群体 • 例如，规则“IF NOT A1 AND NOT A2 THEN C1”可 以用“001”编码。如果一个属性具有k（k>2）个值， 则可以用k个二进位对该属性的值编码。类可以用类 似的形式编码。 • 根据适者生存的原则，形成由当前群体中最适合的规 则组成新的群体，以及这些规则的子女。 • 典型地，规则的适合度（适应度函数）用它对训练样 适合度（ 适合度 适应度函数） 本集的分类准确率评估。
7.6 基于源于关联规则挖掘概念的分类
例如： Coundset={a1，a2，a3，a4} 2.关联分类 y=C 挖掘高支持度和高置信度的规则 （1）找出所有频繁的，精确地可能规则（PR）集合 找出所有频繁的， 找出所有频繁的 精确地可能规则（ ）集合。 算法使用迭代方法，类似于6.2.1小节介绍的Apriori 使用的方法，先验知识用于裁减规则搜索。 （2）使用一种启发式方法构造分类 使用一种启发式方法构造分类。这里，发现的 使用一种启发式方法构造分类 规则根据支持度和置信度按递减的优先次序组织。 （3）对一个新的样本进行分类时，满足该样本的第一 个规则用于对它分类。分类法也包含省缺规则，它具 有最低的优先次序，用来为不被分类法中其它规则满 足的新样本指定一个省缺的类。
来表示元素
M称为隶属度空间 称为隶属度空间
µA
:
表示x属于模糊集 的程度或等级 表示 属于模糊集A的程度或等级 属于模糊集
A: 通常意义下的集合
M:{0，1}
靠近1，则表示 属于 的程度高， 属于A的程度高 靠近 ，则表示x属于 的程度高 值 µA ( x) 靠近0， 则表示x属于 属于A的程度低 靠近 ， 则表示 属于 的程度低，
age(X,”34”) ∧ income(X,”30K - 40K”) ⇒ buys(X,”high resolution TV”) (1) age(X,”35”) ∧ income(X,”30K - 40K”) ⇒ buys(X,”high resolution TV”) (2) age(X,”34”) ∧ income(X,”40K - 50K”) ⇒ buys(X,”high resolution TV”) (3) age(X,”35”) ∧ income(X,”40K - 50K”) ⇒ buys(X,”high resolution TV”) (4)
7.7.5 模糊集方法
• 模糊逻辑使用0.0和 1.0之间的真值表示 一个特定的值是一个 给定类成员的程度， 而不是用类或集合的 精确截断。因而，使 用模糊逻辑，我们可 以断言：在某种程度 某种程度 上，$49K的收入是高 的，尽管没有$50K的 收入高。
Thanks
7.6 基于源于关联规则挖掘概念的分类
• • • • • • 1.基于聚类挖掘关联规则 基于聚类挖掘关联规则 特点： 特点： 限制条件：ARCS的准确性与离散化程度有关 可扩展性：可 时间：相比之下，C4.5具有指数运行时间 空间：相比之下，C4.5要求整个数据库（乘以某个 因子）全部装入内存
7.6 基于源于关联规则挖掘概念的分类
7.6 基于源于关联规则挖掘概念的分类
• 基于关联规则分类 基于关联规则分类： （1）基于聚类挖掘关联规则（ARCS）： 量化关 基于聚类挖掘关联规则（ 基于聚类挖掘关联规则 ） 联规则挖掘和关联规则聚类 • （2）关联分类 关联分类：它挖掘形如“cond_set=>y”具有高 关联分类 支持度和高置信度的规则,这里y是一个类标号 • 挖掘关联规则使用的支持度概念分类 挖掘关联规则使用的支持度概念分类： • （3）通过聚集显露模式分类（ CAEP ） 通过聚集显露模式分类（ 通过聚集显露模式分类 • 基于最小支持度和增长率挖掘显露模式（Eps）
7.7.1 k-最临近分类 最临近分类
分类： 分类：通过K个“近邻”的训练样本对此未知样本进行分 类。 • 针对连续值，返回计算k个最近邻居的平均值 • 针对离散值，返回最近的k个训练样例的最公共的值
局限：分类时需要很高的计算ห้องสมุดไป่ตู้销。因此，需要有效 局限 的牵引技术。
7.7.2 基于案例的推理（case-based 基于案例的推理（ reasoning CBR） ）
训练样本集： 维空间向量 训练样本集：n维空间向量 近邻：k-最临近分类法搜索n维空间，找出最接近 近邻 未知样本的k个训练样本。这k个训练样本是未知样 本的k个“近邻”。 搜索方法 欧几里德距离 搜索方法：欧几里德距离 方法 最近的邻居是用欧几里德距离定义的.其中，两个 点X=(x1,x2,...,xn)和Y=(y1,y2,...,yn)的欧几里德距 离是：
由R = {Headache, Temp.}
划分出来的等价类有: {u1}, {u2}, {u3}, {u4}, {u5, u7}, {u6, u8}. •下近似 下近似由一些这样的 下近似 数据样本组成，根据 关于属性的知识，它 们毫无疑问属于C。 •上近似 上近似由所有这样的 上近似 样本组成，根据关于 属性的知识，它们不 可能被认为不属于C
制作者： 制作者：张华 杜玉锋 2012.04.16
7.6基于源于关联规则挖掘概念的分类 基于源于关联规则挖掘概念的分类 7.7其它分类方法 其它分类方法 -7.7.1 k-最临近分类 最临近分类 -7.7.2基于案例的推理 基于案例的推理 -7.7.3遗传算法 遗传算法 -7.7.4粗糙集方法 粗糙集方法 -7.7.5模糊集方法 模糊集方法
7.7.5 模糊集方法
模糊集概念： 模糊集概念：
为空间， 以来表示， 设X为空间，空间中的点或元素 X 以来表示，即: 为空间
模糊集A是一个集合， 模糊集 是一个集合，是由隶属度 是一个集合 是否所属于模糊集A的特征。 是否所属于模糊集 的特征。即： 的特征 这样的函数，若 µ 这样的函数 若： A ∈ M , x ∈ A, 总有： X → M 总有
X1 = {u | Flu(u) = yes} = {u2, u3, u6, u7} RX1 = {u2, u3}
R X1 = {u2, u3, u6, u7, u5, u8}
7.7.4 粗糙集方法
• 分类中的应用：发现 分类中的应用： 不准确数据或噪音数 据内在的结构联系。 • 范围：它只用于离散 范围 离散 值属性。因此，连续 值属性必须在处理前 离散化。 • 粗糙集主要用于特征 规约
7.7.5 模糊集方法
• 应用 应用：对于连续属性，它们有陡峭的截断。模糊集在 应用中解决这类问题。 • 例子：IF（year_employed>=2） ∧(income>=50K)THEN credit=“approved”(7.21) 根据规则(7.21)，一个至少工作两年的顾客将得到信 用卡，如果他的收入是$50K；但是，如果他的收入是 $49K，他将得不到。这种苛刻的阈值看来可能不公平。 替换地，可以将模糊逻辑引入系统，允许定义“模糊” 阈值或边界。
7.6基于源于关联规则挖掘概念的分 基于源于关联规则挖掘概念的分 类 7.7其它分类方法 其它分类方法 -7.7.1 k-最临近分类 最临近分类 -7.7.2基于案例的推理 基于案例的推理 -7.7.3遗传算法 遗传算法 -7.7.4粗糙集方法 粗糙集方法 -7.7.5模糊集方法 模糊集方法
7.7.1 k-最临近分类 最临近分类
7.6 基于源于关联规则挖掘概念的分类
• 1.基于聚类挖掘关联规则（ARCS） 基于聚类挖掘关联规则（ 基于聚类挖掘关联规则 ） • （1）ARCS挖掘形如Aquant1∧Aquant2=>Acat的 关联规则 • （2）用ARCS产生的聚类关联规则用于分类
age(X,”34-35”) ∧ income(X,”30K - 50K”) ⇒ buys(X,”high resolution TV”) (5)
2.关联分类： 挖掘高支持度和高置信度的规则 关联分类： 关联分类 • 概念： • 挖掘形如condset=>y的规则；其中，condset 是 项（或属性值对）的集合，而y是类标号 • 满足最小支持度的规则是频繁的 频繁的 • 满足最小置信度的规则是精确的 精确的 • 如果一个规则项集具有相同的condset，则选择具 最高置信度的规则作为可能规则（PR），代表该 可能规则（ ） 有最高置信度 最高置信度 可能规则 集合