RIpple-DOwn Rule算法简介

RIpple-DOwn Rule算法（链波下降规则）是一种专家系统方法论，它是澳大利亚新南威尔士大学的Compton教授于1989年提出。它是一种用于知识表示和获取的方法。从某种意义上看RDR算法是CBR方法的一种扩展或者变形，RDR将规则引入CBR中，用规则来索引案例，以错误驱动机制来获取知识。

RIpple-DOwn Rule算法是比较简单，有时候得出的结果不能让人满意，但是它是我最喜欢的一种算法，它通过否定规则来表示结果，非常适合人类理解。

RIpple-DOwn Rule算法流程

RIpple-DOwn Rule算法使用了二元决策树，区别于标准决策树，RDR用复合条款是来确定分支,同时这些条款不需要详尽涵盖所有情况,即可以有分类错误的情况，然后用错误的数据作为新整体再处理，以获得内部分支。

为了方便说明，我们先看一个RDR的输出

这是一个医学诊断系统的涟波规则。

我们还是以weather.arff的数据为例。

看一下我们的分类要求，要分成no和yes两类。

no 的权重是5，yes的权重是9。

由错误驱动生成第一条规则

play = no

很明显这条规则没有正确分类

总共14个样本，有9个被分类错了。

再来生成内规则。

生成过程就省略了…请参考本文最后的参考文献。第二条规则是

Except (humidity <= 82.5) => play = yes

序号为6的数据被错误分类为play了.最终的规则是

play = no

           Except (humidity <= …

OneR算法简介

OneR又称1-R，是1993出现的一种极为简单的分类算法模型，它可以产生一个单层的决策树。

OneR算法是一个简单、廉价的方法，但是常常能够获得一个非常好的结果，用于描述数据中的结构。

OneR算法的使用非常广泛，可以简单的得到一个对数据的概括性了解，有时候甚至可以直接获得结果。

OneR算法实现

OneR的思路很简单，建立一个只针对于单个属性进行测试的规则，并进行不同的分支。每个分支对应的不同属性值。

分支的类就是原始数据（训练数据）在这个分支上出现最多的类。

每一个属性都会产生一个不同的规则集，每条规则对应这个属性的每个值。对每个属性值的规则集的误差率进行评估，选择效果最好的一个即可。

伪代码表述：

对于每个属性

  对于这个属性的每个属性值，建立如下规则

    计算每个类别出现的频率

    找出出现最频繁的类别

    建立规则，将这个类别赋予这个属性值

  计算规则的误差率

选择误差率最小的规则

一个简单的例子，数据使用weka自带的weather数据集。

针对每个属性，一共有5个，其中最后一个是我们希望输出的结果，所以只有4个属性值。即outlook、temperature、humidity、windy。

我们先计算outlook属性，它有3个属性值，sunny、rainy、overcast。

针对属性值sunny而言，一共有5条数据。

其中对应play为no的有3条、对应play为yes的有2条，为no的最频繁，所以给sunny赋值为no。

同理对于rainy而言，有5条记录。

其中对应play为yes的有3条、对应play为no的有2条，为yes的最频繁，所以给rainy赋值为yes。

同理计算overcast属性值，赋值为yes。

然后计算误差率

sunny—>no 中有3个分类正确，2个分类错误，误差0.4

rainy—>yes 误差为0.4

overcast—>yes 误差为0

outlook总误差4/14…

上一篇介绍了arff格式，这是weka专有格式，一般情况需要我们从其他数据源抽取或者获得。weka支持从cvs转化，也可以从数据库中抽取，界面如下图

weka安装目录有一个data目录，里面有一些测试数据，可以用于测试和学习。

导入了数据仅仅是一个开始，我们还需要对数据进行预处理。

数据预处理（data preprocessing）

数据预处理（data preprocessing）是指在主要的处理以前对数据进行的一些处理。

现实世界中数据大体上都是不完整，不一致的脏数据，无法直接进行数据挖掘，或挖掘结果差强人意。

为了提高数据挖掘的质量产生了数据预处理技术。

数据预处理有多种方法：数据清理，数据集成，数据变换，数据归约等。这些数据处理技术在数据挖掘之前使用，大大提高了数据挖掘模式的质量，降低实际挖掘所需要的时间。

数据清理是使用比较频繁的，主要有：

(1)空缺值处理

目前最常用的方法是使用最可能的值填充空缺值，比如可以用回归、贝叶斯形式化方法工具或判定树归纳等确定空缺值．这类方法依靠现有的数据信息来推测空缺值，使空缺值有更大的机会保持与其他属性之间的联系。

还可以用一个全局常量替换空缺值、使用属性的平均值填充空缺值或将所有元组按某些属性分类，然后用同一类中属性的平均值填充空缺值．如果空缺值很多，这些方法可能误导挖掘结果。

(2)噪声数据处理

噪声是一个测量变量中的随机错误或偏差，包括错误的值或偏离期望的孤立点值。常用分箱、回归、计算机检查和人工检查结合、聚类等方法进行噪音处理。

数据变化主要使用平滑聚集，数据概化，规范化等手段使数据换为较利于数据挖掘的格式。

数据归约主要是为了压缩数据量，源数据可以用来得到数据集的归约表示，它接近于保持原数据的完整性，但数据量比原数据小得多．与非归约数据相比，在归约的数据上进行挖掘，所需的时间和内存资源更少，挖掘将更有效，并产生相同或几乎相同的分析结果。常用维归约、数据压缩、数值归约等方法实现。

Weka.Filters

weka.filters中包含了一些数据预处理的简单实现（其实已经够用了），主要分成两大类，监督过滤（UnsupervisedFilter）和非监督过滤（UnsupervisedFilter）。

如果是使用GUI的话，点击Filter的Choose就可以选择

选择完成后点击选择的Filter本身就可以修改相关参数。

完成参数修正后点击Apply就Ok了。

我平时使用的比较多的还是非监督过滤，下面介绍一些比较常见。

先介绍weka.filters.unsupervised.attribute包下的，这是非监督方法对属性进行预处理。

1.Add

为数据库添加一个新的属性，新的属性将会包含所有缺失值。可选参数：

attributeIndex：属性位置，从1开始算，last是最后一个，first是第一个

attributeName：属性名称

attributeType：属性类型，一般是4选1

dateFormat：数据格式，参考ISO-8601

nominalLabels：名义标签，多个值用逗号隔开

2.AddExpression

新增一个属性，该属性由现有属性通过设定的表达式计算得出。支持+, -, *, /, ^, …

我个人认为直接讨论数据挖掘算法和weka的使用过于心急。我一开始就直接学习的数据挖掘方法，有些方法艰涩枯燥，我常常在思考的不是方法本身，而是“这是干什么的？”。

在使用了weka后有些东西渐渐清晰，因为输入和输出给了人很直观的感觉，再结合技术本身学习效率很高。

输入主要有三类：概念、实例和属性。

概念

概念简单而言就是需要被处理的东西。它可以是分类学习中那个已经分类完成的样本集。

你需要处理的东西可能差别很大，但你可以统称它们为概念，而输出就是对其的描述，即概念描述。

实例

实例这个词你可能觉得陌生，但是你可以大致认为其为样本。

我们通常的输入是一个实例集，其中的每一个实例都是单一、独立的概念样本。

当然最常见的实例表现方式就是表格：

不过这是因为如此，有人戏称数据挖掘应该成为文件挖掘。

诚然，关系型数据库可以表现更为复杂的关系，但有限关系的有限集一般都可以转化为单个表。有兴趣深入看看的朋友可以看一下有关反向规格化的虚假事实问题。

属性

如果上面说到的实例是表格中的一行的话，属性就是数据表中的一列。

一个特定实例的一个属性值是属性对应部分的一个测量或者观测值。

ARFF格式

arff格式是weka专用的文件格式，全称Attribute-Relation File Format。

它是一个ASCII文本文件，记录了一些共享属性的实例。arff格式是由怀卡托大学的计算机科学部门开发的。

arff格式文件主要由两个部分构成，头部定义和数据区。

头部定义包含了关系名称（relation name）、一些属性（attributes）和对应的类型，如：

%1.Title:IrisPlantsDatabase %
%2.Sources: %
(a)Creator:R.A.Fisher %
(b)Donor:MichaelMarshall (MARSHALL%[email protected]) %
(c)Date:July,1988 %@RELATION iris@ATTRIBUTE sepallengthNUMERIC@ATTRIBUTE sepalwidthNUMERIC@ATTRIBUTE petallengthNUMERIC@ATTRIBUTE petalwidthNUMERIC@ATTRIBUTEclass {Iris-setosa,Iris-versicolor,Iris-virginica}