《Web数据挖掘》读书笔记1


《Web数据挖掘》

第二章 关联规则和序列模式 2.1 基本概念      一个关联规则可以是如下形式的关系:      X→Y,其中X,Y属于项目集合。例如:牛肉,鸡肉→奶酪      支持度置信度是两个常用的衡量关联规则强度的指标。      支持度:X和Y所占的百分比,即P(X∪Y)      置信度:既包含X又包含Y占所有X的百分比,即P(X∪Y)/P(X)

2.2 Apriori算法      分两步进行:      1.生成所有频繁项目集:一个频繁项目集是一个支持度高于minsup的项目集      2.从频繁项目集中生成所有可信关联规则:一个可信关联规则是置信度大于minconf的规则      虽然算法的空间复杂度是指数级别的,但是它利用了数据的稀疏性和较高的最小支持度值来保证算法的可行性和高效性。还有,该算法不会把整个数据集一次性读入内存中,因此可以应用于规模巨大的数据集上。

2.3 关联规则挖掘的数据格式      关联规则挖掘也可以在关系数据表上进行,只需要先把表数据转换成事务数据。      如何转换:只需要将每个属性值转换成一个(属性,值)对。

2.4 多最小支持度的关联规则挖掘      不同项目之间的出现频率相差太大,最小支持度设置得太大或太小都会出现问题。      对于这个问题的一个常见解决方法是:将数据分成几个较小的块,每个块只包含那些出现频率比较相近的项目。      一个更好的方法是:让用户指定多个最小支持度阈值。

2.5 分类关联规则挖掘      X→y,其中X属于项目集合,y属于分类集合,且y只有一个项目。      例:      文档1:学生,学校→教育      文档2:球员,篮球→体育

2.6 序列模式的基本概念      关联规则挖掘不考虑事务间的顺序,然而很多应用中这样的顺序是很重要的。      序列:一个排过序的项集列表。例:<{3}{4,5}{8}>      基数:一个序列中项集的个数。例:上面序列基数为3      长度:一个序列中项目的个数。例:上面序列长度为4      序列模式:寻找满足某种顺序出现的数据。      算法:基于GSP的序列模式挖掘算法和PrefixSpan算法。(2.7和2.8节)

2.9 从序列模式中产生规则

  • 序列规则
  • 标签序列规则
  • 分类序列规则

第三章 监督学习 3.1 基本概念      监督学习又称为分类归纳学习。      每个数据集里的数据实例都有一组属性值,还有一个特殊的目标属性,称为类属性。      例:贷款申请。           四个属性:Age,Has_job, Own_howse, Credit_rating           一个类属性:是否被批准

3.2 决策树推理      思想:不断地分隔数据,以使最终分隔所得的各个子集尽可能的纯,即类属性尽可能一样。      算法:分治。当所有的当前节点的数据类属性一致时,递归结束。类属性不一样时,通过一个混杂度函数来选择最佳分类属性。      熵Entropy:公式 -∑PilogPi      例如D只有两个属性类      各占50%,则entropy(D) = -0.5log0.5 + -0.5log0.5 = 1      20%-80%,则entropy(D) = -0.2log0.2 + -0.8log0.8 = 0.722      100%-0%,则entropy(D) = -1log1 + -0*log0 = 0      可见,数据变得越来越纯净时,熵越来越小,最小值为0,二元情况下,各占50%时,熵取最大值1.      最流行的用于决策树学习的混杂度函数是信息增益(Information Gain)信息增益率(Information Gain Ratio).

3.3 评估分类器      主要的评估标准是分类精度(Accuracy).      评估方法:

  • Holdout集合
  • 多次随机采样
  • 交叉验证

3.4 规则推理

     方法:

  • 序列化覆盖:基本思想是序列化地学习一系列的规则。当一条规则产生或,把这条规则所覆盖的训练样例移除掉,然后使用剩下的训练样例继续寻找下一条规则。
  • 规则学习:在迭代选择中,贪心地选择最多样例满足的条件。

3.5 基于关联规则的分类

     三种使用关联规则进行分类的方法:

  • 直接使用类关联规则进行分类
  • 使用关联规则作为分类属性
  • 使用古典的关联规则进行分类

3.6-3.8 朴素贝叶斯分类&支持向量机      还有待深入学习,有兴趣者可以看看这篇博文《支持向量机通俗导论》