机器学习与数据挖掘复习

1、 /13机器学习与数据挖掘复习第一章：Introduction什么是数据挖掘：数据挖掘时从大量的数据中取出令人感兴趣的知识（令人感兴趣的知识：有效地、新颖的、潜在有用的和最终可以理解的）。数据挖掘的分类（从一般功能上的分类）：a）描述型数据挖掘（模式）：聚类，summarization,关联规则，序列发现。b）预测型数据挖掘（值）：分类，回归，时间序列分析，预测。KDD（数据库中的知识发现）的概念：KDD是一个选择和提取数据的过程，它能自动地发现新的、精确的、有用的模式以及现实世界现彖的模型。数据挖掘是KDD过程的一个主要的组成部分。用数据挖掘解决实际问题的大概步骤：a）对数据进行KDD过程的

2、处理来获取知识。b）用知识指导行动。c）评估得到的结果：好的话就循坏使用，不好的话分析、得到问题然后改进。KDD过程中的角色问题：DomainExpertsMiningSpecialistsssouonaDataAdministrator6UC一wEguo一一DomainExpertsMiningSpecialistsssouonaDataAdministrator6UC一wEguo一一saldjpu-Uo4glddau-ssouona6.整个KDD过程：a）合并多个数据源的数据。b）对数据进行选择和预处理。c）进行数据挖掘过程得到模式或者模型。d）对模型进行解释和评价得到知识。第二章数据和数

3、据预处理什么是数据：数据是数据对彖和它的属性的集合。一个属性是一个对象的性质或特性。属性的集合描述了一个对象。属性的类型：a）标称（nominal）：它的值仅仅是不同的名字，只是提供足够的信息来区分对彖。例如邮政编码、ID、性别。b）序数：序数属性的值提供足够的信息确定对象的序。例如硬度、成绩、街道号码。c）区间：对于区间属性，值之间的差是有意义的，即存在测量单位。例如口历口期、温度。d）比率：对于比率变量，差和比率都是有意义的。例如绝对温度、年龄、质量、长度。用值的个数描述属性：a）离散的：离散属性具有有限惑无限可数个值，这样的属性可以是分类的。b）连续的：连续属性是取实数值的属性。非对称属

4、性：对于非对称属性，出现非零属性值才是最重要的。数据集的类型：a）记录型数据：每一个数据对象都是有固定数目的属性组成的。数据矩阵：如果一个数据集中的所有数据对彖都具有相同的数值属性集，则数据对彖可以看做是多维空间中的点，其中每个位代表描述对象的一个不同属性。文档数据：每个文档看成是一个向量。爭务数据：每一个事务涉及一个项的集合。b）图数据：可以表示数据对彖河的关系或者是数据对象本身就是用图形表示。c）有序数据：属性在时间或者空间上有关系。时态数据：记录型数据的扩展，但是每个记录都有一个时间。序列数据：由数据构成的序列，没有时间，但表述了一个时间的先后顺序。时间序列数据：每个记录都是一个时间序列

5、。空间数据：属性和空间位置有关。噪声和离群点的区别：噪声是对原始值产生了修改：离群点是具有不同于数据集中其他人部分数据对彖的特征的数据对象，或是相对于该属性的典型值不寻常的属性值。如何处理噪声数据：a）分箱（binning）：分享方法通过考察数据的近邻来光滑有序数据的值。b）回归：可以用一个函数你和数据来光滑数据。c）聚类：将数据划分为不同的类，落在类之外的视为离群点。d）把计算机分析的结果让人检查看是否有问题。数据预处理中的主要任务：a）数据清洗：填补缺值、去除噪声、解决数据不一致、解决冗余。b）数据集成：将不同数据源的数据放在一个地方。c）数据转换：平滑处理、数据聚合、数据泛化、归一化、属

6、性特征构造。d）数据约减：减少数据量，但仍需从少量的数据中得到原有或接近原有的结果。e）数据离散化对给定连续值划分为若干小区间，每个区间用一个值表示。相关分析两类方法：对于数值属性可以通过计算两属性之间的相关系数。对于分类数据两属性之间的相关联系可以通过卡方来计算。对数据归一化处理的三大类方法：a）最小-最大规范化：.丫一wimz.、.v（new_hiaxa-new_nuna）+_mmamaxaminab）乙score规范化：tv_/LIAV=Cac）小数定标规范化：宀亠107属性约减的方法：a）回归：拟合函数。b）直方图：将数据划分为一定的区间，存储时只用存储其平均值。（等宽度、等深度、V-

7、optimal：取最优化分、MaxDiff：根据值间距离来划分）。c）聚类：将数据聚为不同的类，存储类中最有代表性的数据，例如中心点。d）抽样：从数据中抽取一个样本，要能代表原来的数据。数据离散化的方法：a）数值型：直方图：自上而下的划分。聚类的分析。基于爛的离散化。卡方分析。自然划分的方法。b）分类型数据：模式集。属性集。通过只可以得到层次的关系。根据不同属性的取值自动生成。计算二进制属性的相似性用SMC和Jaccard系数（也可以不用于二进制属性，也可用于连续和计数属性），Cosine相似性用来测文档和文档之间的距离。第三章概念学习概念的概念：a）概念是定义在一个人集合上的事物或对彖的子集

8、。b）概念是定义在一个大集合上的二值函数。概念学习的概念：a）概念学习就是从数据里提取出此概念的定义。b）概念学习可看成从给定的数据（输入、输出）中拟合出一个二值函数。概念学习的三种算法：a）Find-S：找到一个最具体的假设把H中的每个h初始化成最具体的假设。它对所有否定样本都不处理。它保证能收敛到一个最具体的假设。缺点：找到一个假设，但是并没有表示他是唯一的，有可能有其他假设存在;不一定最具体的假设就是最好的；不能适应噪声的问题；假设不止一个，然而此算法只能找到一个。b）候选-删除算法：输出与训练样例一致的所有假设的集合。（使S更一般、使G更具体）。它也不适应噪声问题。c）列表后消除算法：

9、列出所有的版本空间成员，然后把不合适的找出。他要先将所有的假设找出来，然而这并不都是可以实现的。第四章决策树决策数学系的概念：决策树学习是一个简单的逼近方法，学习一个离散型函数。学习函数被用一个决策树来表示；同时，决策树能被描述为if-then规则。决策树分类的基本步骤：a）从数据归纳产生出一棵树。b）用模型对新数据进行分类。决策树学习过程：a）生成根节点：对每一个属性进行评估，得到一个最好的属性作为根。b）根属性有几个值就产生几个分支，将数据计划成若干部分。c）重复上述过程。不纯度计算方法：a）GiniIndex：=ginik沙GINIEntropy：Entropy(t)=-Sp(j/)lo

10、gp(J/)lG加N严Emropg-佬EmppW)Class讦icationerror：Error(t)=1-maxPi|/)p决策树优点：a）构造速度较快，节约。b）分类速度快。c）树小时容易解释。d）分类精度和别的方法差不多在一些简单的数据集上。如何解决过拟合现象：a）预裁剪：在树充分长成前停下来。停止的条件是所有的实例都被分为一个类，或者所有的属性值都相同。b）后裁剪：将树充分生成，再按自卞而上的方法进行裁剪。若将子树裁剪后泛化的误差减小，则将子树裁去，将类标号出现最多的标号作为裁掉树后补上的叶子。度量模型的方法：CountPREDICTEDCLASSACTUALCLASSClass=Y

11、esClass=NoClass=YesabClass=Nocd.a+dAccuracv=-a+b+c+clPrecision（p）=a+cRecall（r）=a+b2rplaF-measure（F）=r+p2a+h+c性能评估的方法：a）Holdout：用2/3训练，1/3测试。b）随机二次抽样：多次重复Holdout方法来改进最分类器性能的评估。c）交叉验证：把数据分为人小相同的k份，在每次运行，选择其中一份作检验集，其余的全做为训练集，该过程重复k次，使得每份数据都用于检验恰好一次。d）分块抽样。e）带回放抽样：适用于数据集小的情况。ROC（接受者操作特征曲线）：曲线上的每一点代表每个分类

12、器的性能。第五章神经网络神经网络适合具有下面特征的问题：a）实例是用很多“属性-值”对表示的。b）目标函数的输出可能是离散值、实数值或者由若干实数属性或离散属性组成的向量。c）训练数据可能包含错误。d）可容忍长时间的训练。e）可能需要快速求出目标函数值。f）人类能否理解学到的目标函数是不重要的。感知器：感知器以一个实数值向量作为输入，计算这些输出的线性组合，然后如果结果人于某个阈值就输出2,否则输出4。我们可以把感知器看作是n维实例空间中的超平面决策面。感知器网络的训练方法：a）感知器训练法则：从随机的权值开始，然后反复地应用这个感知器到每个训练样例,只要它误分类样例就修改感知器的权值。重复这

13、个过程，直到感知器正确分类所有的训练样例。法则如下：叫叫+AirzAiVy=7（t-o）xf在有限次使用感知器训练法则后，上面的训练过程会收敛到一个能正确分类所有训练样例的权向量，前提是训练样例线性可分，并且使用了充分小的ro如果数据不是线性可分的，那么不能保证训练过程收敛。b）Delta法则：如果训练样本不是线性可分的，那么delta法则会收敛到目标概念的最佳近似。Delta规则的拟合精度是足够好的，他用梯度下降的方法在假设空间中找出一组能够最好的拟合训练样本的一组。梯度下降法则：随意给一组初始值，循坏的修改初始值使误差E要足够小，他要在曲面上找一个下降方向最快的方向进行估计。w,：+Aw,

14、w,：+Aw,：W,Wi+Aw,：血=一c）这两个算法间的关键差异是感知器训练法则根据阈值化的感知器输出误差更新权值，然而Delta法则根据输入的非阈值化线性组合的误差来更新权值。反向传播算法：用来学习由一系列确定的单元互连形成的多层网络的权值。它采用梯度下降方法试图最小化网络输出值和目标值之间的误差平方。先用样本数据训练神经网络时,它自动地将输出值与期望值进行比较，得到误差信号，再根据误差信号，从后向前调节个神经网络层神经元之间的连接强度，然后再进行运算，使误差减小，再将新的输出值与期望值进行比较，得到新的比先前小的误差信号，再根据较小的误差信号，从后向前重新调节各神经网络层神经元之间的连接

15、强度，依此不断地多次进行，直到误差满足要求为止。第六章贝叶斯学习贝叶斯学习方法的特征：a）观察到的每个训练样例可以增量的降低或升高某假设的估计概率。b）先验知识可以与观察数据一起决定假设的最终概率。c）贝叶斯方法可允许假设做出不确定性的预测。d）新的实例分类可由多个假设一起做出预测，用他们的概率来加权。e）即使在贝叶斯方法计算复杂度较高时，他们仍可作为一个最优的决策的标准衡量其他方法。贝叶斯公式：P(D)极大后验假设MAP和极大似然度ML：考虑候选假设集合H并在其中寻找给定数据D是可能性最大的假设ho这样的具有最大可能性的假设被称为MAP假设。=argmaxP(h|D)heHP(D|h)P(h

16、)=aramax;heHP(D)=argmaxP(Dh)P(h)heH当H中每个假设有相同的先验概率时，最大后验假设就可以进一步化简为极人似然假设：力三argmaxP(Dh)*heH贝叶斯最优分类器：分类通过合并所有假设的预测得到，用后验概率来加权。argmax工如D)它将每一个假设都最大化它的结果。如果我们用了同样的假设空间和先验知识，则贝叶斯最优分类器比其他方法都好。对假设空间的表示要求不是很严格。问题：需要将所有假设空间加起来，若h很人，则计算量很人，因此算法开销比较大。朴素贝叶斯分类器：朴素贝叶斯分类器应用的学习任务中，每个实例x可由属性值的合取描述，而目标函数f(x)从某有限集合V中

17、取值。学习其被提供一系列关于目标函数的训练样例以及新实例,然后要求预测新实例的目标值。它基于一个简单的假定：在给定目标值时属性值之间相互条件独立。%=argmax3%=argmax3)11卩(勺W丿)贝叶斯信念网：贝叶斯信念网用有向环图的方式来表示一组随机变量之间的概率关系，他用更中立的态度进行分类。它还可以被看做是变量之间的因果关系图，用于推理和预测。实例：见课件。第七章基于实例的学习基于实例的学习：对训练样本不作处理，不构造模型，只是存储起来，当新的数据来时，从样本中找出类似的进行评估。基于实例的学习方法有时被称为消极学习法，因为他们把处理工作延迟到必须分类新实例时。这种消极学习方法有一个

18、关键的优点，就是他们不是在整个实例空间上一次性的估计目标函数,而是针对每个待分类新实例做出局部的和相异的估计。KNN基本思想：它假定所有实例都是N维空间中的点，新的实例的值可能和离他较近的只比较类似，则用离新实例较近的k个实例的值来预测新实例的值。如果是离散的，就用投票的方法，实数的就用平均的方法。K值较人时对噪声不敏感，取得比较好的结果的可能性比较人。K值小时可以将局部的结构拟合得很好(前提是数据质量要高)，计算成本小。KNN的优缺点：优点：训练快速。局部拟合，故可以学习较复杂的问题。没有损失信息。b）缺点：查询时间长。对属性受限。局部加权回归：KNN算法被看做在单一查询点x=xq上逼近目标

19、函数f,局部加权回归是这种方法的推广。它在环绕xq的局部区域内为目标函数f建立明确的逼近。他使用附近的或距离加权的训练样例来形成这种对f的局部逼近。基于案例的推理（Case-BasedReasoning）和KNN比较：a）相同点：他们都是消极的学习算法，都把在训练数据之外的泛化推迟至遇到一个新的查询实例才进行。他们通过分析相似的实例来分类新的查询实例，而忽略与查询极其不同的实例。b）不同点：它没有将实例表示为n维空间的实数点，而是使用更丰富的符号来表示实例。用来检索实例的方法更加复杂。第八章其他分类方法基于规则的分类器：是使用一组“if.then.”规则来分类的技术。覆盖度和精度概念：|A|：

20、规则前件；|D|：数据集条数；lAClyl：同时满足规则前件和后件的记录数Coverage（r）=IaI/IdIAccuracy（r）=IAOyI/1AI对分类器要求：a）互斥规则：如果规则集R中不存在两条规则被同一条记录触发，则称规则集R中的规则是互斥的。这个性质确保每条记录至多被R中的一条规则覆盖。b）穷举规则：如果属性值的任一组合，R中都存在一条规则加以覆盖，责成规则集R具有穷举覆盖。这个性质确保每一条记录都至少被R中的一条规则覆盖。对规则进行排序的两种策略：a）基于规则的排序：这个方案依据规则质量的某种度量对规则排序。这种方案确保每一个测试记录都是由他的“最好的”规则来分类。该方案一个

21、潜在的缺点是规则的秩越低越难解释，因为每个规则都假设所有排在他前面的规则不成立。b）基于类的排序：在这种方案中，属于同一类的规则在规则集R中一起出现。然后这些规则根据他们所属的类信息一起排序。同一类之间的相对顺序并不重要，只要其中一个规则被触发，类标号就会付给测试记录。然而，一个质量较差的规则可能碰巧预测较高秩的类，从而导致高质量的规则被忽略。构造规则分类的两大类方法：a）直接方法：直接从数据中抽象出规则。b）间接方法：从其他的分类模型中抽彖出规则。序列覆盖的基本思想：a）序列覆盖算法：最初给定一个空规则。用Learn-one-rule生成一条规则。删除选定规则覆盖的数据。重复2,3。b）停止

22、：计算的Gain和生成新规则后的Gain差别不人。c）裁剪:去掉一条规则，将前后规则集作用在测试集上比较错误率。第九章维度约减维度约减的概念：将原始的高维数据集压缩到低维的空间。维度约减的两类方法：a）特征子集选择：从给定的N个属性中选取M个属性来描述原有的数据集。b）特征抽取：将原始的属性集和投影到另外一个空间里获取新的属性集合。FSS（特征子集选择）要求：a）要有一个搜索的策略。目标函数的两类：a）Filters：目标函数评价属性用属性所含的信息量而和要用的预测算法无关，是一种无指导的选择方法。它主要解决特征之间的相关性。相关性是由数据集本身的特性决定的。b）Wrappers：目标函数本身

23、就是一个预测器，用预测精度来评估。它主要侧重于精度，计算成本较高。搜索的策略：往目前的子集中按一定顺序去增加、减少属性，因为是一个一个地加，故是局部最优的。a）朴素序列特征选择：对属性进行评分然后按分值人小排列，选取分数最高的M个属性。基本不能用，因为没有考虑到属性之间的相互依赖。b）顺序向前选择（SFS）：以一个空集开始，然后向空集中增加一个属性，该属性在给定某个分类器时要有最人识别率。然后在剩余的属性集中依次取出一个属性，使组合起来的识别率最人。当识别率不在增大或者减小时停止加入属性。当最终最优子集长度比较小时用这个方法最好。然而加入属性后就不能再取出。c）顺序向后选择（SBS）：选择所有

24、属性放入集合，第一次拿出一个识别率最低的属性，然后依次拿出属性直到拿出一个属性后该属性集合的性能不升高反而卞降。当最终最优子集长度比较人时用此方法最好。但是一旦拿出一个属性就不能放回去。d）双向搜索（BDS）：从空集开始使用SFS,从全集开始使用SBS,每一次确保SFS选择的属性SBS不能删除，SBS删除的属性SFS不能选择。e）序列漂浮向前选择（SFFS）：从空集开始，每次用SFS增加一个属性的同时用SBS检查该集合内是否有可以删除的属性，循坏该过程，直到该属性集合的识别率卞降停止。FiltersVSWrappers：a）Filters执行起来比较快。泛化性能比较好。对数据压缩程度不是很好（

25、他认为属性个数越多，性能越好）。b）Wrappers精度比较高。有一定的泛化能力。速度慢。泛化能力很多时候比较缺乏。PCA（主成分分析）：通过创建新的属性集的集合对原属性压缩。新的属性集数量要比原来的少且保留尽可能多的信息。PCA直接生成不相关的属性，且对属性排序，取前若干个作为新的属性集合。第十章集成学习什么是集成学习：集合多个模型用来得到比单个模型更好的预测精度。有指导的学习被描述为从一个假设空间中找到一个最好的假设，但有可能最好的假设不在一个单一的假设空间中，故集成学习可以利用多个假设空间，既是所有的假设空间都不包含正确的假设，但用一些方法处理每个假设空间最可能的假设也可能得到最好的假设

26、。集成学习的方法：a）给定数据集D。b）生成多个假设hl,h2.,c）为每个假设生成一个权值（可选）。d）根据工严也来分类/预测。如何集成基分类器：a）（加权）投票。b）（加权）平均。c）特定的方法：Stacking：根据bootstraped方法产生训练子集，然后训练生成结果作为第一层分类器，再将第一层分类器的结果作为第二层分类器的输入。他是为了看训练样例是否被正确处理了。RegionBoost：给每一个分类器加权，性能好权值人。因为很多分类器在处理数据集的某部分时性能好，则提高该分类器在该部分的权值。生成基分类器的方法：a）决定是同址模型还是异址模型。b）通过处理训练数据集：bagging

27、、boosting。c）通过处理属性集：属性集合选择。d）通过处理输出的类：错误纠正输出编码。e）通过处理学习算法：随机注入。Bagging方法：用Bootstraped产生N个训练集，然后训练N个基分类器，再对N个基分类器进行投票。他适用于不稳定的学习过程，即数据集的一个小变动会产生人的差别，例如决策树、多层感知器。Boosting方法：它能提高弱分类器的性能。它是带权值的抽样，改变数据对象的权值，分类好的数据给与小权值,分类不好的数据给与人权值，最终集成分类结果用加权投票的方法。一些经验:a）如果分类器不稳定用baggingob）如果分类器稳定且简单用boostingoc）如果分类器稳定且

28、复杂用随机注入。d）如果数据有很多类，但是分类器只能处理两个类时，用错误纠正编码。为什么集成学习有效：a）从统计学角度来说当假设空间很人时，有可能有一些假设有着相同的精度，单一的学习器只能找出他们中的一个假设。然而集成多个假设就有可能找到最可能的假设。b）从计算角度来讲，很多单一学习算法都只能找到一个局部最优假设，当数据集很人时，可能很难找到一个最优假设，集成学习可以从多个起始点去局部逼近，这样就有可能得到一个全局最优的假设。c）从表示角度来说，很多情况下最好的假设并不存在于假设空间中，当用集成方法对多个假设空间加权集成时就有可能突破假设空间找到最符合的假设。第十一章聚类分析什么叫聚类分析：从

29、给定对象中找出一些簇，使在同一簇中的对象要相似，类与类之间的对象要不相似。我们希望类内部越紧越好，类之间界限要越明显越好。聚类的三类方法和其代表算法思想：a）分层聚类:簇之间是一个嵌套的形式，没有必要定义有多少个类，需要几个都可以。且他可以定义多个含义，具体含义和问题有关。两种方法：聚合方法：每个数据点都看为一个类，两两合并直到合并为一个类。分裂方法：将所有的对象看做一个簇，分类直到每个类里包含一个点时停下。此方法一旦将两个簇合并后就不能再更改，它也没有定义一个明确的目标函数，即不是全局最优化；每种方法都有各种缺点。b）分区聚类：一个数据对象只属于一个簇。K-means：1.随机选择k个点作为

30、初始中心点。计算每个点到不同中心点的距离，将点划分到几个簇里。重新计算每个簇的中心点。重复簇的划分直到簇的分布基本不变时停止。c）基于密度的聚类：对类的定义不同，他认为类是由一些密集的点组成，这些密集的点被一些稀疏的点分开。DBSCAN：认为类是基于密度的，它认为一个簇是由密度连接的点组成的最大的集合。层次局类中计算距离的方法：a）两簇之间的最近距离：可以划分大小不同的类；对噪声和例外点敏感。b）两簇之间的最远距离:对噪声和例外点不是那么敏感单不易划分人小相差很人的类。c）组内平均距离：对噪声不是很敏感但是偏爱球形类。d）中心点之间的距离。e）用目标函数定义的距离。如何评估类：KSSE=工工z=lxeC,K-means方法的问题：a）K值不好选切初始点的选取不容易。解决方法：运行多次，选择一个使SSE最小的。先用分层聚类，然后分到一定成果时用它的值作为初始值,但效率不高。先选择多余k个初始值，然后将分得比较开的簇保留，近的合并。2分k-meansob）容易产生空簇。用增量的方式：每计算一个数据