2017-2018学期数据挖掘作业

2017‐2018学期数据分析与挖掘课程试题1.请简要介绍数据挖掘技术的产生背景。（5’）答：随着通信、计算机和网络技术的快速发展，数据正以空前的速度产生和被收集。在各行各业许多公司已经开始认识到客户对业务非常重要，客户信息是他们的宝贵财富。大量信息在给人们带来方便的同时也带来了一大堆问题:信息冗余、信息真假难以辨识、信息安全难以保证、信息形式不一，难以统一处理等，人们淹没在数据中而难以快速制定合适的决策。在强大的商业需求驱动下，商家开始注意到有效的解决大容量数据的利用问题具有巨大商机，学者们开始思考如何从大容量数据集中获取有用信息和知识。面对这一挑战，数据挖掘技术应运而生，并显示出强大的生命力。利用数据挖掘工具进行数据分析可以发现重要的数据模式，这对商务策略、知识库、科学有重大贡献。2.请介绍数据挖掘包括哪些任务，并简要描述具体任务的工作内容。（5’）答：数据挖掘任务可以分为预测性和描述性任务。预测性任务如回归、分类、离群点检测，描述性任务如聚类分析、关联分析、序列模式挖掘。(1)聚类(Clustering)分析：“物以类聚，人以群分”。聚类分析技术试图找出数据集中的共性和差异，并将具有共性的对象聚合在相应的类中。聚类可以帮助决定哪些组合更有意义，广泛应用于客户细分、定向营销、信息检索等等。(2)分类(Classification)分析：通过分析示例数据库中的数据为每个类别做出准确的描述或建立分析模型或挖掘出分类规则，然后用此分类规则对其它数据库中的记录进行分类。分类分析广泛应用于用户行为分析、风险分析、生物科学等。(3)关联(Association)分析：关联分析，发现特征之间的相互依赖关系，通常是从给定的数据集中发现频繁出现的模式知识(又称为关联规则)。关联分析广泛用于市场营销、事务分析等领域。(4)离群点(Outlier)检测：离群点检测就是发现与众不同的数据。可应用于商业欺诈行为的自动检测，网络入侵检测，金融欺诈检测，反洗钱，犯罪嫌疑人调查，海关、税务稽查等。(5)回归(Regression)分析：回归分析是确定两种或两种以上变数间相互依赖的定量关系的一种分析方法。其可应用于风险分析、作文自动评分等领域。(6)序列模式(SequentialPattern)挖掘：序列模式挖掘是指分析数据间的前后序列关系，包括相似模式发现、周期模式发现等。其应用领域包括客户购买行为模式预测、Web访问模式预测、疾病诊断、网络入侵检测等3.请简要介绍C4.5决策树算法。（5’）答：C4.5是一系列用在机器学习和数据挖掘分类问题中的算法。它的目标是监督学习，给定一个数据集,其中的每一个元组都能用一组属性值来描述,每一个元组属于一个互斥的类别中的某一类。C4.5的目标是通过学习,找到一个从属性值到类别的映射关系,并且这个映射能用于对新的类别未知的实体进行分类。C4.5决策树的生长算法描述如下：（a）如果训练集全部属于同一个类别，那么创建一个叶节点；（b）否则计算训练集中每个属性的信息增益率，选择增益率最大的属性作为决策属性，并以该决策属性创建结点；（c）对上一步中决策属性结点的每个取值添加一个分支；（d）对每个分支的训练集，转至（a）。C4.5决策树的剪枝处理算法描述如下：（a）计算待剪子枝中叶结点的加权估计误差；（b）如果待剪子枝是一个叶结点，则结束；（c）否则，计算其子树误差和所有的分支误差；（d）如果叶结点误差小于子树误差和最大的分支误差，则剪枝，设置待剪子枝的根节点为叶结点；（e）如果最大的分支误差小于子树误差，则剪枝，以误差最大的分支替换待剪子树；（f）否则，不剪枝。4.请简要介绍K‐Means算法及其优缺点并阐述你对可能改进K‐Means算法的方法。答：简介:K-Means其核心思想是找出K个簇中心，使得每一个数据点到其最近的簇中心的平方距离和被最小化。k-means聚类算法的形式化描述如下：从数据集D中任意选择k个对象作为初始簇中心；计算对象P到k个簇中心的距离,将对象P指派到与其最近(距离最短)的簇；计算每个簇中对象的均值，做为新的簇的中心；一直重复操作，一直到k个簇的簇中心不再发生变化。优点：K-Means算法描述容易、实现简单、快速缺点：（1）簇个数k需要预先指定，但实际上难以确定；（2）算法对初始值的选取依赖性极大以及算法常陷入局部最优解；（3）由于将簇的质心作为簇中心进行新一轮聚类计算，远离数据密集区的孤立点和噪声点会导致簇的质心偏离真正的数据密集区，所以K-Means算法对噪声点和孤立点很敏感；（4）不能用于发现非凸形状的簇，或具有各种不同大小或密度的簇，即很难检测到“自然的”簇；（5）只能用于处理数值属性的数据集，不能处理包含分类属性的数据集。改进K-Means算法方法：(a)将分类型数据转换为数值型数据，再利用K-Means算法进行聚类分析；（b）适用于纯分类属性数据集的K-modes算法和适用于混合属性数据集的K-prototypes算法；（c）适用于混合属性数据集的K-Summary算法，它使用簇的摘要信息表示簇的质心。5.现有A、B、C、D、E五种商品的交易记录表，试找出满足最小支持度为50%，最小置信度为60%的关联规则。（20分）交易号商品代码100A、C、D200B、D、E300A、B、C、E400B、E答：首先列出所有频繁项目及大于或等于最小支持度的项集{A}-50%,{B}-75%,{C}-50%,{D}-50%,{E}-75%,{A,C}-50%.{B,E}-75%项集支持度计数{A,C}2{B,E}3support(A,B)=support(A,D)=support(A,E)=support(B,C)=support(B,D)=support(C,D)=support(C,E)=support(D,E)=25%50%，所以剔除得到关联规则：对于A-C:支持度=support({A,C})=50%置信度=support({A,C})/support({A})=100%对于B-E:支持度=support({B,E})=75%置信度=support({B,E})/support({B})=100%所以A,C与B,E都满足规则，可得到：A-C，C-A，B-E，E-B的强关联规则.6.一家著名高尔夫俱乐部在2周共计14天的时间内记录了每天的天气信息以及顾客是否光顾俱乐部的信息，如下表所示。请用朴素贝叶斯算法预测第15天X={sunny,mild,normal,false,?}的“是否打球人多”的类标号。（20分）3overcastHothighFALSEyes4rainyMildhighFALSEyes5rainyCoolnormalFALSEyes6rainyCoolnormalTRUEno7overcastCoolnormalTRUEyes8sunnymildhighFALSEno9sunnyCoolnormalFALSEyes10rainyMildnormalFALSEyes11sunnyMildnormalTRUEyes12overcastMildhighTRUEyes13overcasthotnormalFALSEyes序号天气状况温度湿度是否有风是否打球人多1sunnyHothighFALSEno2sunnyHothighTRUEno14rainycoolhighTRUEno15sunnymildnormalFALSE?答：思路:我们可以求出在{sunny,mild,normal,false}发生的条件下,事件play=yes和事件play=no的概率,谁的概率大,最终答案就选谁解：根据贝叶斯公式,有P(play=yes|X)=P(X|play=yes)*P(play=yes)/P(X)P(play=no|X)=P(X|play=no)*P(play=no)/P(X)我们要比较这两个概率的大小，由于分母相同且大于0，所以我们只需比较分子P(X|play=yes)*P(play=yes)=P(x1|play=yes)其中P(x1|play=yes)=P(天气状况=sunny|play=yes)=2/9P(x2|play=yes)=P(温度=mild|play=yes)=4/9P(x3lplay=yes)=P(湿度=normallplay=yes)=6/9P(x4lplay=yes)=P(风=false|play=yes)=6/9P(play=yes)=9/14P(play=yes|X)≈2/9*4/9*6/9*6/*9/14=16/567同理可得P(x1|play=no)=P(天气状况=sunny|play=no)=3/5P(x2|play=no)=P(温度=mild|play=no)=1/5P(x3lplay=no)=P(湿度=normallplay=no)=1/5P(x4lplay=no)=P(风=false|play=no)=2/5P(play=no)=5/14P(play=no|X)3/5*1/5*1/5*2/5*5/14=16/567=3/875根据结果P(play=yes|XP(play=no|X)所以,样本X={sunny,mild,normal,false？}的play类标号值为yes7.请计算第7题中属性“湿度”的信息增益和信息增益率。并请用C4.5算法预测第15天X={sunny,mild,normal,false,?}的“是否打球人多”的类标号。（20’）答：思路：假定S为训练集，S的目标属性C具有m个可能的类标号值，C={𝐶1，𝐶2，…𝐶𝑚}，𝐶𝑖在所有样本中出现的概率𝑝𝑖(i=1,2,3,…，m)，则该信息熵Entropy(S)为：Entropy(S)=Entropy(𝑝1，𝑝2，…，𝑝𝑚)=-914log2914-514log2514=0.9403（1）𝐸𝑛𝑡𝑟𝑜𝑝𝑦湿度（S）=∑𝑆𝑖𝑠𝑘𝑖=1Entropy(𝑆𝑖)=714(−37log237−47log247)+714(−67log267−17log217)=0.7885信息增益:Gain(S,湿度)=Entropy(S)-𝐸𝑛𝑡𝑟𝑜𝑝𝑦湿度（S）=0.1518SplitE（S,湿度）=-714log2714-714log2714=1信息增益率:GainRation(S,湿度)=𝐺𝑎𝑖𝑛(𝑆,湿度)SplitE（S,湿度）=0.1518同理可得：(2)Gain(S,天气状况)=Entropy(S)-𝐸𝑛𝑡𝑟𝑜𝑝𝑦天气状况（S）=0.9403-0.6935=0.2468SplitE（S,天气状况）=-514log2514-414log2414-514log2514=1.5774GainRation(S,天气状况)=𝐺𝑎𝑖𝑛(𝑆,天气状况)SplitE（S,天气状况）=0.1565(3)Gain(S,温度)=Entropy(S)-𝐸𝑛𝑡𝑟𝑜𝑝𝑦温度（S）=0.9403-0.5586=0.2468SplitE（S,天气状况）=-514log2514-414log2414-514log2514=1.5774GainRation(S,天气状况)=𝐺𝑎𝑖𝑛(𝑆,天气状况)SplitE（S,天气状况）=0.3817(4)Gain(S,有风)=Entropy(S)-𝐸𝑛𝑡𝑟𝑜𝑝𝑦天气状况（S）=0.9403-（614(−36log236−36log236)+814(−68log268−28log228)）=0.0481SplitE（S,有风）=-614log2614-814log2814=0.9852GainRation(S,有风)=𝐺𝑎𝑖𝑛(𝑆,有风)SplitE（S,有风）=0.0488判断的优先级为：温度天气状况湿度是否有风温度湿度有风天气hotmild,coolyesovercastrainy,sunnyhighnormalfalsey