数据挖掘试卷及答案

12/13年第2学期《数据挖掘与知识发现》期末考试试卷及答案一、什么是数据挖掘？什么是数据仓库？并简述数据挖掘的步骤。（20分）数据挖掘是从大量数据中提取或发现（挖掘）知识的过程。数据仓库是面向主题的、集成的、稳定的、不同时间的数据集合，用于支持经营管理中的决策制定过程。步骤：1）数据清理（消除噪声或不一致数据）2）数据集成（多种数据源可以组合在一起）3）数据选择（从数据库中检索与分析任务相关的数据）4）数据变换（数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作）5）数据挖掘（基本步骤，使用智能方法提取数据模式）6）模式评估（根据某种兴趣度度量，识别表示知识的真正有趣的模式；）7）知识表示（使用可视化和知识表示技术，向用户提供挖掘的知识）二、元数据的定义是什么？元数据包括哪些内容？（20分）元数据是关于数据的数据。在数据仓库中，元数据是定义仓库对象的数据。元数据包括：数据仓库结构的描述，包括仓库模式、视图、维、分层结构、导出数据的定义，以及数据集市的位置和内容。操作元数据，包括数据血统（移植数据的历史和它所使用的变换序列）、数据流通（主动的、档案的或净化的）、管理信息（仓库使用统计量、错误报告和审计跟踪）。汇总算法，包括度量和维定义算法，数据所处粒度、划分、主题领域、聚集、汇总、预定义的查询和报告。由操作环境到数据仓库的映射，包括源数据库和它们的内容，网间连接程序描述，数据划分，数据提取、清理、转换规则和缺省值，数据刷新和净化规则，安全（用户授权和存取控制）。关于系统性能的数据，刷新、更新定时和调度的规则与更新周期，改善数据存取和检索性能的索引和配置。商务元数据，包括商务术语和定义，数据拥有者信息和收费策略。三、在OLAP中，如何使用概念分层？请解释多维数据模型中的OLAP上卷下钻切片切块和转轴操作。（20分）在多维数据模型中，数据组织成多维，每维包含由概念分层定义的多个抽象层。这种组织为用户从不同角度观察数据提供了灵活性。有一些OLAP数据立方体操作用来物化这些不同视图，允许交互查询和分析手头数据。因此，OLAP为交互数据分析提供了友好的环境。上卷：上卷操作通过一个维的概念分层向上攀升或者通过维归约，在数据立方体上进行聚集。下钻：下钻是上卷的逆操作，它由不太详细的数据到更详细的数据。下钻可以通过沿维的概念分层向下或引入新的维来实现。切片：在给定的数据立方体的一个维上进行选择，导致一个子方。切块：通过对两个或多个维执行选择，定义子方。

转轴：转轴是一种目视操作，它转动数据的视角，提供数据的替代表示。四、什么是数据变换?数据变换涉及的内容有哪些？（20分）数据变换是将数据转换成适合于挖掘的形式。数据变换可能涉及如下内容：1）.平滑：去掉数据中的噪声。这种技术包括分箱、聚类和回归。2）.聚集：对数据进行汇总和聚集。例如，可以聚集日销售数据，计算月和年销售额。通常，这一步用来为多粒度数据分析构造数据立方体。3）.数据概化：使用概念分层，用高层次概念替换低层次“原始”数据。例如，分类的属性，如street，可以概化为较高层的概念，如city或country。类似地，数值属性，如age，可以映射到较高层概念，如young,middle-age和senior。4）.规范化：将属性数据按比例缩放，使之落入一个小的特定区间，如一1.0至01.0或0.0至01.0。5）.属性构造（或特征构造）：可以构造新的属性并添加到属性集中，以帮助挖掘过程。五、用Apriori、FP-growth、GSP、Prefixspan、SPAM算法中任意一到两种算法，挖掘出所有的频繁项集（表1）或频繁序列（表2），并写出具体过程。假设事务数据库D如下：最小支持度计数为2。（20分）以Apriori算法为例。TidItems10A,C,D20B,C,E30A,B,C,E40B,EDatabaseTDBSidSequence10<a(abc)(ac)d(cf)>TidItems10A,C,D20B,C,E30A,B,C,E40B,EDatabaseTDBSidSequence10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<(af)cbc>TidItems10A,C,D20B,C,E30A,B,C,E40B,E1stscanItemsetsup{A}2{B}3{C}31{E}31C1Itemsetsup{A}2{B}3{C}3{E}3L1Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2L2C2Itemset{B,C,E}3rdscanItemsetsup{B,C,E}2L31.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）数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。这可能包括时间相关数据的特征化、区分、关联和相关分、分类、预测和聚类，这类分析的不同特点包括时间序列数据分析、序列或周期模式匹配和基于相似性的数据分析。例如：假设你有纽约股票交易所过去几年的主要股票市场（时间序列）数据，并希望投资高科技产业公司的股票。股票交易数据挖掘研究可以识别整个股票市场和特定的公司的股票的演变规律。这种规律可以帮助预测股票市场价格的未来走向，帮助你对股票投资做决策。11一种是聚类的方法，另一种是预测或回归的方法。（1）聚类方法：聚类后，不同的聚类代表着不同的集群数据。这些数据的离群点，是不属于任何集群。在各种各样的聚类方法当中，基于密度的聚类可能是最有效的。（2）使用预测或回归技术：构建一个基于所有数据的概率（回归）模型，如果一个数据点的预测值有很大的不同给定值，然后给定值可考虑是异常的。用聚类的方法来检查离群点更为可靠，因为聚类后，不同的聚类代表着不同的集群数据，离群点是不属于任何集群的，这是根据原来的真实数据所检查出来的离群点。而用预测或回归方法，是通过构建一个基于所有数据的（回归）模型，然后根据预测值与原始数据的值比较，当二者相差很大时，就将改点作为离群点处理，这对所建立的模型有很大的依赖性，另外所建立的模型并不一定可以很好地拟合原来的数据，因此一个点在可能某个模型下可能被当作离群点来处理，而在另外一个模型下就是正常点。所以用聚类的方法来检查离群点更为可靠1.15挖掘海量数据的主要挑战是：第一个挑战是关于数据挖掘算法的有效性、可伸缩性问题，即数据挖掘算法在大型数据库中运行时间必须是可预计的和可接受的，且算法必须是高效率和可扩展的。另一个挑战是并行处理的问题，数据库的巨大规模、数据的广泛分布、数据挖掘过程的高开销和一些数据挖掘算法的计算复杂性要求数据挖掘算法必须具有并行处理的能力，即算法可以将数据划分成若干部分，并行处理，然后合并每一个部分的结果。性—-第二章11三种规范化方法：最小一最大规范化(min-max规范化)：对原始数据进行线性变换，将原始数据映射到一个指定的区间。V，=v——mi^(newmax-newmin)+newmin•max-minz-score规范化(零均值规范化)：将某组数据的值基于它的均值和标准差规范化，是其规范化后的均值为0方差为1。V，=」^，其中日是均值，。是标准差b小数定标规范化：通过移动属性A的小数点位置进行规范化。v'=二其中，j是使得Max(vL1的最小整数10j1(a)min-max规范化V，v-min/V，(new_max-new_min)+new_minmax-min其中v是原始数据，min和max是原始数据的最小和最大值，new_max和new_min规范化到的区间的上下限原始数据2003004006001000[0,1]规范化00.1250.250.51(b)z-score规范化v，=1二，其中日是均值，b是标准差b1000H=200+300+400+600+1000=500

10001(200-500力+(300-500)2+(400-500)2+(500-500)2+(1000-500)2rr—I—282.8427UV1\5原始数据2003004006001000z-score-1.06-0.7-0.350.351.782.13⑵逐步向后删除结束所选属性是否超出停止界限？是否在初始设置中有是更多的属性设置？否删除选中的最差属性，以减少属性的设置初始化属性设置为整个属性集确定原属性集中最差的属性4(3)向前选择和向后删除的结合性—*-弟三章3.2简略比较以下概念，可以用例子解释你的观点（a）雪花形模式、事实星座形、星形网查询模型。答：雪花形和事实星形模式都是变形的星形模式，都是由事实表和维表组成，雪花形模式的维表都是规范化的；而事实星座形的某几个事实表可能会共享一些维表；星形网查询模型是一个查询模型而不是模式模型，它是由中心点发出的涉嫌组成，其中每一条射线代表一个维的概念分层。（b）数据清理、数据变换、刷新答：数据清理是指检测数据中的错误，可能时订正它们；数据变换是将数据由遗产或宿主格式转换成数据仓库格式；刷新是指传播由数据源到数据仓库的更新。3.4（a）雪花形模式图如下：（见74页）course维表univfacttablestudent维表area维表（b）特殊的QLAP操作如下所示：（见79页）1）在课程维表中，从course_id到department进行上卷操作；2）在学生维表中，从student_id到university进行上卷操作；3）根据以下标准进行切片和切块操作:department="CS"anduniversity=”BigUniversity”；4）在学生维表中，从university到student_id进行下钻操作。（c）这个立方体将包含54625个长方体。（见课本88与89页）nz?-3^弟五早5.1（a）假设s是频繁项集，min_sup表示项集的最低支持度，D表示事务数据库。由于s是个频繁项集，所以有support(s)=support-count(s)>min_sup假设s'是s的一个非空子集，由于support_count(s')>support_sup(s),故有support(s')=supprot_count(s')>min_supIDI所以原题得证，即频繁项集的所有非空子集必须也是频繁的。(b)由定义知，support(s)=support_count(s)令s'是s的任何一个非空子集，则有support(s')=supprot_count(s)由(a)可知，support(s')>supprot(s),这就证明了项集s的任意非空子集s'的支持度至少和s的支持度一样大。(c)因为confidence(s=>l一s)="",confidence(s'=>l一s')="("p(s)p(s’)根据(b)有p(s')=>p(s)所以confidences=>l一s)>confidence^'=>l一s')即“s'=>(i-s')”的置信度不可能大于“s=>(l-s)”(d)反证法：即是D中的任意一个频繁项集在D的任一划分中都不是频繁的=C，…，d假设D划分成d,d,…,d,设|d|=C,d12nI1’1，min_sup表示最小支持度，C=|D|=C1+C2+•••+CNF是某一个频繁项集，A=F，A>CXmin_sup，D设F的项集在d,d，…,d中分别出现a,a,…,a次12n12n所以A=a1+a2+…+an故A>Cxmin_sup=(C+C++C^)xminsup)(*)na+ahba>(C+CHbC)xmin_sup12几12NF在D的任意一个划分都不是频繁的a<Cxmin_sup,a<Cxmin_sup，…，a<Cxmin_sup1122nn:.(a+aHba)<(C+CHbC)xmin_supnA<Cxmin_sup这与(*)式矛盾从而证明在D中频繁的任何项集，至少在D的一个部分中是频繁。5.3最小支持度为3（a）Apriori方法:C1m3o5.3最小支持度为3（a）Apriori方法:C1m3o3n2k5e4y3d1a1u1c2i1m3o3k5e4y3L1mo1mk3me2my2ok3oe3oy2ke4ky3ey2C2mk3ok3oe3ke4ky3L2okekeyaC3okey3L3FP-growth:Y:1itemConditionalpatternbaseConditionaltreeFrequentpatterny{{k,e,m,o:1}，{k,e,o:1}，{k,m:1}}K:3{k,y:3}o{{k,e,m:1}，{k,e:2}}K:3，e:3{k,o:3}，{e,o:3}，{k,e,o:3}m{{k,e:2}，{k:1}}K:3{k,m:3}e{{k:4}}K:4{k,e:4}这两种挖掘过程的效率比较：Aprior算法必须对数据库进行多次的扫描，而FP增长算法是建立在单次扫描的FP树上。在Aprior算法中生成的候选项集是昂贵的（需要自身的自连接），而FP-growth不会产生任何的候选项集。所以FP算法的效率比先验算法的效率要高。k,o—e[0.6,1]（b）e,o—k[0.6,1]5.6一个全局的关联规则算法如下：1）找出每一家商店自身的频繁项集。然后把四个商店自身的频繁项集合并为CF项集；2）通过计算四个商店的频繁项集的支持度，然后再相加来确定CF项集中每个频繁项集的总支持度即全局的支持度。其支持度超过全局支持度的项集就是全局频繁项集。3）据此可能从全局频繁项集发现强关联规则。5.14support(hotdogsnhumbergers)>25%2000=67%>50%3000>25%2000=67%>50%3000(a)===40%50005000p(hotdogs,hamburgers)coniidence=p(hotdogs)所以该关联规则是强规则。p(hotdogs,hamburgers)corr(hotdogs,hamburgers)=p(hotdogs)p(hamburgers)(b)_20005000_0.4_4>130005000x250050000.6x2.53所以给定的数据，买hotdogs并不独立于hamburgers,二者之间是正相关。5.191）挖掘免费的频繁1-项集，记为S12）生成频繁项集S2,条件是商品价值不少于$200（使用FP增长算法）3）从S1S2找出频繁项集4）根据上面得到的满足最小支持度和置信度的频繁项集，建立规则S1=>S2弟六早6.1简述决策树的主要步骤答：假设数据划分D是训练元组和对应类标号的集合树开始时作为一个根节点N包含所有的训练元组；如果D中元组都为同一类，则节点N成为树叶，并用该类标记它；否则，使用属性选择方法确定分裂准则。分裂准则只当分裂属性和分裂点或分裂子集。节点N用分裂准则标记作为节点上的测试。对分裂准则的每个输出，由节点N生长一个分枝。D中元组厥词进行划分。(1)如果A是离散值，节点N的测试输出直接对应于A的每个已知值。(2)如果A是连续值的，则节点N的测试有两个可能的输出，分别对应于A<split_point和A>split_point。(3)如果A是离散值并且必须产生二叉树，则在节点N的测试形如“AG5人”，5人是A的分裂子集。如果给定元组有A的值七，并且a,gSa，则节点N的测试条件满足，从N生长出两个分枝。对于D的每个结果划分D,，使用同样的过程递归地形成决策树。递归划分步骤仅当下列条件之一成立时停止：划分D的所有元组都属于同一类；没有剩余的属性可以进一步划分元组；给定分枝没有元组。6.4计算决策树算法在最坏情况下的计算复杂度是重要的。给定数据集D，具有n个属性和|D|个训练元组，证明决策树生长的计算时间最多为nxD|xlog板|)证明：最坏的可能是我们要用尽可能多的属性才能将每个元组分类，树的最大深度为log(|D|),在每一层，必须计算属性选择O(n)次，而在每一层上的所有元组总数为|D|，所以每一层的计算时间为O(nx|DI)，因此所有层的计算时间总和为O(nx|D|xlog《D|)，即证明决策树生长的计算时间最多为nx|D|xlog《D|)6.5为什么朴素贝叶斯分类称为“朴素”？简述朴素贝叶斯分类的主要思想。答：(1)朴素贝叶斯分类称为“朴素”是因为它假定一个属性值对给定类的影响独立于其他属性值。做此假定是为了简化所需要的计算，并在此意义下称为“朴素”。主要思想：(a)设D是训练元组和相关联的类标号的集合。每个元组用一个n维属性向量X={x,x,…,x}表示，描述由n个属性A,A，…,A对元组的n个测量。12n12n另外，假定有m个类C「C2,…,Cm(b)朴素贝叶斯分类法预测X属于类C‘.，当且仅当P(C.IX)>P(C^IX)1<j<m,j丰i，因此我们要最大化P(CIX)=P(XCP(C「，由于P(X)对于所有类为常数，因此只需要P(XIC)P(C).P(X)..最大即可。如果类的先验概率未知，则通过假定这些类是等概率的，即p（C）=P（C）=…P（C）,并据此对P（XIC）最大化，否则，最大化p（xIC）P（C）,12miiiICI类的先验概率可以用P-^1~估计。其中ICiDI是D中Ci类的训练元组数。（c）假定属性值有条件地相互独立，则P（XIC）=FfP（xIC）=P（xIC）XP（xIC）X…XP（xIC），如果A是分类属iki1i2inikk=1性，则P（xkIC）是D中属性Ak的值为xk的C,类的元组数除以D中C,类的元组数ICDI；如果Ak是连续值属性，则P（气IC）由高斯分布函数决定。6.13给定k和描述每个元组的属性数n,写一个k最近邻分类算法。算法：输入：（1）设U是待分配类的元组；（2）T是一个训练元组集，包括T=（t,t，…,t），11,11,21,nT=（t,t，…，t），…，T=（t,t，…，t）22，12,22，nmm，1m，2m，n（3）假设属性t^是T的类标签；（4）m为训练元组的个数；（5）n为每个元组的描述属性的个数；（6）k是我们要找的最邻近数。输出：U的分类标签算法过程：（1）定义矩阵a[m][2]。//（m行是存储与m个训练元组有关的数据，第一列是存储待分类元组U与训练元组的欧几里得距离，第二列是存储训练元组的序号）（2）fori=1tomdofa[i][1]=Euclideandistance（U;Ti）;a[i][2]=i;g//savetheindex,becauserowswillbesortedlater（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）数值（区间标度）变量答：区间标度变量描述的对象间的相异度通常基于每对对象间的距离计算的，常用的距离度量有欧几里得距离和曼哈顿距离以及闵可夫基距离。欧几里得距离的定义如下：d（i,j）^.'^X^-^-^^T^X"-^^T^T^X^^T"-^^其中i=（x,x，…,x）和j=（x,x，…,x）是两个n维数据对象。i1i2inj1j2jn曼哈顿距离的定义：d(i,j)=曼哈顿距离的定义：d(i,j)=x.—x.闵可夫基距离的定义：d（i,j）=（x+xx2-xj2+…+7%i1-xj1xx2-xj2injn（b）非对称的二元变量答：如果二元变量具有相同的权值，则一个二元变量的相依表如下:答：如果二元变量具有相同的权值，则一个二元变量的相依表如下:r+s忽略，所以二元变量的相异度的计算公式为：d（i,］）=q+r+s（c）分类变量答：分类变量是二元变量的推广，它可以取多于两个状态值。两个对象i和j之间的相异度可以根据不匹配率来计算：d（i,j）=P—m，其中m是匹配的数目（即对i和j取值相同状P态的变量的数目），而p是全部变量的数目。另外，通过为M个状态的每一个创建一个二元变量，可以用非对称二元变量对分类变量编码。对于一个具有给定状态值的对象，对应于该状态值的二元变量置为1，而其余的二元变量置为0.（d）比例标度变量答：有以下三种方法：（1）将比例标度变量当成是区间标度标量，则可以用闽可夫基距离、欧几里得距离和曼哈顿距离来计算对象间的相异度。（2）对比例标度变量进行对数变换，例如对象i的变量f的值xf变换为yf=log（x^），变换得到的yf可以看作区间值。（3）将x^看作连续的序数数据，将其秩作为区间值来对待。（e）非数值向量对象答：为了测量复杂对象间的距离，通常放弃传统的度量距离计算，而引入非度量的相似度函数。例如，两个向量X和y,可以将相似度函数定义为如下所示的余弦度量：xt-vS（X'V）=希其中，xt是向量X的转置，||x||是向量X的欧几里得范数，||v||是向量y的欧几里得范数，s本质上是向量x和y之间夹角的余弦值。7.5简略描述如下的聚类方法：划分方法、层次方法、基于密度的方法、基于网格的方法、基于模型的方法、针对高维数据的方法和基于约束的方法。为每类方法给出例子。（1）划分方法：给定n个对象或数据元组的数据可，划分方法构建数据的k个划分，每个划分表示一个簇，k<=n。给定要构建的划分数目匕划分方法创建一个初始画风。然后采用迭代重定位技术，尝试通过对象在组间移动来改进划分。好的划分的一般准则是：在同一个簇的对象间互相“接近”和相关，而不同簇