注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

瘋人院

lunatic asylum

 
 
 

日志

 
 

数据挖掘作业复习  

2010-01-19 12:51:18|  分类: 數據挖掘 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

======================第一章===========================

1. 给出下列英文缩写或短语的中文名称和简单的含义

(1)      Data Mining 数据挖掘:从大量数据中提取或者“挖掘”知识。

(2)      Artificial intelligence 人工智能:是研究开发用于模拟延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的术学科。

(3)      Machine learning 机器学习:人工智能的一个子领域,主要关注与开发一些让计算机可以自动“学习”的技术。

(4)      Knowledge engineering 知识工程:人工智能在知识信息处理方面的发展,研究如何由计算机表示知识,进行问题的自动求解。

(5)      Information retrieval 信息检索:指将信息按一定的方式组织和存储起来,并根据信息用户的需要找出有关的过程和技术。

(6)      Data visualization 数据可视化:是关于数据之视觉表现形式的研究。

 

2.给出下列英文缩写或短语的中文名称和简单的含义:

       1OLTP(on-line transaction processing) 联机事务处理:是推动和管理面向事务的应用程序的一类程序,典型地针对数据输入和恢复事务处理。

       2OLAP(on-line analytic processing) 联机分析处理:使分析人员,管理人员或执行人员能够从多角度对信息进行快速一致,交互地存取,从而获得对数据的更深入了解的一类软件技术。

       3decision support 决策支持:为决策者提供分析问题,建立模型,模拟决策过程和方案的环境

       4KDD(knowledge Discovery in databases) 从数据集中识别出有效地、新颖的、潜在有用的,以及最终可以理解的模式的非平凡过程。

       5transaction database 事务数据库:由一个文件组成,其中每个记录代表一个事务的集合

       6distributed database 分布式数据库:是用计算机网络将物理上分散的多个数据库单元连接起来组成一个逻辑统一的数据库。

 

3.数据(data)、信息(information)和知识(knowledge)是人们认识和利用数据的三个不同阶段,数据挖掘技术是如何把它们有机的结合在一起的?

                                                                                   客观世界---(收集)---》数据---(分析)---》信息---(深入分析)---》知识---(决策与行动)---》客观世界。

 

8.从数据挖掘研究角度看如何理解数据、信息和知识的不同和联系?

                                                                                   数据时原材料他只是描述发生了什么事,并不能构成决策或行动的可靠基础。通过对数据进行分析找出其中关系,赋予数据以某种意义和关联,就形成所谓信息。信息虽给出了数据中一些有定义意义的东西,但它往往和人们需要完成的任务没有直接的关系,也还不能做为判断,决策和行动的依据,而所谓知识,可定义为信息块的一组逻辑联系其关系式通过上下文或过程的贴近度发现的。

 

9.简述数据挖掘技术将来的发展趋势

                                                                                   1)、形式化描述的语言

                                                                                   2)、可视化的数据挖掘过程

                                                                                   3)、web网络中数据挖掘的应用

                                                                                   4)、融合各种异构数据的挖掘技术

                                                                                   5)、处理的数据将会涉及到更多的数据类型

                                                                                   6)、交互式发现

       7)、知识的维护更新

 

11、你认为应该如何来理解KDDdata mining的关系?说明你的理由?

                                                           在某些时候可以认为data mining就是KDD,但data mining所包含的范围相对比较小一点。Data mining简单地讲就是从大量数据中挖掘或抽取出知识,而KDD它是一个从大量数据中抽取挖掘出未知的,有价值的模式或规律等知识的复杂过程。

 

12.解释data mining理解为KDD整个过程的一个关键步骤的合理性?

                                                           都是利用智能方法挖掘数据模式或规律知识

 

=========================第二章====================

1.KDD是一个多步骤的处理过程,它一般包含哪些基本阶段?简述各阶段的功能。

      KDD是一个多步骤的处理过程,一般分为问题定义、数据抽取、数据预处理、数据挖掘以及模式评估等基本阶段。

(1)      问题定义阶段的功能:和领域专家以及最终用户紧密协作,一方面了解相关领域的有关情况,熟悉背景知识,弄清用户要求,确定挖掘目标等要求;另一方面通过对各种学习算法的对比而确定可用的学习算法。

(2)      数据抽取阶段的功能: 选取相应的源数据库,并根据要求从数据库中提取相关的数据。

(3)      数据预处理阶段的功能:对前一阶段抽取的数据进行再加工,检查数据的完整性及数据的一致性。

(4)      数据挖掘阶段的功能:运用选定的数据挖掘算法,从数据中提取出用户所需要的知识。

(5)      模式评价阶段的功能:将KDD系统发现的知识以用户能了解的方式呈现,并且根据需要进行知识的评价。如果发现知识和用户挖掘的目标不一致,则重复以上阶段以最终获得可用知识。

 

5.阶梯处理过程模型是知识发现的基本模式,画出它的基本处理流程,并简要说明各阶段的任务。

     图参考课本P43页图2-1KDD阶梯处理过程模型;

源数据—(数据选择)—>目标数据—(数据预处理)—>预处理后的数据—(数据缩减)—>缩减后的数据—(数据挖掘)—>模式—(模式解释与评估)—>知识

     各阶段任务:

(1)      数据准备:了解相关领域的情况,弄清楚用户的要求,确定挖掘的总体目标和方法,并对原数据结构加以分析、确定数据选择原则等工作。

(2)      数据选择:从数据库中提取与KDD目标相关的数据。

(3)      数据预处理:主要是对上一阶段产生的数据进行再加工,检查数据的完整性及数据一致性,对其中的噪音数据进行处理、对丢失的数据可以利用统计方法进行填补。对一些不适合于操作的数据进行必要的处理等。

(4)      数据缩减:对经过溢出的数据,根据知识发现的任务对数据进行抽取处理,是数据再次精简取其精华,更好地集中于用户挖掘目标上。

(5)      确定KDD的目标:根据挖掘的目标和用户的要求,确定KDD发现的具体知识模式和类型。

(6)      确定数据挖掘算法:根据上一阶段所确定的模式,选择合适的数据挖掘算法。

(7)      数据挖掘:运用选定的算法,从数据中提取出用户所需要的知识。

(8)      模式解释:对发现的模式进行解释。在此过程中,为了取得更为有效的知识,可能会返回前面处理不重的某些步以改进结果,保证提取出的知识是有效和可用的。

(9)      知识评价:将发现的知识以用户能了解的方式呈现给用户。这期间也包含对知识的一致性和检查,以确信本次发现的知识不与以前发现的知识相抵触。

 

8.联机KDD模型需要解决那些问题

  完善可视化技术;对可视化数据挖掘的统一框架进行探索,也需要对某一个方面的问题探索不同的解决方法。

 

9.知识发现软件或工具的发展经历哪三个主要阶段?简述他们的主要特点。

知识发现软件或工具的发展经历了独立的知识发现软件、横向的知识发现工具和纵向的知识发现解决法案三个主要阶段。

(1)       独立的知识发现软件:这类软件要求用户必须对具体的数据挖掘技术和算法有相当了解,还要手工负责大量的数据预处理工作。

(2)       横向的知识发现工具:这些集成软件属于通用辅助工具范畴,可以帮助用户快速完成知识发现的不同阶段处理工作。使用这些工具,用户可以在数据挖掘和知识发现专家的指导和参与下开发对应的应用,起到了加速应用研制的作用。比如:DBMiner,Quest, IBM Intelligent Miner, Darwin,ReMind.

(3)       纵向的知识发现解决方案:这种方法的核心是对特定的商业领域和商业逻辑提供完整的数据挖掘和知识发现解决方案。

 

12.简述强度挖掘的I-MIN过程模型的主要阶段和任务。

主要分成IM1IM2...IM6等步骤处理。

任务:      IM1:是KDD项目的计划阶段,需要确定企业的挖掘目标,选择知识发现模式,编译知识发现模式得到元数据。

IM2:是KDD的预处理阶段,可以用IM2aIM2c、等分别对应于数据清洗、数据选择和数据转换等阶段。

IM3:是KDD的挖掘准备阶段数据挖掘工程师进行挖掘实验,反复测试和验证模型的有效性。

IM4:是KDD的数据挖掘阶段,用户通过指定数据挖掘算法得到对应的知识。

IM5:是KDD的知识表示阶段,按指定要求形成规格化的知识。

IM6:是KDD的知识解释与使用阶段。

 

13简述数据挖掘语言的三中基本类型和特点。

 根据功能和侧重点不同,数据挖掘语言可以分为三种类型:数据挖掘查询语言、数据挖掘建模语言、通用数据挖掘语言。

(1)      数据挖掘查询语言:遵循类似SQL的语法,通过数据挖掘任务、功能以及其他约束指定、知识形成和展示等系列工作,以类似于查询的形式输入到数据挖掘系统,通过数据挖掘系统产生对应的结果。

(2)      数据挖掘建模语言:是对数据挖掘模型进行描述和定义语言。数据挖掘系统在模型定义和描述方面有标准可以遵循,那么各系统之间可以共享模型,既可以解决目前各数据挖掘系统之间封闭性的问题,又可以在其他应用系统中嵌入数据挖掘模型,解决统一的知识发现描述问题。

(3)      通用数据挖掘语言:通用数据挖掘语言合并上了上述两种语言的特点,既具有定义模型的功能,又能作为查询语言与数据挖掘系统通信,进行交互式挖掘。

 

14.为什么说数据挖掘语言研制对数据挖掘技术的发展是至关重要的?

       因为数据挖掘系统的期望特点是能够支持特别的和交互的数据挖掘,以利用灵活和有效地知识发现。它促进了信息交换和技术转换,推动了数据库的商品化和广泛接受,并成为数据可系统的成功开发、商品化、标准化的重用要性

==============================第三章====================================

1.       简单地描述下列英文缩写或短语的含义。

(1)      Parallel Association Rule Mining

并行关联规则挖掘:是指利用并行处理机、使用挖掘算法或在并行计算的环境下完成数据的高效挖掘工作。

(2)      Quantities Association Rule Mining

数量关联规则挖掘:指对含有非离散的数值属性的数据进行挖掘的技术。

(3)      Frequent Itemset

频繁项目集:是指出现频率高的项目对应的集合,反映交易数据中项目出现的频度信息。

(4)      Maximal Frequent Itemset

最大频繁项目集:是指频繁项目集中不出现相互包含的项目子集。

(5)      Closed Itemset

关闭项目集:简单地说,对于一个关闭项目集的任何元素,要么不被任何元素所包含,要么只被小于它的支持度的元素所包含。

2.      解析下列概念:

(1)      多层次挖掘关联规则

(2)      多维关联规则

(3)      事务数据库

(4)      购物篮分析

(5)      强关联规则

       1、由具有概念分层的关联规则挖掘产生的规则称为多层关联规则。

       2、在关联规则中的项或属性每个涉及多个维,则它就是多维关联规则。

                               3、数据库事务是指作为单个逻辑工作单元执行的一系列操作。

                                                             4、通过支持度和置信度这两个值来衡量两个商品会被一起购买的分析方法。

                                                             5、同时满足最小支持度阀值(min_sup)和最小置信度阀值(min_conf)的规则称为强关联规则。

 

3.      给出一个项目集I1在数据集D上的支持度(Support)的定义,并直观地解释它的含义。

   I1?I,项目集I1在数据集D上的支持度是包含I1的事务在D中所占的百分比。直观上说,一个项目集在一个数据集D上的支持度反映了这个项目集在数据集中出现的频率。

 

6.以购物篮应用为例说明挖掘频繁项目集所蕴含的商业价值。

  假如你是ALLElectronics的分店经理,你想更加了解你的顾客的购物习惯。例如,你想知道“什么商品组成集合顾客多半会在一次购物时同时就购买?”,你可以在你的商店顾客事务零售数据上运行购物篮分析。分析结构可以用于市场规划、广告策划、分类设计。例如,购物篮分析可以帮助经理设计部同的商店布局。一种策略是:经常一块购物的商品可以放近一些,以便进一步刺激这些商品一起销售。例如:如果顾客购买计算机业倾向于同时购买财务软件,便将硬件摆放离软件陈列近一点。另一种策略是:将硬件和软件放在商店的两端,可能诱发买这些商品的顾客一路挑选其它商品。

 

7.给出一个规则的可信度(Confidence)的定义,并直观地解释它的含义。

给定一个被讨论的项目集I和数据库D,规则I1=>I2的可信度是指包含I1I2的事务数在只包含I1的事务数所占的百分比例。利用支持度定义可以描述为:

         ConfidenceI1=>I2 = SupportI1I2/ SupportI1),其中I1I2?II1I2=Ф

 

9.一般地,在一个事物数据库中挖掘关联规则通过哪两个主要步骤完成,各步骤的主要如何和目标是什么?

(1)      发现频繁项目集:通过用户给定的最小支持度,寻找所有频繁项目集,即满足Support不小于最小支持度的所有项目子集。

(2)      生成关联规则:通过用户给定的最小可信度,在已经发现的最大频繁项目中,寻找可信度不小于用户给定的最小可信度的关联规则。

 

13.给定如表A3-1所示的一个事务数据库,写出Apriori算法生成频繁项目集的过程。(假设Minsuport=50%

L1生成:C1={a4)(b2)(c3)(d4)(e3)(f4);

L1={acdef}

L2生成:C2={ac2)(ad4(ae,3)(af,3)(cd,2)(ce,2)(cf,2)(de,3)(df,3)(ef,2);

L2={ad,ae,af,de,df};

L3生成:C3={(ade,3)(adf,3)(def,2);L3={ade,adf};

L4生成:C4{(adef,2)};L4=Φ

最大的频繁项目集为{adeadf}

15.对上上面的第13题所生成的最大频繁项目集,跟踪Rule-generate来生成对已的关联规则(设minconfidence=80%

   参考答案:

序号

Lk

Xm-1

Confidence

Support

规则(是否是强规则)

1

2

3

4

5

6

7

8

9

10

11

12

ade

ade

ade

ade

ade

ade

adf

adf

adf

adf

adf

adf

ad

a

d

ae

e

de

ad

a

d

af

f

df

75%

75%

75%

100%

100%

100%

75%

75%

75%

100%

75%

100%

60%

60%

60%

60%

60%

60%

60%

60%

60%

60%

60%

60%

ad->e

a->de

d->ae

ae->d

e->ad

de->a

ad->f

a->df

d->af

af->d

f->ad

df->a

 

17.Apriori算法的主要性能瓶颈是什么?

(1)           多次扫描事务数据库,需要很大的I/O负载;

(2)           可能产生庞大的候选集,由Lk-1产生K-候选集CK是指数增长的。

 

18.针对Apriori算法的主要性能瓶颈提出你的改进想法。

   (1)数据分割方法:

基本思想:首先把大容量数据库从逻辑上分成几个互不相交的块,每块应用挖掘算法生成局部的频繁项目集,然后把这些局部的频繁项目集作为候选的全局频繁项目集,通过测试他们的支持度来得到最终的全局频繁项目集。

改进方面:合理利用主存空间,数据分割为块内数据一次性导入主存提供机会支持并行挖掘算法。

      保证算法完整性:设数据集D被分割成分块D1,D2,...,Dn, 全局最小支持度为minsup_count,数据分块Di的局部最小支持度记为minsup_counti(i=1,2,...,n), 那么局部最小支持度minsup_counti按照如下方法生成: minsup_counti=minsup_count*||Di||/||D||,可以保证所有的局部频繁项目集成为全局频繁项目集的候选(即所有的局 部频繁项目集涵盖全局频繁项目集)。

  (2)基于散列(hash)的方法:

    基本思想:频繁项目集主要计算是在生成2-频繁项目集L2上。因此提出了改进产生2-频繁项目集的方法。这种方法把扫描的项目放到不同的hash桶中,每对项目最多只可能在一个特定的桶中。这样可以对每个桶中的项目子集进行测试,减少了候选集生成的代价,这种方法也可以扩展倒任意的k-频繁项目集生成上。

3)基于采样(sampling)的方法:

      基本思想:先使用数据库的抽样数据得到一些可能成立的规则,然后利用数据库的剩余部分验证这些关联规则是否正确。

      改进方面:降低I/O代价,但是抽样数据的选取以及由此而产生的结果偏差过大,即存在所谓的数据扭曲问题。从本质上说,使用一个抽样样本而不使用整个数据集的主要原因是效率问题。

 

19.基于数据分割(Partition)的方法可以改善Apriori算法的效率。阐述它的理由.

(1)      合理利用主存空间。数据分割为块内数据一次性导入主存提供机会,因而提高对大容量数据集的挖掘效率。

(2)      支持平行挖掘算法。

 

21.基于散列(Hash)的方法,可以改善Apriori算法的效率。阐述它的理由。

     使用散列的方法产生频繁项目集,可以改善Apriori算法的效率,主要是因为散列拥有能够快速查找元素的特性。这种方法把扫描的项目放到不同的哈希桶中,每个项目集最多只能在一个特定的桶中。这样可以对每个桶的项目子集进行测试,减少了候选集的生成代价。

 

22.除了上面提高的技术可以用于改善Apriori算法的效率以外,你认为还有哪些技术可以被应用来解决问题。

  Close算法

基本原理和思想:1)一个频繁闭合项目集的所有闭合项目子集一定是频繁的

    2)一个非频繁闭合项目集的所有闭合超级一定是非频繁的

    3)查找闭合项目集的方法:取出数据库的一项,记为t,如果对应的产生式pt的子集而且它的闭合为空,则把t记为p的闭合。如果不为空,则把p的闭合与t的交集作为p的新闭合。

    4)连接和剪枝同Apriori,但是新增了一个步骤:对于FCCi+1的每个产生式p,将FCi的产生式中是p的子集放在Sp中(因为已经进行了非频 繁子集的修剪,所以p的所有i项子集都存在于FCi中)。对于Sp的每一项s,如果ps的闭合的子集(注意是闭合的子集,不是等于闭合),则p的闭合就 等于s的闭合,因此需要把它从FCCi+1中删除。

 

改进:对特殊数据是可以减少数据库扫描次数的,由于实际上既是频繁的又是闭合的项目集的比例比频繁项目集的比例要小很多。所以算法改进在某些情况下是提高了数据库扫描次数。

 

FP-Tree算法

基本原理和思想:只进行2次数据库扫描,不使用候选集,直接压缩数据库成一个频繁模式树,最后通过这棵树生成挂链规则。基本过程如下:

  (1) Apriori算法,扫描数据库一次生成1-频繁集,并把它们按照降序排序,放入L表中。

  (2) 创建根节点,并标志为null,扫描数据库一次,当得到数据库的一个项目集时,就把其中的元素按L表的次序排序,然后递归调用FP-growth来实现FP-tree增长。

 

26.比较Apriori算法,阐述FP-tree的算法的优缺点

       不可以动态地更新数据,但可以减少I/O操作

27给定如表A3-4所示的一个事物数据库,画出FP-tree的生成过程。

最终生成树为:

33.多层次关联规则挖掘有两种基本策略,简述他们可能存在的主要问题及相关对策

(1)      统一的最小支持度:对于所有层次,都使用同一个最小支持度。这样对于用户和算法实现来说,相对容易,而且很容易支持层间的关联规则生成。但弊端也是显然的。首先,不同层次可能考虑问题的精度不同,面向的用户群不同。对于一些用户,可能觉得支持度太小,产生了过多不感兴趣的规则。而对于另外用户来说,又认为支持度太大,有用信息丢失过多。

(2)      不同层次使用不同的最小支持度:每个层次都有自己的最小支持度。较底层次的最小支持度相对较小,而较高层次的最小支持度相对较大。这种方法增加了挖掘的灵活性。但是,也留下了许多相关问题需要解决。首先,不同层次间的支持度应该所有关联,只有正确地刻画这种联系或找到转换方法,才能使生成的规则相对客观。另外,由于具有不同的支持度,层间的关联规则挖掘也是必须解决的问题。

34为什么层次关联挖掘可能产生规则冗余问题,你认为应该如何有效地避免这些冗余可能带来的问题?

  因为在挖掘的过程中很可能像挖到这样的数据对象,规则“夏季服装》酸奶“完全包含规则”衬衫》酸奶“的信息。有时可能需要考虑不到规则的部分包含问题,规则的合并问题等。因此对于多层次关联规则挖掘需要根据具体情况确定合适的挖掘策略。

 

35举例说明单维关联规则和多维关联规则的区别

   多维和单维关联规则的主要的区别在于维数。

 

===============================第四章===================================

1、 简单地描述下列英文缩写或短语的含义

a)        Data classification 数据分类

b)       K-nearest neighbors k-最临近方法

c)        Decision tree 决策树

d)       Entropy

e)        Posterior probability 后验概率

2、 数据分类分为哪两个步骤?简述每步的基本任务。

步骤:1、建立一个模型,描述预定的数据类集或概念集

         2、使用模型进行分类

3、决策树分类算法通常分为两个步骤:决策树生成和决策树修剪

 

===============================第五章===================================

1、 简单地描述下列英文缩写或短语的含义

a)        Partitioning methods 划分法

b)       Hierarchical methods 层次法

c)        Density-based methods 基于密度的方法

d)       Grid-based methods 基于网络的方法

2、 简单地描述下列英文缩写或短语的含义

a)        PAM:围绕中心点划分,是最早提出的k-中心点算法之一,它选用簇中位置最中心的对象作为代表对象,试图对n个对象给出k个划分。

b)       STING:是一种基于网络的多分辨率聚类技术,它将空间区域划分为矩形单元。

c)        DBSCAN :是一个基于密度的聚类算法。它将簇定义为密度相连的点的最大集合,能够把具有足够高密度的区域划分为簇,并可在有“噪声”的空间数据库中发现任意形态的聚类。

3、 简述聚类的基本概念

聚类就是将数据对象分组成为多个类或簇,划分的原则是在同一个簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大。

4、 你认为一个好的聚类算法应该具备哪些特性?

a)        可伸缩性

b)       具有处理不同类型属性的能力

c)        能够发现任意形状的聚类

d)       输入参数对领域知识的弱依赖性

e)        对与输入记录顺序不敏感

f)         挖掘算法应该具有处理高维数据的能力

g)       处理噪声数据的能力

h)       基于约束的聚类

i)          挖掘出来的信息是可理解的和可用的

5、 哪种聚类算法对噪声数据不明显,可以发现不规则的类?

a)        密度聚类

6、 简述划分聚类方法的主要思想。

给定一个有n个对象的数据集,划分聚类技术将构造数据k个划分,每一个划分就代表一个簇,k<=n

              划分满足下面条件:每一个簇至少包含一个对象

                                                 每一个对象属于且仅属于一个簇。

7、 举例说明k-平均算法的主要思想。

 

  评论这张
 
阅读(3876)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017