搜索
第七章分类和预测数据库内容丰富，蕴藏大量信息，可以用来作出智能的商务决策。分类和预测是两种数据分析形式，可以用于提取描述重要数据类的模型或预测未来的数据趋势。然而，分类是预测分类标号（或离散值），而预测建立连续值函数模型。例如，可以建立一个分类模型，对银行贷款的安全或风险进行分类；而可以建立预测模型，给定潜在顾客的收入和职业，预测他们在计算机设备上的花费。许多分类和预测方法已被机器学习、专家系统、统计和神经生物学方面的研究者提出。大部分算法是内存算法，通常假定数据量很小。最近的数据挖掘研究建立在这些工作之上，开发了可规模化的分类和预测技术，能够处理大的、驻留磁盘的数据。这些技术通常考虑并行和分布处理。本章，你将学习数据分类的基本技术，如判定树归纳、贝叶斯分类和贝叶斯网络、神经网络。数据仓库技术与分类的集成，以及基于关联的分类也在本章讨论。本章还介绍其它分类方法，如k-最临近分类、基于案例的推理、遗传算法、粗糙集和模糊逻辑技术。预测方法，包括线性的、非线性的、广义线性回归也将简要讨论。你将学会修改、扩充和优化这些技术，将它们应用到大型数据库的分类和预测。7.1什么是分类？什么是预测？数据分类是一个两步过程（图7.1）。第一步，建立一个模型，描述预定的数据类或概念集。通过分析由属性描述的数据库元组来构造模型。假定每个元组属于一个预定义的类，由一个称作类标号属性的属性确定。对于分类，数据元组也称作样本、实例或对象。为建立模型而被分析的数据元组形成训练数据集。训练数据集中的单个元组称作训练样本，并随机地由样本群选取。由于提供了每个训练样本的类标号，该步也称作有指导的学习（即，模型的学习在被告知每个训练样本属于哪个类的“指导”下进行）。它不同于无指导的学习（或聚类），那里每个训练样本的类标号是未知的，要学习的类集合或数量也可能事先不知道。聚类是第8章的主题。通常，学习模型用分类规则、判定树或数学公式的形式提供。例如，给定一个顾客信用信息的数据库，可以学习分类规则，根据他们的信誉度优或相当好来识别顾客（图7.1(a)）。该规则可以用来为以后的数据样本分类，也能对数据库的内容提供更好的理解。第二步（图7.1(b)），使用模型进行分类。首先评估模型（分类法）的预测准确率。本章的7.9节介绍评估分类准确率的多种方法。保持（holdout）方法是一种使用类标号样本测试集的简单方法。这些样本随机选取，并独立于训练样本。模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比。对于每个测试样本，将已知的类标号与该样本的学习模型类预测比较。注意，如果模型的准确率根据训练数据集评估，评估可能是乐观的，因为学习模型倾向于过分适合数据（即，它可能并入训练数据中某些异常，这些异常不出现在总体样本群中）。因此，使用测试集。如果认为模型的准确率可以接受，就可以用它对类标号未知的数据元组或对象进行分类。（这种数据在机器学习也称为“未知的”或“先前未见到的”数据）。例如，在图7.1(a)通过分析现有顾客数据学习得到的分类规则可以用来预测新的或未来顾客的信誉度。“预测和分类有何不同？”预测是构造和使用模型评估无标号样本，或评估给定样本可能具有的属性值或值区间。在这种观点下，分类和回归是两类主要预测问题；其中，分类是预测离散或标称值，而回归用于预测连续或有序值。然而，我们的观点是：预测类标号为分类，预测连续值（例如，使用回归方法）为预测。这种观点在数据挖掘界广泛接受。分类和预测具有广泛的应用，包括信誉证实、医疗诊断、性能预测和选择购物。图7.1数据分类过程：(a)学习：用分类算法分析训练数据。这里，类标号属性是credit_rating，学习模型或分类法以分类规则形式提供。(2)分类：测试数据用于评估分类规则的准确率。如果准确率是可以接受的，则规则用于新的数据元组分类例7.1假定我们有一个AllElectronics的邮寄清单数据库。邮寄清单用于分发介绍新产品和降价信息材料。数据库描述顾客的属性，如他们的姓名、年龄、收入、职业和信誉度。顾客可以按他们是否在AllElectronics购买计算机分类。假定新的顾客添加到数据库中，你想将新计算机的销售信息通知顾客。将促销材料分发给数据库中的每个新顾客的费用可能很高。一个更有效的方法是只给那些可能买新计算机的顾客寄材料。为此，可以构造和使用分类模型。另外，假定你想预测在一个财政年度，一个顾客将在AllElectronics进行的主要购买数量。由于预测的值是有序的，为此可以构造一个预测模型。7.2关于分类和预测的问题本节介绍分类和预测数据的预处理问题。分类方法的比较和评估标准也在本节介绍。7.2.1准备分类和预测数据可以对数据使用下面的预处理，以便提高分类和预测过程的准确性、有效性和可规模性。数据清理：是旨在消除或减少数据噪音（例如，使用平滑技术）和处理遗漏值（例如，用该属性最常出现的值，或根据统计，用最可能的值替换遗漏值）的数据预处理。尽管大部分分类算法都有处理噪音和遗漏值的机制，但该步骤有助于减少学习时的混乱。相关性分析：数据中许多属性可能与分类和预测任务不相关。例如，记录银行贷款星期几签署的数据可能与应用的成功不相关。此外，其它属性可能是冗余的。因此，可以进行相关分析，删除学习过程中不相关或冗余属性。在机器学习，这一过程称为特征选择。包含这些属性将减慢和误导学习步骤。理想地，用在相关分析上的时间，加上从“压缩的”结果子集上学习的时间，应当少于由原来的数据集合上学习所花的时间。因此，这种分析可以帮助提高分类的有效性和可规模性。数据变换：数据可以泛化到较高层概念。概念分层可以用于此目的。对于连续值属性，这一步非常有用。例如，属性income的数值值可以泛化为离散的区间，如low,medium和high。类似地，标称值，如street，可以泛化到高层概念，如city。由于泛化压缩了原来的训练数据，学习时的输入/输出操作将减少。数据也可以规范化，特别是在学习阶段使用神经网络或涉及距离度量的方法时。规范化涉及将属性的所有值按比例缩放，使得它们落入较小的指定区间，如-1.0到1.0，或0.0到1.0。例如，在使用距离度量的方法中，这可以防止具有较大初始域的属性（如income）相对于具有较小初始域的属性（如二进位属性）权重过大。数据清理、相关分析和数据变换已在本书的第3章详细介绍。相关分析还在第5章介绍过。7.2.2比较分类方法。分类和预测方法可以根据下列标准进行比较和评估：预测的准确率：这涉及模型正确地预测新的或先前未见过的数据的类标号的能力。速度：这涉及产生和使用模型的计算花费。强壮性：这涉及给定噪音数据或具有遗漏值的数据，模型正确预测的能力。可规模性：这涉及给定大量数据，有效地构造模型的能力。可解释性：这涉及学习模型提供的理解和洞察的层次。这些问题的讨论贯穿本章。数据库研究界对数据挖掘的分类和预测的贡献一直强调可规模性，特别是对判定树归纳。7.3用判定树归纳分类“什么是判定树？”判定树是一个类似于流程图的树结构；其中，每个内部结点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶结点代表类或类分布。树的最顶层结点是根结点。一棵典型的判定树如图7.2所示。它表示概念buys_computer，即，它预测AllElectronics的顾客是否可能购买计算机。内部结点用矩形表示，而树叶用椭圆表示。为了对未知的样本分类，样本的属性值在判定树上测试。路径由根到存放该样本预测的叶结点。判定树容易转换成分类规则。在7.3.1小节，我们介绍学习判定树的基本算法。在判定树构造时，许多分枝可能反映的是训练数据中的噪音或局外者。树剪枝试图检测和剪去这种分枝，以提高在未知数据上分类的准确性。树剪枝在7.3.2小节介绍。由判定树提取分类规则在7.3.3小节讨论。基本判定树算法的加强在7.3.4小节给出。大型数据库判定树归纳的可规模性问题在7.3.5小节讨论。7.3.6小节介绍判定树归纳与诸如数据方等数据仓库机制的集成，允许多个粒度层的判定树挖掘。判定树已在由医疗到游戏理论和商务等应用领域广泛使用。判定树是一些商业规则归纳系统的基础。图7.2概念buys_computer的判定树，指出AllElectronics的顾客是否可能购买计算机。每个内部（非树叶）结点表示一个属性上的测试，每个树叶结点代表一个类（buys_computer=yes,或buys_computer=no）算法：Generate_decision_tree。由给定的训练数据产生一棵判定树。输入：训练样本samples，由离散值属性表示；候选属性的集合attribute_list。输出：一棵判定树。方法：(1)创建结点N；(2)ifsamples都在同一个类Cthen(3)returnN作为叶结点，以类C标记；(4)ifattribut_list为空then(5)returnN作为叶结点，标记为samples中最普通的类；//majorityvoting(6)选择attribute_list中具有最高信息增益的属性test_attribute；(7)标记结点N为test_attribute；(8)foreachtest_attribute中的未知值ai//partitionthesamples(9)由结点N长出一个条件为test_attribute=ai的分枝；(10)设si是samples中test_attribute=ai的样本的集合；//apartition(11)ifsi为空then(12)加上一个树叶，标记为samples中最普通的类；(13)else加上一个由Generate_decision_tree(si,attribute_list–test_attribute)返回的结点；图7.3由训练样本归纳判定树的基本算法7.3.1判定树归纳判定树归纳的基本算法是贪心算法，它以自顶向下递归的划分-控制方式构造判定树。算法在图7.3中，是一种著名的判定树算法ID3版本。算法的扩展将在7.3.2到7.3.6小节讨论。算法的基本策略如下：树以代表训练样本的单个结点开始（步骤1）。如果样本都在同一个类，则该结点成为树叶，并用该类标号（步骤2和3）。否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最好地将样本分类的属性（步骤6）。该属性成为该结点的“测试”或“判定”属性（步骤7）。在算法的该版本中，所有的属性都是分类的，即离散值。连续属性必须离散化。对测试属性的每个已知的值，创建一个分枝，并据此划分样本（步骤8-10）。算法使用同样的过程，递归地形成每个划分上的样本判定树。一旦一个属性出现在一个结点上，就不必该结点的任何后代上考虑它（步骤13）。递归划分步骤仅当下列条件之一成立停止：(a)给定结点的所有样本属于同一类（步骤2和3）。(b)没有剩余属性可以用来进一步划分样本（步骤4）。在此情况下，使用多数表决（步骤5）。这涉及将给定的结点转换成树叶，并用样本中的多数所在的类标记它。替换地，可以存放结点样本的类分布。(c)分枝test_attribute=ai没有样本（步骤11）。在这种情况下，以samples中的多数类创建一个树叶（步骤12）。属性选择度量在树的每个结点上使用信息增益度量选择测试属性。这种度量称作属性选择度量或分裂的优劣度量。选择具有最高信息增益（或最大熵压缩）的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或“不纯性”。这种信息理论方法使得对一个对象分类所需的期望测试数目最小，并确保找到一棵简单的（但不必是最简单的）树。设S是s个数据样本的集合。假定类标号属性具有m个不同值，定义m个不同类Ci(i=1,...,m)。设si是类Ci中的样本数。对一个给定的样本分类所需的期望信息由下式给出：miiimppsssI1221)(log),...,,((7.1)其中，pi是任意样本属于Ci的概率，并用si/s估计。注意，对数函数以2为底，因为信息用二进