Data-Method-01规则学习没有规范，没有标准，就成不了事。数据系列：目录｜配置｜代码仓库｜对应实战《数据挖掘导论》第五章，《机器学习》15章节。作为“符号学习”的主要代表，规则学习是最早开始研究的机器学习技术之一。把它作为方法的开始是很有意义的。1、Rule（规则）【基本概念】Rule（规则）：语义清晰，能够描述数据分布所隐含的客观规律或领域概念，可以表示为“如果……，然后...”。规则可以写成：$f_1\wedgef_2\wedge...\wedgef_L\rightarrow\oplus$例如，$r_i:(viviparous=no)\wedge(flyinganimal=yes)\rightarrowbird$$f_1\wedgef_2\wedge...\wedgef_L$：规则体、规则前提、前提条件，是由逻辑$f_k$组成的合取词。$\oplus$：规则头（head），规则后件（ruleconsequent），表示预测结果，即目标类别或概念。$L$：逻辑字符的个数，称为规则的长度。【规则的分类】从形式语言表达能力的角度，规则可以分为“命题规则”和“一阶规则”。命题规则：由原子命题（propositionalatom）和逻辑连词（带$\wedge$，或$\vee$，不带$\neg$，暗示$\leftarrow$）组成的简单描述性句子，如$rule1:Goodmelon\leftarrow(root=curl)\wedge(umbilical=sag)$在类似$root=curl$的等式中，判断两个逻辑词的评价。一阶规则：由能够描述事物的属性或关系的“原子公式”组成，可以表示复杂的关系。它们也被称为“关系规则”并具有表示关系的谓词，如$father(X,Y)$,$\sigma(X)=X+1$,$naturalnumber(X)$;用于限制变量取值范围的量词，如$\forall$和$\exists$；示例：$rule:goodmelon(X)\leftarrowroot(X,curled)\wedgenavel(X,sag)$命题规则是一阶规则的特例。【规则的质量】规则的质量可以用覆盖率和准确率来衡量。有数据集$D$和规则$r:A\rightarrowy$覆盖率：触发规则$在$D$条记录中的比例，$Coverage(r)=|A|/|D|$准确率：规则$r$触发的记录比例正确，$Accuracy(r)=|A\cupy|/|A|$2。规则集【基本概念】对于一个模型中的每一个规则/析取项$r_i$，都有一个规则集$R=(r_1\veer_2\vee...\veer_k)$。【两个重要的属性】规则集有两个重要的属性，互斥规则和穷举规则（不一定满足）。互斥规则：如果规则集中没有两条规则被同一条记录触发，则称规则集中的规则是互斥的，这确保了每条记录最多被规则集中的一条规则覆盖。穷举规则：对于数据集中的任意一条记录，都有一条规则覆盖它，则规则集具有穷举覆盖，保证每条记录至少被规则集中的一条规则所覆盖。【冲突与解决】如果规则集不互斥，一条记录可能被多个规则覆盖，这些规则的预测结果会发生冲突。解决冲突的方法称为冲突解决，常用的方法有投票法、排序法和元规则法。投票方式：以最受歧视的结果为最终结果。学习过程是一个无序的规则。优点：不易受规则选择不当造成的误差影响，建立模型的成本相对较小。inferior：将测试记录的属性与每条规则的前因进行比较，所以模型采用Prediction-timecost-intensivesortingmethod：定义规则集上的顺序，当有时选择最先排序的规则冲突。学习过程称为有序规则或优先规则。有序的规则集也称为决策列表。排序可以是基于规则的，也可以是基于类的，大多数基于规则的分类器都是基于规则的类排序：按照规则的某种度量进行排序，保证每条记录都被那个“最佳规则”分类覆盖，但可能会导致等级越低的法则，越难领悟；class-based：属于同一个预测结果的规则被排序在一起，即按类排序，这样更容易理解规则，但可能导致属于较高级别的类的质量较差的规则。元规则方法：根据领域知识，设置一些元规则，即规则的规则（例如“发生冲突时使用长度最小的规则”）【默认规则】规则集可能没有涵盖所有这时候一般会设置一个默认规则（defaultrule）或者默认规则（比如“没有被规则1和2涵盖的都不是好瓜”）。3.规则学习【基本概念】规则学习（rulelearning）：从训练数据中学习到一组规则，可以用来判别看不见的例子。规则学习的目标：生成一个能覆盖尽可能多的例子的规则集。规则学习的学习过程：寻找最优的逻辑词集合构成规则体是一个搜索问题，本质上是一个贪心搜索过程，因此需要降低过拟合的风险。常用的方法是修剪。.【规则抽取】规则抽取最直接的方法是顺序覆盖（sequentialcovering），即逐项归纳：从训练集中学习一个“好的”规则（覆盖较多的正例，没有或很少反面例子）；集中删除此规则涵盖的样本，并对其余样本重复此操作。一次只处理一部分数据，也称为“分而治之”策略。规则提取也可以使用间接的方法，比如从决策树生成规则集，如下图（来自《数据挖掘导论》）和决策树，可以剪枝；规则的排序可以使用C4.5规则算法。[规则生成]基于穷举搜索的方法在属性和候选项较多时可能会造成组合爆炸，因此需要一种策略来生成规则。通常有两种策略，自上而下和自下而上。自上而下（top-down）从更通用的规则开始，逐渐添加新的连词来缩小规则的覆盖范围，直到满足终止条件（例如，添加连词不能提高规则的质量）。也称为“生成然后测试”方法，规则逐渐“专业化”。更容易生成具有更好泛化性能和对噪声更鲁棒的规则。Bottom-up从比较特殊的规则开始，逐步删除关联项，扩大规则的覆盖范围，直到满足终止条件。也称为“数据驱动”方法，规则逐渐“通用化”。更适用于训练样本较少的情况。自上而下策略常用于命题规则学习，自下而上策略更多用于一阶规则学习等非常复杂的假设空间。另外，如果每次只增加或减少一次连接数，会过于贪心，容易陷入局部最优。因此，可以采用beamsearch等方法来缓解（每轮保留$b$组合取公式，下一轮用于构建候选集）。[规则评估]我们通过考虑规则的准确性、覆盖率和属性顺序来评估添加或减去规则的优缺点。此外，似然比、FOIL信息增益等也可以用来衡量加减conjunction后规则的质量是否更好。${\rmFOIL}信息增益=p_1\times(\log_2\frac{p_1}{p_1+n_1}-\log_2\frac{p_0}{p_0+n_0})$其中，$p$和$n$分别表示正类和负类的个数。当然这里的measurement和decisiontree有很多相似之处，decisiontree的evaluation可以借鉴。【规则剪枝】为了减轻过拟合的风险，可以使用剪枝的方法，可以是post-pruning，也可以是pre-pruning。CN2算法：借助统计显着性检验进行剪枝，使用LikelihoodRatioStatistics(LRS)测得${\rmLRS}=2\cdot(\hatm_+\log_2\frac{(\frac{\hatm_+}{\hatm_++\hatm_-})}{(\frac{m_+}{m_++m_-})}+\hatm_-\log_2\frac{(\frac{\hatm_-}{\hatm_++\hatm_-})}{(\frac{m_-}{m_++m_-})})$REP剪枝（ReducedErrorPruning，减错剪枝）：分为训练集和验证集，进行多轮剪枝，每轮穷举剪枝操作，使用验证机进行评估，保留最佳规则集进行下一轮剪枝，直到性能不能再提升。IREP剪枝（IncrementalREP）：划分训练集和测试集，在训练集上生成规则$r$，立即对验证集进行REP剪枝，得到规则$r'$，覆盖规则$r'$删除并重复REP修剪。与REP的$O(m^4)$复杂度相比，IREP的复杂度为$O(m\log^2m)$。RIPPER算法：将IREP使用的准确率替换为$\frac{\hatm_++(m_--\hatm_-)}{m_++m_-}$作为规则性能衡量指标，删除尾部剪枝时的规则对于多个文本，在得到最终的规则集后进行一次IREP剪枝。替换规则：根据$r_i$覆盖的样本，使用IREP*重新生成规则$r_i'$。修改后的规则：特化$r_i$的新增文本，然后通过IREP*剪枝生成规则$r_i''$。【特点与优势】与神经网络、支持向量机等“黑盒模型”相比，规则学习具有更好的可解释性，更容易理解；数理逻辑具有很强的表达能力，规则学习可以更自然地在学习过程中引入领域知识；逻辑规则具有抽象描述能力，规则学习在处理一些高度复杂的AI任务时具有显着优势；许多基于规则的分类器采用的基于类的规则排序方法适用于处理类分布不平衡的数据集。4.一阶规则学习与归纳逻辑规划【一阶规则学习】命题规则学习很难处理对象之间的关系，比如“瓜1比瓜2黑，所以瓜1比瓜2好”"，所以需要用一阶逻辑来表示，用一阶规则来学习。一阶规则学习可以更容易地引入领域知识。FOIL（First-OrderInductiveLearner）是一种著名的一阶规则学习算法。它遵循顺序覆盖框架，采用自上而下的规则归纳策略，使用FOIL增益（FOILgain）来选择文本。${\rmFOIL}Informationgain=p_1\times(\log_2\frac{p_1}{p_1+n_1}-\log_2\frac{p_0}{p_0+n_0})$只考虑正例的信息量，并使用新规则覆盖的正例数作为权重，因为关系数据中正例数往往远少于负例数。FOIL可以粗略地看作是命题规则学习和归纳逻辑编程之间的过渡。【归纳逻辑编程】归纳逻辑编程（ILP）在一阶规则学习中引入函数嵌套和逻辑表达式。机器学习系统具有更强大的表达能力，可以看作是利用机器学习技术解决基于背景知识的逻辑程序归纳，学习到的规则可以直接被PROLOG等逻辑编程语言使用。另一方面，嵌套函数和逻辑表达式的引入也使计算复杂化。最小泛化归纳逻辑程序设计采用自下而上的规则生成策略，直接将一个或多个正例对应的扎根事实作为初始规则，逐步泛化规则以增加覆盖率。泛化可以用逻辑变量替换规则中的常量，或者删除规则主体中的文字。LeastGeneralGeneralization(LGG)：最基本的特化规则RLGG（RelativeLeastGeneralization）：计算LGG时考虑所有背景知识，将初始规则$e\leftarrowK$定位，$K$为原子的合取背景知识。逆分解：根据背景知识发明新的概念和关系$p\leftarrowq$等价于$p\vee\negq$四种逆分解操作吸收（absorption）：$\frac{p\leftarrowA\wedgeB\quadq\leftarrowA}{p\leftarrowq\wedgeB\quadq\leftarrowA}$识别（identifictaion）：$\frac{p\leftarrowA\wedgeB\quadp\leftarrowA\wedgeq}{q\leftarrowB\quadp\leftarrowA\wedgeq}$内部结构：$\frac{p\leftarrowA\wedgeB\quadp\leftarrowA\wedgeC}{q\leftarrowB\quadp\leftarrowA\wedgeq\quadq\leftarrowC}$结构间：$\frac{p\leftarrowA\wedgeB\quadq\leftarrowA\wedgeC}{p\leftarrowr\wedgeB\quadr\leftarrowA\quadq\leftarrowr\wedgeC}$Substitution：用一些项来替换逻辑表达式中的变量。统一：使用一个逆解析的一大特点是它可以自动发明新的谓词。参考文献《数据挖掘导论》Chapter5《机器学习》Chapter15
