还剩11页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
第一章1.6
(1)数据特征化是目标类数据的一般特性或特征的汇总例如,在某商店花费1000元以上的顾客特征的汇总描述是年龄在40—50岁、有工作和很好的信誉等级
(2)数据区分是将目标类数据对象的一般特性与一个或多个对比类对象的一般特性进行比较例如,高平均分数的学生的一般特点,可与低平均分数的学生的一般特点进行比较由此产生的可能是一个相当普遍的描述,如平均分高达75%的学生是大四的计算机科学专业的学生,而平均分低于65%的学生则不是
(3)关联和相关分析是指在给定的频繁项集中寻找相关联的规则例如,一个数据挖掘系统可能会发现这样的规则专业(X,“计算机科学”)=拥有(X,”个人电脑“)[support=12%,confidence=98%],其中X是一个变量,代表一个学生,该规则表明,98%的置信度或可信性表示,如果一个学生是属于计算机科学专业的,则拥有个人电脑的可能性是98%12%的支持度意味着所研究的所有事务的12%显示属于计算机科学专业的学生都会拥有个人电脑
(4)分类和预测的不同之处在于前者是构建了一个模型(或函数),描述和区分数据类或概念,而后者则建立了一个模型来预测一些丢失或不可用的数据,而且往往是数值,数据集的预测它们的相似之处是它们都是为预测工具分类是用于预测的数据和预测对象的类标签,预测通常用于预测缺失值的数值数据例如某银行需要根据顾客的基本特征将顾客的信誉度区分为优良中差几个类别,此时用到的则是分类;当研究某只股票的价格走势时,会根据股票的历史价格来预测股票的未来价格,此时用到的则是预测
(5)聚类分析数据对象是根据最大化类内部的相似性、最小化类之间的相似性的原则进行聚类和分组聚类还便于分类法组织形式,将观测组织成类分层结构,把类似的事件组织在一起例如世界上有很多种鸟,我们可以根据鸟之间的相似性,聚集成n类,其中n可以认为规定
(6)数据演变分析描述行为随时间变化的对象的规律或趋势,并对其建模这可能包括时间相关数据的特征化、区分、关联和相关分、分类、预测和聚类,这类分析的不同特点包括时间序列数据分析、序列或周期模式匹配和基于相似性的数据分析例如假设你有纽约股票交易所过去几年的主要股票市场(时间序列)数据,并希望投资高科技产业公司的股票股票交易数据挖掘研究可以识别整个股票市场和特定的公司的股票的演变规律这种规律可以帮助预测股票市场价格的未来走向,帮助你对股票投资做决策1.11一种是聚类的方法,另一种是预测或回归的方法
(1)聚类方法聚类后,不同的聚类代表着不同的集群数据这些数据的离群点,是不属于任何集群在各种各样的聚类方法当中,基于密度的聚类可能是最有效的
(2)使用预测或回归技术构建一个基于所有数据的概率(回归)模型,如果一个数据点的预测值有很大的不同给定值,然后给定值可考虑是异常的用聚类的方法来检查离群点更为可靠,因为聚类后,不同的聚类代表着不同的集群数据,离群点是不属于任何集群的,这是根据原来的真实数据所检查出来的离群点而用预测或回归方法,是通过构建一个基于所有数据的(回归)模型,然后根据预测值与原始数据的值比较,当二者相差很大时,就将改点作为离群点处理,这对所建立的模型有很大的依赖性,另外所建立的模型并不一定可以很好地拟合原来的数据,因此一个点在可能某个模型下可能被当作离群点来处理,而在另外一个模型下就是正常点所以用聚类的方法来检查离群点更为可靠1.15挖掘海量数据的主要挑战是1)第一个挑战是关于数据挖掘算法的有效性、可伸缩性问题,即数据挖掘算法在大型数据库中运行时间必须是可预计的和可接受的,且算法必须是高效率和可扩展的2)另一个挑战是并行处理的问题,数据库的巨大规模、数据的广泛分布、数据挖掘过程的高开销和一些数据挖掘算法的计算复杂性要求数据挖掘算法必须具有并行处理的能力,即算法可以将数据划分成若干部分,并行处理,然后合并每一个部分的结果第二章2.11三种规范化方法
(1)最小—最大规范化(min-max规范化)对原始数据进行线性变换,将原始数据映射到一个指定的区间
(2)z-score规范化(零均值规范化)将某组数据的值基于它的均值和标准差规范化,是其规范化后的均值为0方差为1其中是均值,是标准差
(3)小数定标规范化通过移动属性A的小数点位置进行规范化amin-max规范化其中v是原始数据,min和max是原始数据的最小和最大值,new_max和new_min是要规范化到的区间的上下限原始数据2003004006001000
[01]规范化
00.
1250.
250.51bz-score规范化其中是均值,是标准差原始数据2003004006001000z-score-
1.06-
0.7-
0.
350.
351.
782.131逐步向前选择2逐步向后删除3向前选择和向后删除的结合第三章
3.2简略比较以下概念,可以用例子解释你的观点(a)雪花形模式、事实星座形、星形网查询模型答雪花形和事实星形模式都是变形的星形模式,都是由事实表和维表组成,雪花形模式的维表都是规范化的;而事实星座形的某几个事实表可能会共享一些维表;星形网查询模型是一个查询模型而不是模式模型,它是由中心点发出的涉嫌组成,其中每一条射线代表一个维的概念分层(b)数据清理、数据变换、刷新答数据清理是指检测数据中的错误,可能时订正它们;数据变换是将数据由遗产或宿主格式转换成数据仓库格式;刷新是指传播由数据源到数据仓库的更新
3.4a雪花形模式图如下(见74页)course维表univfacttablestudent维表area维表course_idcourse_namedepartmentarea_idcityprovincecountrystudent_idstudent_namearea_idmajorstatusuniversitystudent_idcourse_idsemester_idInstructor_idcountavg_gradeSemester维表semester_idsemesteryearInstructor维表Instructor_iddeptrankb特殊的QLAP操作如下所示(见79页)1)在课程维表中,从course_id到department进行上卷操作;2)在学生维表中,从student_id到university进行上卷操作;3)根据以下标准进行切片和切块操作department=”CS”anduniversity=”BigUniversity”;4)在学生维表中,从university到student_id进行下钻操作c这个立方体将包含个长方体(见课本88与89页)第五章
5.1(a)假设s是频繁项集,min_sup表示项集的最低支持度,D表示事务数据库由于s是一个频繁项集,所以有假设是s的一个非空子集,由于support_countsupport_sups,故有所以原题得证,即频繁项集的所有非空子集必须也是频繁的(b)由定义知,令是s的任何一个非空子集,则有由(a)可知,support这就证明了项集s的任意非空子集的支持度至少和s的支持度一样大(c)因为根据(b)有p=ps所以即“=l-”的置信度不可能大于“”(d)反证法即是D中的任意一个频繁项集在D的任一划分中都不是频繁的假设D划分成,min_sup表示最小支持度,C=F是某一个频繁项集,,,设F的项集在中分别出现次所以A=故(*)这与(*)式矛盾从而证明在D中频繁的任何项集,至少在D的一个部分中是频繁
5.3最小支持度为3(a)Apriori方法C1L1C2L2C3L3oke3key2mk3ok3oe3ke4ky3mo1mk3me2my2ok3oe3oy2ke4ky3ey2m3o3k5e4y3m3o3n2k5e4y3d1a1u1c2i1okey3FP-growth:RootK:5E:4M:1M:2O:2Y:1O:1Y:1Y:1itemConditionalpatternbaseConditionaltreeFrequentpatternyome{{kemo:1},{keo:1},{km:1}}{{kem:1},{ke:2}}{{ke:2},{k:1}}{{k:4}}K:3K:3,e:3K:3K:4{ky:3}{ko:3},{eo:3},{keo:3}{km:3}{ke:4}这两种挖掘过程的效率比较Aprior算法必须对数据库进行多次的扫描,而FP增长算法是建立在单次扫描的FP树上在Aprior算法中生成的候选项集是昂贵的(需要自身的自连接),而FP-growth不会产生任何的候选项集所以FP算法的效率比先验算法的效率要高(b)
5.6一个全局的关联规则算法如下1)找出每一家商店自身的频繁项集然后把四个商店自身的频繁项集合并为CF项集;2)通过计算四个商店的频繁项集的支持度,然后再相加来确定CF项集中每个频繁项集的总支持度即全局的支持度其支持度超过全局支持度的项集就是全局频繁项集3)据此可能从全局频繁项集发现强关联规则
5.14(a)所以该关联规则是强规则(b)所以给定的数据,买hotdogs并不独立于hamburgers,二者之间是正相关
5.191)挖掘免费的频繁1-项集,记为S12)生成频繁项集S2,条件是商品价值不少于$200(使用FP增长算法)3)从S1S2找出频繁项集4)根据上面得到的满足最小支持度和置信度的频繁项集,建立规则S1=S2第六章
6.1简述决策树的主要步骤答假设数据划分D是训练元组和对应类标号的集合1)树开始时作为一个根节点N包含所有的训练元组;2)如果D中元组都为同一类,则节点N成为树叶,并用该类标记它;3)否则,使用属性选择方法确定分裂准则分裂准则只当分裂属性和分裂点或分裂子集4)节点N用分裂准则标记作为节点上的测试对分裂准则的每个输出,由节点N生长一个分枝D中元组厥词进行划分
(1)如果A是离散值,节点N的测试输出直接对应于A的每个已知值
(2)如果A是连续值的,则节点N的测试有两个可能的输出,分别对应于和
(3)如果A是离散值并且必须产生二叉树,则在节点N的测试形如“”,是A的分裂子集如果给定元组有A的值,并且,则节点N的测试条件满足,从N生长出两个分枝5)对于D的每个结果划分,使用同样的过程递归地形成决策树6)递归划分步骤仅当下列条件之一成立时停止
(1)划分D的所有元组都属于同一类;
(2)没有剩余的属性可以进一步划分元组;
(3)给定分枝没有元组
6.4计算决策树算法在最坏情况下的计算复杂度是重要的给定数据集D,具有n个属性和|D|个训练元组,证明决策树生长的计算时间最多为证明最坏的可能是我们要用尽可能多的属性才能将每个元组分类,树的最大深度为log|D|在每一层,必须计算属性选择On次,而在每一层上的所有元组总数为|D|所以每一层的计算时间为因此所有层的计算时间总和为,即证明决策树生长的计算时间最多为
6.5为什么朴素贝叶斯分类称为“朴素”?简述朴素贝叶斯分类的主要思想答
(1)朴素贝叶斯分类称为“朴素”是因为它假定一个属性值对给定类的影响独立于其他属性值做此假定是为了简化所需要的计算,并在此意义下称为“朴素”
(2)主要思想(a)设D是训练元组和相关联的类标号的集合每个元组用一个n维属性向量表示,描述由n个属性对元组的n个测量另外,假定有m个类(b)朴素贝叶斯分类法预测X属于类C,当且仅当,因此我们要最大化,由于P(X)对于所有类为常数,因此只需要最大即可如果类的先验概率未知,则通过假定这些类是等概率的,即,并据此对最大化,否则,最大化,类的先验概率可以用估计其中是D中C类的训练元组数(c)假定属性值有条件地相互独立,则,如果是分类属性,则是D中属性的值为的C类的元组数除以D中C类的元组数;如果是连续值属性,则由高斯分布函数决定
6.13给定k和描述每个元组的属性数n写一个k最近邻分类算法算法输入
(1)设U是待分配类的元组;
(2)T是一个训练元组集,包括,
(3)假设属性是的类标签;
(4)m为训练元组的个数;
(5)n为每个元组的描述属性的个数;
(6)k是我们要找的最邻近数输出U的分类标签算法过程
(1)定义矩阵a[m]
[2]//(m行是存储与m个训练元组有关的数据,第一列是存储待分类元组U与训练元组的欧几里得距离,第二列是存储训练元组的序号)
(2)fori=1tomdofa[i]
[1]=EuclideandistanceU;Ti;a[i]
[2]=i;g//savetheindexbecauserowswillbesortedlater
(3)将a[i]
[1]按升序排列
(4)定义矩阵b[k]
[2]//第一列包含的K-近邻不同的类别,而第二列保存的是它们各自频数
(5)fori=1tokdofif类标签ta[i]
[2];n已经存在于矩阵b中then矩阵b中找出这个类标签所在的行,并使其对应的频数增加1eles将类标签添加到矩阵b可能的行中,并使其对应的频数增加1
(6)将矩阵b按类的计数降序排列
(7)返回b
1.//返回频数最大的类标签作为U的类标签第七章
7.1简单地描述如何计算由如下类型的变量描述的对象间的相异度(a)数值(区间标度)变量答区间标度变量描述的对象间的相异度通常基于每对对象间的距离计算的,常用的距离度量有欧几里得距离和曼哈顿距离以及闵可夫基距离欧几里得距离的定义如下其中和是两个n维数据对象曼哈顿距离的定义闵可夫基距离的定义(b)非对称的二元变量答如果二元变量具有相同的权值,则一个二元变量的相依表如下对象j10和1qrq+r0sts+t和q+sr+tp对象i在计算非对称二元变量的相异度时,认为负匹配的情况不那么重要,因此计算相异度时可以忽略,所以二元变量的相异度的计算公式为(c)分类变量答分类变量是二元变量的推广,它可以取多于两个状态值两个对象i和j之间的相异度可以根据不匹配率来计算,其中m是匹配的数目(即对i和j取值相同状态的变量的数目),而p是全部变量的数目另外,通过为M个状态的每一个创建一个二元变量,可以用非对称二元变量对分类变量编码对于一个具有给定状态值的对象,对应于该状态值的二元变量置为1,而其余的二元变量置为
0.(d)比例标度变量答有以下三种方法
(1)将比例标度变量当成是区间标度标量,则可以用闽可夫基距离、欧几里得距离和曼哈顿距离来计算对象间的相异度
(2)对比例标度变量进行对数变换,例如对象i的变量f的值变换为,变换得到的可以看作区间值
(3)将看作连续的序数数据,将其秩作为区间值来对待(e)非数值向量对象答为了测量复杂对象间的距离,通常放弃传统的度量距离计算,而引入非度量的相似度函数例如,两个向量x和y,可以将相似度函数定义为如下所示的余弦度量其中,是向量x的转置,是向量x的欧几里得范数,是向量y的欧几里得范数,s本质上是向量x和y之间夹角的余弦值
7.5简略描述如下的聚类方法划分方法、层次方法、基于密度的方法、基于网格的方法、基于模型的方法、针对高维数据的方法和基于约束的方法为每类方法给出例子
(1)划分方法给定n个对象或数据元组的数据可,划分方法构建数据的k个划分,每个划分表示一个簇,k=n给定要构建的划分数目k,划分方法创建一个初始画风然后采用迭代重定位技术,尝试通过对象在组间移动来改进划分好的划分的一般准则是在同一个簇的对象间互相“接近”和相关,而不同簇中的对象之间“远离”或不同k均值算法和k中心点算法是两种常用的划分方法
(2)层次方法层次方法创建给定数据对象集的层次分解根据层次的分解的形成方式,层次的方法可以分类为凝聚的或分裂的方法凝聚法,也称自底向上方法,开始将每个对象形成单独的组,然后逐次合并相近的对象或组,直到所有的组合并为一个,或者满足某个终止条件分裂法,也称自顶向下方法,开始将所有的对象置于一个簇中每次迭代,簇分裂为更小的簇,直到最终每个对象在一个簇中,或者满足某个终止条件
(3)基于密度的方法主要是想是只要“邻域”中的密度(对象或数据点的数目)超过某个阈值,就继续聚类也就是说,对给定簇中的每个数据点,在给定半径的邻域中必须至少包含最少数目的点这样的方法可以用来过滤噪声数据(离群点),发现任意形状的簇DBSCAN和OPTICS方法是典型的基于密度的聚类方法
(4)基于网格的方法基于网格的方法把对象空间量化为有限数目的单元,形成一个网格结构所有的聚类操作都在这个网格结构上进行这种方法的主要优点是处理速度很快,其处理时间通常独立于数据对象的数目,仅依赖于量化空间中每一维的单元数目STING是基于网格方法的典型例子
(5)基于模型的方法基于模型的方法为每簇坚定一个模型,并寻找数据对给定模型的最佳拟合基于模型的算法通过构建反映数据点空间分布的密度函数来定位簇它也导致基于标准统计量自动地确定簇的数目,考虑“噪声”数据和离群点的影响,从而产生鲁棒的聚类方法COBWEB和SOM是基于模型方法的示例
7.7k均值和k中心点算法都可以进行有效的聚类概述k均值和k中心点算法的优缺点并概述两种方法与层次聚类方法(如AGBES)相比的优缺点答
(1)k均值和k中心点算法的优缺点k中心点算法比k均值算法更鲁棒性,这是因为中线点不想均值那样容易受离群点或其他极端值影响然而,k中心点方法执行代价比k均值算法高
(2)k均值和k中心点算法与层次聚类方法(如AGBES)相比的优缺点k均值和k中心点算法都是划分的聚类方法,它们的优点是在聚类是它们前面的步骤可以撤销,而不像层次聚类方法那样,一旦合并或分裂执行,就不能修正,这将影响到聚类的质量k均值和k中心点方法对小数据集非常有效,但是对大数据集没有良好的可伸缩性,另外的一个缺点是在聚类前必须知道类的数目而层次聚类方法能够自动地确定类的数量,但是层次方法在缩放时会遇到困难,那是因为每次决定合并或分裂时,可能需要一定数量的对象或簇来审核与评价改善层次聚类方法有BIRCHROCK和Chameleon算法开始初始化属性集,设置初始归约集为空集确定原属性集中最好的属性所选属性是否超出停止界限把选中的属性添加到归约集中以减少属性设置否在初始设置中是否还有更多的属性是是否结束开始初始化属性设置为整个属性集确定原属性集中最差的属性所选属性是否超出停止界限否删除选中的最差属性以减少属性的设置在初始设置中有更多的属性设置是否是结束选择最好的属性加入到归约集中,并在剩余的属性中删除一个最差的属性开始初始化属性设置为空集确定原属性集中最好和最差的属性所选的最好的属性是否超出停止界限否所选的最差的属性是否超出停止界限?合并设置为减少属性所设置的初始工作的所有剩余的属性是否从最初的工作集属性中删除选定属性在初始设置中是否有更多的属性设置是否结束是。