23.txt

This complete matlab for neural network

每一个循环结束后，处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程
是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶
颈。其他的方法还有在多处理器之间共享一个杂凑树来产生频集。更多的关于生成频集的
并行化方法可以在[2,11,17]中找到。

2.         基于hash的方法。一个高效地产生频集的基于杂凑(hash)的算法由Park等[10
]提出来。通过实验我们可以发现寻找频集主要的计算是在生成频繁2-项集Lk上，Park等就
是利用了这个性质引入杂凑技术来改进产生频繁2-项集的方法。

3.         基于采样的方法。基于前一遍扫描得到的信息，对此仔细地作组合分析，可以
得到一个改进的算法，Mannila等[8]先考虑了这一点，他们认为采样是发现规则的一个有
效途径。随后又由Toivonen[16]进一步发展了这个思想，先使用从数据库中抽取出来的采
样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。To
ivonen的算法相当简单并显著地减少了I/O代价，但是一个很大的缺点就是产生的结果不精
确，即存在所谓的数据扭曲(data skew)。分布在同一页面上的数据时常是高度相关的，可
能不能表示整个数据库中模式的分布，由此而导致的是采样5%的交易数据所花费的代价可
能同扫描一遍数据库相近。Lin和Dunham在[7]中讨论了反扭曲(Anti-skew)算法来挖掘关联
规则，在那里他们引入的技术使得扫描数据库的次数少于2次，算法使用了一个采样处理来
收集有关数据的次数来减少扫描遍数。

Brin等[4]提出的算法使用比传统算法少的扫描遍数来发现频集，同时比基于采样的方法使
用更少的候选集，这些改进了算法在低层的效率。具体的考虑是，在计算k-项集时，一旦
我们认为某个(k+1)-项集可能是频集时，就并行地计算这个(k+1)-项集的支持度，算法需
要的总的扫描次数通常少于最大的频集的项数。这里他们也使用了杂凑技术，并提出产生
“相关规则”（Correlation Rules）的一个新方法，这是基于他们的[3]工作基础上的。

4.         减少交易的个数。减少用于未来扫描的事务集的大小。一个基本的原理就是当
一个事务不包含长度为k的大项集，则必然不包含长度为k+1的大项集。从而我们就可以将
这些事务移去，这样在下一遍的扫描中就可以要进行扫描的事务集的个数。这个就是Apri
oriTid的基本思想

 

3.2其他的频集挖掘方法
上面我们介绍的都是基于Apriori的频集方法。即使进行了优化，但是Apriori方法一些固
有的缺陷还是无法克服：

1)        可能产生大量的候选集。当长度为1的频集有10000个的时候，长度为2的候选集
个数将会超过10M。还有就是如果要生成一个很长的规则的时候，要产生的中间元素也是巨
大量的。

2)        无法对稀有信息进行分析。由于频集使用了参数minsup，所以就无法对小于mi
nsup的事件进行分析；而如果将minsup设成一个很低的值，那么算法的效率就成了一个很
难处理的问题。

下面将介绍两种方法，分别用于解决以上两个问题。

在[18]中提到了解决问题1的一种方法。采用了一种FP-growth的方法。他们采用了分而治
之的策略：在经过了第一次的扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-t
ree），同时依然保留其中的关联信息。随后我们再将FP-tree分化成一些条件库，每个库
和一个长度为1的频集相关。然后再对这些条件库分别进行挖掘。当原始数据量很大的时候
，也可以结合划分的方法,使得一个FP-tree可以放入主存中。实验表明，FP-growth对不同
长度的规则都有很好的适应性，同时在效率上较之apriori算法有巨大的提高。

第二个问题是基于这个的一个想法：apriori算法得出的关系都是频繁出现的，但是在实际
的应用中，我们可能需要寻找一些高度相关的元素，即使这些元素不是频繁出现的。在ap
riori算法中，起决定作用的是支持度，而我们现在将把可信度放在第一位，挖掘一些具有
非常高可信度的规则。在[19]中介绍了对于这个问题的一个解决方法。整个算法基本上分
成三个步骤：计算特征、生成候选集、过滤候选集。在三个步骤中，关键的地方就是在计
算特征时Hash方法的使用。在考虑方法的时候，有几个衡量好坏的指数：时空效率、错误
率和遗漏率。基本的方法有两类：Min_Hashing(MH)和Locality_Sensitive_Hashing(LSH)
。Min_Hashing的基本想法是：将一条记录中的头k个为1的字段的位置作为一个Hash函数。
Locality_Sentitive_Hashing的基本想法是：将整个数据库用一种基于概率的方法进行分
类，使得相似的列在一起的可能性更大，不相似的列在一起的可能性较小。我们再对这两
个方法比较一下。MH的遗漏率为零，错误率可以由k严格控制，但是时空效率相对的较差。
LSH的遗漏率和错误率是无法同时降低的，但是它的时空效率却相对的好很多。所以应该视
具体的情况而定。最后的实验数据也说明这种方法的确能产生一些有用的规则。

3.3多层和多维关联规则的挖掘
随着数据仓库和OLAP技术研究的深入，可以预见大量的数据将经过整合、预处理，从而存
入数据仓库之中。在当前，大多数的数据仓库的应用都是进行统计、建立多维以及OLAP的
分析工作。随着数据挖掘研究的深入，已经有了OLAP和数据挖掘相结合的方法[20,21]。

首先一个有效的数据挖掘方法应该可以进行探索性的数据分析。用户往往希望能在数据库
中穿行，选择各种相关的数据，在不同的细节层次上进行分析，以各种不同的形式呈现知
识。基于OLAP的挖掘就可以提供在不同数据集、不同的细节上的挖掘，可以进行切片、切
块、展开、过滤等各种对规则的操作。然后再加上一些可视化的工具，就能大大的提高数
据挖掘的灵活性和能力。接着，我们来看一下多层和多维关联规则的定义。

多层关联规则：

对于很多的应用来说，由于数据分布的分散性，所以很难在数据最细节的层次上发现一些
强关联规则。当我们引入概念层次后，就可以在较高的层次上进行挖掘。虽然较高层次上
得出的规则可能是更普通的信息，但是对于一个用户来说是普通的信息，对于另一个用户
却未必如此。所以数据挖掘应该提供这样一种在多个层次上进行挖掘的功能。

多层关联规则的分类：根据规则中涉及到的层次，多层关联规则可以分为同层关联规则和
层间关联规则。

多层关联规则的挖掘基本上可以沿用“支持度-可信度”的框架。不过，在支持度设置的问
题上有一些要考虑的东西。

同层关联规则可以采用两种支持度策略：

1)        统一的最小支持度。对于不同的层次，都使用同一个最小支持度。这样对于用
户和算法实现来说都比较的容易，但是弊端也是显然的。

2)        递减的最小支持度。每个层次都有不同的最小支持度，较低层次的最小支持度
相对较小。同时还可以利用上层挖掘得到的信息进行一些过滤的工作。

层间关联规则考虑最小支持度的时候，应该根据较低层次的最小支持度来定。

多维关联规则：

以上我们研究的基本上都是同一个字段的值之间的关系，比如用户购买的物品。用多维数
据库的语言就是单维或者叫维内的关联规则，这些规则一般都是在交易数据库中挖掘的。
但是对于多维数据库而言，还有一类多维的关联规则。例如：

年龄（X，“20...30”）Ù职业（X,“学生”）==> 购买(X，“笔记本电脑”)

在这里我们就涉及到三个维上的数据：年龄、职业、购买。

根据是否允许同一个维重复出现，可以又细分为维间的关联规则（不允许维重复出现）和
混合维关联规则（允许维在规则的左右同时出现）。

年龄（X，“20...30”）Ù购买(X，“笔记本电脑”) ==> 购买(X，“打印机”)

这个规则就是混合维关联规则。

在挖掘维间关联规则和混合维关联规则的时候，还要考虑不同的字段种类：种类型和数值
型。

对于种类型的字段，原先的算法都可以处理。而对于数值型的字段，需要进行一定的处理
之后才可以进行。处理数值型字段的方法基本上有以下几种：

1)        数值字段被分成一些预定义的层次结构。这些区间都是由用户预先定义的。得
出的规则也叫做静态数量关联规则。

2)        数值字段根据数据的分布分成了一些布尔字段。每个布尔字段都表示一个数值
字段的区间，落在其中则为1，反之为0。这种分法是动态的。得出的规则叫布尔数量关联
规则。

3)        数值字段被分成一些能体现它含义的区间。它考虑了数据之间的距离的因素。
得出的规则叫基于距离的关联规则。

4)        直接用数值字段中的原始数据进行分析。使用一些统计的方法对数值字段的值
进行分析，并且结合多层关联规则的概念，在多个层次之间进行比较从而得出一些有用的
规则。得出的规则叫多层数量关联规则。

在OLAP中挖掘多层、多维的关联规则是一个很自然的过程。因为OLAP本身的基础就是一个
多层多维分析的工具，只是在没有使用数据挖掘技术之前，OLAP只能做一些简单的统计，
而不能发现其中一些深层次的有关系的规则。当我们将OLAP和DataMining技术结合在一起
就形成了一个新的体系OLAM（On-Line Analytical Mining）[20]。

4关联规则价值衡量的方法
当我们用数据挖掘的算法得出了一些结果之后，数据挖掘系统如何知道哪些规则对于用户
来说是有用的、有价值的？这里有两个层面：用户主观的层面和系统客观的层面。

4.1系统客观层面：
很多的算法都使用“支持度-可信度”的框架。这样的结构有时会产生一些错误的结果。看
如下的一个例子：

假设一个提供早餐的零售商调查了4000名学生在早晨进行什么运动，得到的结果是2200名
学生打篮球，2750名学生晨跑，1800名学生打篮球、晨跑。那么如果设minsup为40%，min
conf为60%，我们可以得到如下的关联规则：

打篮球Þ晨跑                     （1）

这条规则其实是错误的，因为晨跑的学生的比例是68%，甚至大于60%。然而打篮球和晨跑
可能是否定关联的，即当我们考虑如下的关联时：

  打篮球Þ（不）晨跑   （2）

虽然这条规则的支持度和可信度都比那条蕴涵正向关联的规则（1）低，但是它更精确。 
          然而，如果我们把支持度和可信度设得足够低，那么我们将得到两条矛盾的规
则。但另一方面，如果我们把那些参数设得足够高，我们只能得到不精确的规则。总之，
没有一对支持度和可信度的组合可以产生完全正确的关联。

于是人们引入了兴趣度，用来修剪无趣的规则，即避免生成“错觉”的关联规则。一般一
条规则的兴趣度是在基于统计独立性假设下真正的强度与期望的强度之比，然而在许多应
用中已发现，只要人们仍把支持度作为最初的项集产生的主要决定因素，那么要么把支持
度设得足够低以使得不丢失任何有意义的规则，或者冒丢失一些重要规则的风险；对前一
种情形计算效率是个问题，而后一种情形则有可能丢失从用户观点来看是有意义的规则的
问题。

在[12]中作者给出了感兴趣的规则的定义（R-interesting），在[13]中他们又对此作了改
进。在[10]中把事件依赖性的统计定义扩展到兴趣度的定义上来；[15]定义了否定关联规
则的兴趣度。

除了把兴趣度作为修剪无价值规则的工具，现在已有许多其他的工作来重新认识项集，如
Brin等[3]考虑的相关规则。在[4]中讨论了蕴涵规则(implication rule)，规则的蕴涵强