《数据挖掘原理与实践蒋盛益版期末复习.doc》由会员分享，可在线阅读，更多相关《数据挖掘原理与实践蒋盛益版期末复习.doc（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据挖掘原理与实践蒋盛益版期末复习第一章数据挖掘定义技术层面：数据挖掘就是从大量数据中，提取潜在有用的信息和知识的过程.商业层面：数据挖掘就是一种商业信息处理技术,其主要特点是对大量业务数据进行抽取、转换、分析和建模处理，从中提取辅助商业决策的关键性数据。数据挖掘任务预测任务根据其它属性的值预测特定属性的值，如分类、回归、离群点检测.描述任务寻找概括数据中潜在联系的模式,如聚类分析、关联分析、演化分析、序列模式挖掘 。（1) 分类（Classification）分析分类分析，通过分析示例数据库中的数据为每个类别做出准确的描述或建立分析模型或挖掘出分类规则,然后用此分类规则对其它数据库中的记录进
2、行分类。 分类分析广泛应用于用户行为分析（受众分析）、风险分析、生物科学等。(2) 聚类(Clustering）分析“物以类聚，人以群分。聚类分析技术试图找出数据集中的共性和差异，并将具有共性的对象聚合在相应的类中。聚类可以帮助决定哪些组合更有意义,广泛应用于客户细分、定向营销、信息检索等等。(3) 回归（Regression )分析回归分析是确定两种或两种以上变数间相互依赖的定量关系的一种分析方法.其可应用于风险分析、作文自动评分等领域。（4) 关联（Association）分析关联分析，发现特征之间的相互依赖关系，通常是从给定的数据集中发现频繁出现的模式知识（又称为关联规则)。关联分析广泛
3、用于市场营销、事务分析等领域。聚类与分类的主要区别聚类与分类是容易混淆的两个概念，聚类是一种无指导的观察式学习，没有预先定义的类。而分类问题是有指导的示例式学习，预先定义的类。数据挖掘过程数据挖掘和知识发现紧密相连。知识发现是从数据中发现有用知识的整个过程n 知识发现的主要步骤：n 数据清洗。其作用是清除数据噪声和与挖掘主题明显无关的数据。n 数据集成。其作用是将来自多数据源中的相关数据组合到一起。n 数据转换。其作用是将数据转换为易于进行数据挖掘的数据存储形式。n 数据挖掘。其作用是利用智能方法挖掘数据模式或规律知识.n 模式评估。其作用是根据一定评估标准从挖掘结果筛选出有意义的相关知识。n
4、 知识表示。其作用是利用可视化和知识表达技术，向用户展示所挖掘的相关知识从商业的角度看，数据挖掘过程可分为三个阶段 数据收集：数据收集容易且不引人注意，但却是数据挖掘的基础。知识是从海量数据里提取出来的，因此要挖掘知识必须得收集一定量的数据。收集到的原始数据一般存在缺失值、错误值等问题，不能直接用作知识提取的数据源，需要进行数据预处理。 知识提取:基于经过预处理的数据,使用各种数据挖掘方法(如分类、聚类、关联分析等)进行知识提取，这是数据挖掘的核心部分。知识辅助决策：数据挖掘技术已被广泛地应用于各领域，其提取出来的知识可以很好地辅助决策者做出良好的决策第二章数据统计特征数据的中心度量1数据集
5、“中心”的最常用、最有效的数值度量是（算术）均值（mean).2设x1, x2,， xN是N个值的集合,则该值集的均值定义为： 截断均值:指定0和100间的百分位数p，丢弃高端和低端(p/2)的数据,然后用常规方法计算均值,所得的结果即是截断均值.中位数是p=100时的截断均值，而标准均值是对应于p=0的截断均值.例：计算1,2，3,4，5，90值集的均值，中位数和p=40的截断均值.解:均值是17。5，中位数是3。5,p=40时的截断均值也是3。5 数据预处理n 数据清理n 数据集成n 数据变换n 数据归约n 数据离散化数据清理噪声数据的平滑方法n 目前噪声数据的平滑方法包括：n 分箱:分箱
6、方法通过考察“邻居”（即周围的值)来平滑有序数据的值。n 聚类：聚类将类似的值组织成群或“簇”。n 回归：让数据适合一个函数来平滑数据。数据平滑实例n 一组排序后的数据（单位：元）：4，8,15,21,21，24，25，28，34n 划分为等深的箱q 箱1：4，8，15q 箱2:21，21，24q 箱3：25,28，34n 用箱平均值进行平滑q 箱1：9,9，9（下同）n 用箱的边界进行平滑q 箱1：4，4,15q 箱2：21，21，24q 箱3：25,25,34数据变换规范化n 最小-最大规范化：，优点：计算简单n Z-score规范化: ， 是均值，为标准差n 小数定标规范化： 离散属性间
7、的相关性计算q 离散型数据间相关性计算(互信息）n 特征x的信息熵n 已知变量y后x的条件信息熵n 信息增益数据对象之间的相异度n 距离：q 欧几里得距离其中，n的维数（总特征数），Xk和Yk分别表示X和Y的第k个分量q 闵可夫斯基(Minkowski )距离q x=1,城市块（曼哈顿）距离q x=2，欧几里得距离q x=，切比雪夫(Chebyshev）距离 二值属性n 二元数据相似性度量M01 = x取0并且y取1的属性的个数M10 = x取1并且y取0的属性的个数M00 = x取0并且y取0的属性的个数M11 = x取1并且y取1的属性的个数n 简单匹配系数（Simple Matching
8、 Coefficient,SMC): SMC = 值匹配的属性个数 /属性个数 = (M11 + M00） / (M01 + M10 + M11 + M00)n Jaccard系数J = 匹配的个数 /不涉及00匹配的属性个数 = （M11) / （M01 + M10 + M11) 例子X = （1 0 0 0 0 0 0 0 0 0） Y= （ 0 0 0 0 0 0 1 0 0 1） M01 = 2 (x取0并且y取1的属性的个数) M10 = 1 (x取1并且y取0的属性的个数） M00 = 7 (x取0并且y取0的属性的个数） M11 = 0 （x取1并且y取1的属性的个数) SMC
9、= (M11 + M00)/(M01 + M10 + M11 + M00) = （0+7) / (2+1+0+7） = 0。7 J = M11 / (M01 + M10 + M11) = 0 / (2 + 1 + 0) = 0 2.18以下表格包含了属性name,gender，trait1，trait2，trait-3,及trait-4，这里的name是对象的id,gender是一个对称的属性，剩余的trait属性是不对称的,描述了希望找到的笔友的个人特点.假设有一个服务是试图发现合适的笔友.对 不对称的属性的值，值P被设为1,值N被设为0。假设对象（潜在的笔友）间的距离是基于不对称变量来计算
10、的。(a) 计算对象间的简单匹配系数；SMC（Keavn,Caroline)=(2+2）/(0+0+2+2）=1SMC(Keavn，Erik)=（0+0)/(2+2+0+0)=0SMC(Caroline，Erik)=（0+0)/(2+2+0+0）=0(b) 计算对象间的Jaccard系数；Jaccard（Keavn，Caroline)=2/(2+0+0）=1Jaccard（Keavn，Erik)=0/（0+2+2)=0Jaccard（Caroline,Erik)=0/(0+2+2）=0(c) 你认为哪两个人将成为最佳笔友？哪两个会是最不能相容的？根据属性的匹配程度，Keavn和Caroline
11、将成为最佳笔友，Caroline和Erik会是最不能相容的（d)假设我们将对称变量gender包含在我们的分析中。基于Jaccard系数，谁将是最和谐的一对？为什么？若将对称变量gender包含在分析中，设值M被设为1,值F被设为0,Jaccard（Keavn，Caroline）=2/(2+1+0）=2/3Jaccard(Keavn，Erik）=1/(1+2+2）=1/5Jaccard（Caroline,Erik)=0/（0+2+3)=0因为Jaccard(Keavn，Caroline）最大，因此，Keavn和Caroline是最和谐的一对。第三章分类的定义q 分类是数据挖掘中的一种主要分析手
12、段q 分类的任务是对数据集进行学习并构造一个拥有预测功能的分类模型,用于预测未知样本的类标号，如:分类与回归的区别q 分类和回归都有预测的功能，但是：n 分类预测的输出为离散或标称的属性；n 回归预测的输出为连续属性值；q 分类与回归的例子：n 预测未来某银行客户会流失或不流失,这是分类任务；n 预测某商场未来一年的总营业额,这是回归任务。分类与聚类的区别q 分类因为使用了类标号属性,属于有监督的学习方法q 聚类,事先没有使用任何类标号信息，属于无监督的学习方法决策树的基本概念n 决策树（Decision Tree）是一种树型结构，包括：决策节点（内部节点)、分支和叶节点三个部分。n 其中：q
13、 决策节点代表某个测试，通常对应于待分类对象的某个属性，在该属性上的不同测试结果对应一个分支.q 叶节点存放某个类标号值，表示一种可能的分类结果。q 分支表示某个决策节点的不同取值。q 决策树可以用来对未知样本进行分类,分类过程如下:从决策树的根节点开始，从上往下沿着某个分支往下搜索，直到叶结点，以叶结点的类标号值作为该未知样本所属类标号。 决策树的属性选择n 虽然可以采用任何一个属性对数据集进行划分，但最后形成的决策树会差异很大。需要寻找合适的属性选择方法。n 属性选择是决策树算法中重要的步骤,常见的属性选择标准包括信息增益和Gini系数。q 信息增益是决策树常用的分枝准则,在树的每个结点上
14、选择具有最高信息增益的属性作为当前结点的划分属性。q Gini系数是一种不纯度函数，用来度量数据集的数据关于类的纯度.获得大小合适的树n 决策树学习的目的是希望生成能够揭示数据集结构并且预测能力强的一棵树,在树完全生长的时候有可能预测能力反而降低,为此通常需要获得大小合适的树。n 一般来说有两种获取方法:q 一种为定义树的停止生长条件，常见条件包括最小划分实例数、划分阈值和最大树深度等。q 另一种方法是对完全生长决策树进行剪枝，方法是对决策树的子树进行评估，若去掉该子树后整个决策树表现更好,则该子树将被剪枝.ID3分类算法n 它使用信息增益(information gain)作为属性的选择标准
15、。q 首先检测所有的属性,选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支,再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一个类别的数据为止。最后得到一棵决策树,它可以用来对新的样本进行分类。n 与ID3分类算法相关的基本概念包括：q 信息熵：用来度量一个属性的信息量。假定S为训练集，S的目标属性C具有m个可能的类标号值,C=C1,C2，Cm，假定训练集S中,Ci在所有样本中出现的频率为 （i=1，2，3,m）,则该训练集S所包含的信息熵定义为：熵越小表示样本对目标属性的分布越纯，反之熵越大表示样本对目标属性分布越混乱。 信息熵例题n 考虑数据集wea
16、ther如下, 求weather数据集关于目标属性play ball的熵.n 解答：令weather数据集为S，其中有14个样本，目标属性play ball有2个值C1=yes, C2=no。14个样本的分布为：q 9个样本的类标号取值为yes，5个样本的类标号取值为No。C1=yes在所有样本S中出现的概率为9/14,C2=no在所有样本S中出现的概率为5/14。q 因此数据集S的熵为：q信息增益信息增益是划分前样本数据集的不纯程度(熵)和划分后样本数据集的不纯程度（熵）的差值q 假设划分前样本数据集为S，并用属性A来划分样本集S，则按属性A划分S的信息增益Gain(S，A)为样本集S的熵减
17、去按属性A划分S后的样本子集的熵：按属性A划分S后的样本子集的熵定义如下：假定属性A有k个不同的取值,从而将S划分为k个样本子集S1,S2,Sk，则按属性A划分S后的样本子集的信息熵为：其中Si（i,=1，2，k）为样本子集Si中包含的样本数，|S为样本集S中包含的样本数。信息增益越大，说明使用属性A划分后的样本子集越纯，越有利于分类。信息增益例题n 以数据集weather为例，设该数据集为S，假定用属性wind来划分S，求S对属性wind的信息增益。 n 解答：q (1）首先由前例计算得到数据集S的熵值为0。94;q (2）属性wind有2个可能的取值weak，strong，它将S划分为2个
18、子集：S1,S2，S1为wind属性取值为weak的样本子集,共有8个样本;S2为wind属性取值为strong的样本子集，共有6个样本;下面分别计算样本子集S1和S2的熵。对样本子集S1，play ball=yes的有6个样本，play ball=no的有2个样本,则：对样本子集S2，play ball=yes的有3个样本，play ball=no的有3个样本，则：n 利用属性wind划分S后的熵为：n 按属性wind划分数据集S所得的信息增益值为：ID3建树算法n 以weather数据集为例,讲解ID3的建立过程。数据集的构成n 数据集具有属性：outlook， temperature，
19、humidity, wind。 n outlook = sunny, overcast， rain n temperature = hot， mild， cool n humidity = high， normal n wind = weak, strong ID3建立决策树n 首先计算总数据集S对所有属性的信息增益，寻找根节点的最佳分裂属性:n Gain(S, outlook) = 0。246n Gain（S, temperature) = 0。029n Gain(S, humidity) = 0。152n Gain（S, wind） = 0。049 n 显然,这里outlook属性具有最高
20、信息增益值，因此将它选为根结点。 n 以outlook做为根结点，继续往下:n 思想是，以outlook的可能取值建立分支，对每个分支递归建立子树.n 因为outlook有3个可能值，因此对根结点建立3个分支sunny, overcast, rain。n 首先对outlook的sunny分支建立子树.q 找出数据集中outlook = sunny的样本子集Soutlook=sunny,然后依次计算剩下三个属性对该样本子集Ssunny划分后的信息增益：n Gain（Ssunny， humidity) = 0。971n Gain(Ssunny， temperature） = 0。571n Gain
21、（Ssunny， wind） = 0。371显然humidity具有最高信息增益值，因此它被选为outlook结点下sunny分支下的决策结点n 采用同样的方法，依次对outlook的overcast分支、rain分支建立子树，最后得到一棵可以预测类标号未知的样本的决策树。ID3算法总结n ID3算法是所有可能的决策树空间中一种自顶向下、贪婪的搜索方法。n ID3搜索的假设空间是可能的决策树的集合,搜索目的是构造与训练数据一致的一棵决策树，搜索策略是爬山法，在构造决策树时从简单到复杂，用信息熵作为爬山法的评价函数.n ID3算法的核心是在决策树各级结点上选择属性，用信息增益作为属性选择的标准，
22、使得在每个非叶节点进行测试时能获得关于被测数据最大的类别信息,使得该属性将数据集分成子集后，系统的熵值最小。C4。5分类算法n 基于ID3算法中存在的不足，Quinlan于1993年对其做出改进，提出了改进的决策树分类算法C4.5，该算法继承了ID3算法的优点，并在以下几个方面对ID3算法进行了改进：q (1)能够处理连续型属性数据和离散型属性数据；q （2)能够处理具有缺失值的数据；q (3）使用信息增益率作为决策树的属性选择标准；q (4）对生成的树进行剪枝处理，以获取简略的决策树;q （5)从决策树到规则的自动产生。C4。5算法的概念描述假定S为训练集，目标属性C具有m个可能的取值，C=
23、C1，C2,Cm,即训练集S的目标属性具有m个类标号值C1,C2，Cm，C4。5算法所涉及的概念描述如下：n （1)假定训练集S中，Ci在所有样本中出现的频率为pi(i=1,2,3，m)，则该集合S所包含的信息熵为:n （2)设用属性A来划分S中的样本，计算属性A对集合S的划分熵值EntropyA(S）定义如下：若属性A为离散型数据，并具有k个不同的取值，则属性A依据这k个不同取值将S划分为k个子集S1,S2,Sk,属性A划分S的信息熵为其中|Si|和|S分别是Si和S中包含的样本个数.如果属性A为连续型数据,则按属性A的取值递增排序,将每对相邻值的中点看作可能的分裂点,对每个可能的分裂点，计
24、算：其中SL和SR分别对应于该分裂点划分的左右两部分子集,选择EntropyA(S）值最小的分裂点作为属性A的最佳分裂点，并以该最佳分裂点按属性A对集合S的划分熵值作为属性A划分S的熵值.n (3) C4。5以信息增益率作为选择标准,不仅考虑信息增益的大小程度，还兼顾为获得信息增益所付出的“代价”:n C4。5通过引入属性的分裂信息来调节信息增益,分裂信息定义为q 信息增益率定义为q 这样如果某个属性有较多的分类取值,则它的信息熵会偏大，但信息增益率由于考虑了分裂信息而降低,进而消除了属性取值数目所带来的影响。 C4。5算法演示n 以weather数据集为例，演示C4。5算法对该数据集进行训练
25、,建立一棵决策树的过程,对未知样本进行预测。Step1：计算所有属性划分数据集S所得的信息增益分别为(参考ID3例题演示):Step2：计算各个属性的分裂信息和信息增益率q 以outlook属性为例，取值为overcast的样本有4条,取值为rain的样本有5条，取值为sunny的样本有5条：q 同理依次计算其它属性的信息增益率分别如下:Step3：取值信息增益率最大的那个属性作为分裂结点，因此最初选择outlook属性作为决策树的根结点，产生3个分支，如下：Step4：对根结点的不同取值的分支，递归调用以上方法，求子树，最后通过C4。5获得的决策树为贝叶斯分类方法q 贝叶斯分类方法是一种基于
26、统计的学习方法.q 是一种利用概率统计知识进行学习分类的方法。n 如：预测一个数据对象属于某个类别的概率。n 如：计算邮件是垃圾邮件或合法邮件的概率，取概率大的为预测结果q 主要算法有：n 朴素贝叶斯分类算法n 贝叶斯信念网络分类算法等。贝叶斯定理n 假定X为类标号未知的一个数据样本，H为样本X属于类别C的一个假设q 分类问题就是计算概率P（H|X) 的问题,即给定观察样本X下假设H成立的概率有多大。q 这里：n P（H)表示假设H的先验概率(prior probability)。n P(X)表示样本数据X的先验概率.n P(H|X)表示在条件X下，假设H的后验概率(posterior pro
27、bability）。n P(XH)表示在给定假设H的前提条件下，样本X的后验概率例：n 假设数据集由三个属性构成：q 年龄、收入、是否购买计算机q 样本X为:35, 4000， ?q 假设H为：顾客将购买计算机.q 则：n P（H）表示任意给定的顾客将购买计算机的概率，而不考虑年龄、收入其它信息。n P（X)表示数据集中,样本年龄为35，工资为4000的概率。n P（HX）表示已知顾客的年龄和收入分别为35和4000，顾客购买计算机的概率。n P(XH）表示已知顾客购买计算机,顾客年龄和收入属性值为35和4000的概率。 n 假设X,Y是一对随机变量,它们的：q 联合概率P（X=x，Y=y)是
28、指X取值x且Y取值y的概率q 条件概率是指一随机变量在另一随机变量取值已知的情况下取某一个特定值的概率。n 例如P(Y=yX=x）是指在变量X取值x的情况下，变量Y取值y的概率）。n 贝叶斯定理是指X和Y的联合概率和条件概率满足如下关系：n 例:考虑A和B两队之间的足球比赛：假设过去的比赛中,65%的比赛A对取胜，35%的比赛B对取胜。A对胜的比赛中只有30是在B对的主场，B对取胜的比赛中75%是在主场.n 如果下一场比赛在B对的主场进行，请预测哪支球队最有可能胜出？解答：根据贝叶斯定理,假定n 随机变量X代表东道主,X取值范围为A,Bn 随机变量Y代表比赛的胜利者，取值范围为A,B.n 已知
29、:n A对取胜的概率为0.65，表示为：P（Y=A）=0.65，n B对取胜的概率为0.35 ，表示为：P（Y=B)=0.35，n B对取胜时作为东道主的概率是0。75，表示为：P(X=B|Y=B) = 0.75，n A对取胜时B对作为东道主的概率是0.3,表示为：P（X=B|Y=A) = 0。3,n 计算：n 下一场比赛在B对主场，同时A对胜出的概率表示为：P(Y=AX=B）q P（Y=A|X=B) = P(X=B|Y=A）P(Y=A）/P(X=B） = (0.3*0。65）/0.4575=0.4262n 下一场比赛在B对主场，同时B对胜出的概率表示为:P(Y=B|X=B）q P（Y=BX=
30、B）=P(X=B|Y=B)P(Y=B）/P(X=B) =(0.75*0。35）/0。4575=0.5737根据计算结果，可以推断出，下一场最有可能是B对胜出P(X=B)的计算 ：q P（X=B)= P（X=B,Y=A）+P(X=B，Y=B） = P（Y=AX=B）*P(X=B) + P(Y=BX=B)*P（X=B） = P(X=B|Y=A）*P（Y=A) + P(X=BY=B）P(Y=B) = 0。30.65+0。750。35=0.195+0.2625 = 0。4575 朴素贝叶斯分类算法n 朴素贝叶斯分类算法利用贝叶斯定理来预测一个未知类别的样本属于各个类别的可能性，选择其中可能性最大的一个
31、类别作为该样本的最终类别。朴素贝叶斯分类算法演示例子：对weather数据集使用朴素贝叶斯算法预测未知样本X=rainy,hot,normal,false，？的play ball类标号属性的值。n 该问题描述如下：n 样本X=rainy， hot, normal， false, ？n 类标号play ball有2个取值yes， non 题目即求：n 样本X在play为yes的概率P（play=yes|X)n 和样本在play为no的概率P（play=noX）n 样本X将被预测为概率值大的那个类。解:根据朴素贝叶斯定理：P（play=yesX）=P(Xplay=yes）*P（play=yes）
32、=P(x1|play=yes)*P（x2play=yes）P(x3play=yes）P(x4play=yes）*P（play=yes）其中：P(x1play=yes)=P（outlook=rainy|play=yes）=3/9P(x2play=yes）=P（temperature=hotplay=yes)=2/9P(x3|play=yes)=P（humidity=normal|play=yes）=6/9P(x4play=yes)=P（windy=falseplay=yes）=6/9P(play=yes)=9/14因此：P(play=yes|X)=1/32/92/32/39/14=0.0211
33、同样方法计算：P(play=noX)=P（Xplay=no)*P(play=no) =P(x1|play=no）*P（x2play=no)P（x3play=no)*P（x4play=no）P(play=no)其中:P（x1play=no)=P（outlook=rainy|play=no）=2/5P(x2|play=no）=P（temperature=hotplay=no)=2/5P(x3play=no）=P(humidity=normal|play=no)=1/5P(x4|play=no）=P(windy=falseplay=no)=2/5P(play=no)=9/14因此:P（play=no
34、|X)=2/52/51/52/59/14=0.0082 n 根据计算结果：q P(play=yes|X) P(play=noX）n 所以：q 样本X=rainy,hot，normal,false,?的play类标号值应为yes.第四章基于划分的聚类算法给定一个 n 个对象或元组的数据库，一个划分方法构建数据的k个划分,每个划分表示一个聚类，并且k=n。也就是说，它将数据划分为k个组,同时满足如下的要求： (1）每个组至少包含一个对象； （2）每个对象必须属于且只属于一个组。划分式聚类算法需要预先指定簇数目或簇中心，通过反复迭代运算，逐步降低目标函数的误差值，当目标函数值收敛时，得到最终聚类结果
35、。这类方法分为基于质心的(Centroid-based）划分方法和基于中心的(Medoid-based）划分方法基本kmeans聚类算法k-means聚类算法：(1)从数据集D中任意选择k个对象作为初始簇中心；(2) repeat（3） for 数据集D中每个对象P do(4） 计算对象P到k个簇中心的距离（5) 将对象P指派到与其最近(距离最短）的簇；(6) end for(7) 计算每个簇中对象的均值，做为新的簇的中心；(8） until k个簇的簇中心不再发生变化 K-means算法采用k，mean来表示一个簇k-means聚类算法示例n 例 4.1 对表4-1中二维数据，使用k-mea
36、ns算法将其划分为2个簇，假设初始簇中心选为P7(4，5），P10（5，5)。表41 k-means聚类过程示例数据集1n 解：图42 显示了对于给定的数据集k-means聚类算法的执行过程。（1）根据题目，假设划分的两个簇分别为C1和C2，中心分别为(4,5）和（5，5)，下面计算10个样本到这2个簇中心的距离，并将10个样本指派到与其最近的簇：（2）第一轮迭代结果如下： 属于簇C1的样本有：P7，P1,P2，P4，P5，P8 属于簇C2的样本有:P10，P3，P6，P9重新计算新的簇的中心，有：C1的中心为(3.5，5。167），C2的中心为（6.75,4.25）（ 簇中心的计算方式是平均
37、类中所有点）(3）继续计算10个样本到新的簇的中心的距离，重新分配到新的簇中，第二轮迭代结果如下： 属于簇C1的样本有： P1，P2，P4,P5，P7，P10 属于簇C2的样本有： P3，P6，P8，P9 重新计算新的簇的中心，有:C1的中心为(3.67，5.83)，C2的中心为(6。5，3.25）(4)继续计算10个样本到新的簇的中心的距离，重新分配到新的簇中，发现簇中心不再发生变化,算法终止.K-均值算法练习给出一个样本数据库，并对它实施k均值算法设n=8，k=2,随机选择序号1和3作为初始点n 设n=8，k=2n 第一次迭代：假定随机选择两个对象,如序号1和序号3当作初始点，分别找到离两
38、点最近的对象,并产生两个簇1,2和3，4,5，6，7，8n 对于产生的簇计算平均值（1。5,1) (3.5,3）n 第二次迭代:根据平均值调整对象所在的簇，重新聚类，得到新的簇1，2,3,4和5,6,7，8。重新计算平均值(1.5，1.5) （4。5，3。5)第三次迭代：按平均值重新聚类，簇保持不变,程序结束K-均值算法应用实例n 根据2005-2010年的战绩，分析中国男足的地位n 其中包括两次世界杯和一次亚洲杯,提前对数据做如下预处理：对于世界杯，进入决赛圈则取其最终排名,没有进入决赛圈的，打入预选赛十强赛赋予40，预选赛小组未出现的赋予50.对于亚洲杯，前四名取其排名，八强赋予5,十六强
39、赋予9，预选赛没出现的赋予17。这样做是为了使得所有数据变为标量，便于后续聚类。n 对数据进行归一化：n 用算法进行聚类，设k=3，将15支球队分为3个集团具体步骤：1抽取日本,巴林和泰国的值作为三个簇的种子,即初始化三个簇中心为：A=0。3,0,0。19,B=0.7,0。76,0.5,C=1,1，0.52计算所有球队分别对三个点的相异度(欧式距离）第一次聚类结果：A:日本，韩国，伊朗，沙特B:乌兹别克斯坦，巴林，朝鲜C:中国，伊拉克,卡塔尔，阿联酋,泰国，越南，阿曼，印尼。3 根据第一次聚类结果，调整各个簇的中心点:A簇的中心点为：（0。3+0+0。24+0.3）/4=0.21,（0+0。1
40、5+0。76+0.76)/4=0。4175,(0.19+0。13+0。25+0。06）/4=0.1575=0.21,0.4175,0。1575B0.7，0.7333，0。4167C1,0.94,0。40625用调整后的中心再次聚类，得到:第二次迭代后,结果无变化，说明结果已收敛。最终聚类结果：亚洲一流:日本，韩国，伊朗，沙特亚洲二流:乌兹别克斯坦，巴林，朝鲜亚洲三流：中国，伊拉克，卡塔尔，阿联酋，泰国，越南,阿曼，印尼。第五章关联分析的基本概念举例TIDItems100Cola Egg Ham200Cola Diaper Beer300Cola Diaper Beer Ham400Diaper
41、 Beer，T为事务集合Apriori方法的优化策略Apriori算法的例子1n 考虑下面的事务数据库TIDItems100Cola Egg Ham200Cola Diaper Beer300Cola Diaper Beer Ham400Diaper Beern 最小支持度计数阈值=2Apriori练习设定min_sup=2，min_conf=50，求出所有的频繁项集合强关联规则Apriori算法例子：FP-Growth方法FP树的构建FP增长过程n 首先查找以“Ham为后缀的频繁项集,然后依次是“Beer、“Diaper、“Cola”. n “Ham”的条件模式基（Cola： 1)，（Col
42、a Diaper Beer: 1） q “Ham的条件FP-树只有1个分支 q 得到频繁项集Cola Ham:2 FP增长过程n “Beer”的条件模式基(Cola Diaper：2)，(Diaper：1）q “Beer”的条件FP-树q 迭代挖掘条件FP树，产生模式集Diaper Beer：3，Cola Diaper Beer：2，Cola Beer：2 第六章什么是离群点（Outlier）？离群点是在数据集中偏离大部分数据的数据离群点的特殊意义和实用价值现有数据挖掘研究大多集中于发现适用于大部分数据的常规模式,在许多应用领域中,离群点通常作为噪音而忽略，许多数据挖掘算法试图降低或消除离群点
43、的影响。而在有些应用领域识别离群点是许多工作的基础和前提，离群点会带给我们新的视角. 如在欺诈检测中，离群点可能意味欺诈行为的发生,在入侵检测中离群点可能意味入侵行为的发生离群点检测的应用领域n 电信、保险、银行中的欺诈检测与风险分析 n 发现电子商务中的犯罪行为n 灾害气象预报n 税务局分析不同团体交所得税的记录,发现异常模型和趋势 n 海关、民航等安检部门推断哪些人可能有嫌疑 n 海关报关中的价格隐瞒n 营销定制：分析花费较小和较高顾客的消费行为n 医学研究中发现医疗方案或药品所产生的异常反应n 计算机中的入侵检测n 应用异常检测到文本编辑器，可有效减少文字输入的错误 基于距离的离群点检测
44、基于距离的离群点检测算法n 输入：数据集D；最近邻个数kn 输出：离群点对象列表n 1:for all 对象x don 2： 确定x的k-最近邻集合N（x，k)n 3： 确定x的离群因子 OF1(x,k)n 4:end forn 5:对OF1（x，k)降序排列，确定离群因子大的若干对象n 6:return例61 在图64所示的二维数据集中,当k=2时,P1、P2哪个点具有更高的离群点得分?(使用欧式距离）解答：对P1点进行分析：k=2；最近邻的点为P3(5,7），P2（5,2），distance(P1，P2)与distance（P1，P3)分别为6.08,1.41，平均距离为：对P2点进行分析：k=2；最