《数据挖掘概念与技术》第七章高级模式挖掘

频繁模式挖掘是数据挖掘中频繁项挖掘的基本目标。
另外包括闭频繁项模式和极大频繁项模式。

除了挖掘基本的频繁项集和关联外，还可以挖掘高级的模式形式，本章中分别介绍了：

多层关联
多维关联
量化关联规则
稀有模式
负模式
高维模式
模式压缩和近似模式

多层关联

多层关联涉及多个抽象层中的数据。例如戴尔电脑可以抽象到电脑，而索尼耳机可以抽象到耳机。这些可以使用多个最小支持度阈值挖掘。
对于多层关联模式，阈值的选择：
可以使用相同的阈值来挖掘关联模式；也可以逐层降低来挖掘关联模式，避免丢掉更低层中的关联模式包含的信息；可以使用所有层中最小的阈值。

多层关联中的副作用是，由于项之间的“祖先”关系，可能产生一些多个抽象层上的冗余规则。例如

买电脑=>买惠普打印机（支持度8%，置信度70%） ——————（1.1）
买戴尔电脑=>买惠普打印机（支持度2%，置信度72%） ——————（1.2）

目前挖掘出了规则（1.1）和（1.2），那么这两个规则中，后一个子规则是有用的吗？
其中，电脑是戴尔电脑的“祖先”，规则（1.1）是规则（1.2）的“祖先”。
这里，给出一个冗余性定义：

规则R1是规则R2的祖先，如果R1能够通过将R2中的项用它在概念分层中的祖先替换得到，则R2冗余。
根据这个定义，一个规则被认为是冗余的，如果根据规则的祖先，它的支持度和置信度都接近于“期望值”。

在该例子中，规则（1.1）具有70%置信度和8%支持度，并且大约1/4的电脑是戴尔电脑（1/4为假设），那么我们可以期望规则（1.2）具有大约70%的置信度和2%（8%*1/4）的支持度，如果确实是这样，那么规则（1.2）不是有趣的，它不提供任何附加的信息，并且一般性不如它的祖先。

多维关联

多维关联包含多个维。挖掘这种关联的技术因如何处理重复谓词而异。
如规则
age(X,“20,…,29”) ^ occupation(X,“student”) => buy(X,“laptop”)
其中，age、occupation、buy均为谓词，涉及两个或多个维或谓词的关联规则称为多维关联规则。多维中维度不同，即具有不重复谓词，称为维间关联规则；具有重复谓词，则称为混合维关联规则。

方法：

使用预先定义的概念分层对量化属性离散化。使用量化属性的静态离散化挖掘多维关联规则。
年龄离散化为区间（20-30,30-40，…）
根据数据分布将量化属性离散化或聚类到“箱”。

在多维关联中，我们搜索频繁谓词集。不是搜索频繁项集。k-谓词集是包含k个合取谓词的集合。{age，occupation，buy}是一个3-谓词集。

量化关联

量化关联规则设计量化属性。
离散化、聚类和揭示异常行为的统计分析可以与模式挖掘过程集成在一起。

基于数据立方体挖掘
将变换后的多维数据构造数据立方体，进行数据挖掘。
基于聚类
自顶向下方法。

对于每个量化维，可以使用一种标准的聚类算法，发现该维上满足最小支持的阈值的簇。对于每个这样的簇，我们考察该簇与另一维的一个簇或标称属性值组合生成的二维空间，看这一组合是否满足最小支持度阈值。如果满足，继续考察更高维空间。在该过程中，我们可以使用先验剪枝，如果在任一点，组合的支持度不满足最小支持度，则它的进一步划分或与其他维组合也都不满足最小支持度。

这里对于划分不满足明白，但对于与其他维组合不满足不清楚。

使用统计学理论
即结果与现实经验不符。

稀有模式和负模式

稀有模式是很少出现但特别有趣。负模式是其成员呈现负相关行为的模式。
应该小心定义负模式，考虑零不变性。
稀有模式和负模式可能凸显数据的异常行为

零不变性

即值可能错误地被零事务影响，其中零事务是不包含被考察项集的任何项的事务。
这里有一个很有趣的例子。
当考虑事务的总量不同时，会有不一样的情况，定义7.3同理可证。

基于约束的挖掘

基于约束的挖掘策略可以用来引导挖掘过程，挖掘与用户直观一致或满足某些约束的模式，许多用户指定的约束都可以推进到挖掘过程中。
约束分为模式剪枝约束和数据剪枝约束。
这些约束的性质包括单调性、反单调性、简洁性、可变性、和数据反单调性。

其中，单调性基于满足性，而反单调性基于违反条件。如果某个单元违反某条件，则它的任何超集也将违反该条件，则称为反单调。
满足反单调的有：sum(S)<=v.
由于当前单元的和已经大于v，那么它的任何超集都无法满足小于等于v的条件。
单调的有：count(I)>10.
集合中的数量大于10，则进一步添加更多的商品到集合中会增加数量，也满足条件。
简洁性：是指该约束的集合可枚举。
可转变的约束：
约束avg(I.piece)<50.即价格的平均值不超过50，该约束既不是单调也不是反单调，但如果事务中的项以单价的递增顺序添加，则该约束就变成反单调的。

高维空间和模式融合

高维空间挖掘，为挖掘维数很大但元组很少的数据集的基于行枚举的模式增长方法，以及通过模式融合方法挖掘巨型模式。
（这个没太理解）

模式压缩和近似模式

为了减少挖掘返回的模式数量，我们可以代之以挖掘压缩模式或近似模式。
压缩模式可以通过基于聚类概念定义代表模式来挖掘，而近似模式可以通过提取感知冗余的top-k模式来挖掘。

模式压缩

通过在聚类簇中找到代表模式进行模式压缩。即模式压缩可以通过模式聚类实现。
闭模式是频繁模式集的无损压缩，而极大模式是有损压缩。
但使用闭项集和极大项集进行压缩的缺点是：
当数据集中没有闭项集，我们选择极大项集来代表该数据的压缩版本。但在之前我们已经知道，极大项集并不携带各项集的支持度信息，我们将失去整个支持度信息。
于是，我们提出，由于闭项集是原频繁模式集的无损压缩，我们在闭模式集合上发现代表模式。

这里提出，闭模式之间的距离度量计算。
设P1和P2是两个闭模式，他们的支持事务集分别为T（P1）和T(P2)。则P1和P2的模式距离为：
Pat_Dist(P1,P2)=1- (|T(P1)∩T(P2)|) / (|T(P1)∪T(P2)|)

模式距离是一种定义在事务集合上的有效距离度量。包含了模式的支持度信息。

例子：
假设P1、P2是两个模式，使得T(P1)={t1,t2,t3,t4,t5},T(P2)={t1,t2,t3,t4,t6}，其中ti是数据库中的事务。
那么P1和P2的距离为：
Pat_Dist(p1,p2)=1-|{t1,t2,t3,t4}|/|{t1,t2,t3,t4,t5,t6}| = 1 - 4/6 = 1/3

即：给定一个事务数据库，最小支持度min_sup，和聚类质量度量o，模式压缩问题及时找到一个代表模式的集合R，使得每个频繁模式P，存在一个代表模式Pr属于R，它覆盖P，并且|R|是最小化的。

感知冗余top-k模式

k个代表模式的小集合，它们不仅具有高显著性，而且相互之间低冗余。

在下图中，显著性用灰度表示，而球之间的距离越近，代表冗余度越高。假定现在要找的代表模式个数为3，即k=3.
图中箭头用来指示所选的模式，b为感知冗余的top-k模式选择的模式，c为传统top-k模式选择的模式，d为k-概括模式选择的模式。

很明显的看出，c中模式选择仅依赖显著性，从集合中选出显著性最高的三个模式，而不考虑冗余。
d中模式选择仅依赖非冗余性选择模式，先将集合划分为3簇，并发现最具代表性的模式是最靠近每个簇“中心”的模式。
而b中，在显著性和相关性之间进行平衡。

那么，显著性和冗余性该如何度量呢？

显著性度量

显著性度量S是一个函数，它把模式p∈P映射到一个实数值，使得S（p）是模式p的兴趣度（或有用性）。该度量可以是主观的也可以是客观的。S（p,q）是模式p和q的联合显著性，S（p|q）=S(p,q)-S(q)是给定q、p的相对显著性。
这里应该注意S(p,q)是两个模式的共同显著性。

冗余性

给定显著性度量S，两个模式p和q之间的冗余性R定义为R(p,q)=S§+S(q)-S(p,q)。
即有S(p|q) = S ( p) -R(p,q)。

假定两个模式的联合显著性不小于任何一个模式的显著性，并且不超过两个模式的显著性之和。也就是说两个模式之间的冗余应该满足：
（这里可以根据上面给出的公式自己推一推）
0≤R(p,q)≤min(S( p),S(q))
由于理想的冗余性度量R很难得到。我们可以使用模式间的距离来近似冗余度。该问题最终转换为发现最大化边缘显著性的k模式集问题。