数据挖掘 复习笔记第一部分

CourseReview

tomining,definition(

WhypreprocessData清理Data集成Datatransformation变换Data约简

Datadiscretization

离散化

OLAPOverviewCh2Whatwarehouse?

Differenceand

ClassificationPredictionCh4

Distancebasedalgorithm:(K-

Nearest

Decision:ID3strategyPredictionby

DistanceEuclideanHierarchicalMethods:Divisivek-Means,k-Medoid/PAM(PartitionAroundClusterbasedonin

AssociationRules

）

concept:correlationEfficientandFrequentMiningMethods:theofApriori:withoutMiningofAssociationRules:Multi-level,FromAssociationMiningStrongRulesAreNotNecessarilyInteresting

todatamining,definition(Ch1,Ch3)Dataminingdata)（据挖掘的定义）ofinterestingimplicit,previouslypotentiallyuseful)patternsamountofdata1+数据挖掘与只是发现的异同从大量的数据中提取非平凡的，先前不知道的，潜在有用的模式的过程。ML/statisticalprograms专家系统是数据处理小程序数挖掘的应用（市场分析管理）relationship(CRM),marketbasketmarketanalysis（风险分析与管理）customerretention,improvedunderwriting,qualitycompetitivedetectionpatterns其他应用挖流式据挖掘ofMultiple（数据挖掘是多学科的交叉）

数挖掘的功能A描述性的任务B预性的任务数挖掘的过程数据清理数据集成数选择数据转换数挖掘模式估识表达

数挖掘的多维视角DatatobeminedKnowledgetoassociation,clustering,trend/deviation,etc.atmultipleutilizedDatabase-oriented,datawarehouse(OLAP),machinestatistics,visualization,etc.ApplicationsadaptedRetail,telecommunication,fraudmining,marketanalysis,Web数挖掘能做什么ClusterRegressionSummarystatistics,rulesAnalysis/DependenciesanalysisTime-seriesanalysis,Detect数仓库和数据库的区别OLAPOverviewCh2Whatwarehouse?·betweendatabase

特点：

数据仓库的数据组织形式．星形模型由事实表和多个维度表组成。事实表中存放大量关于企业的事实数据，对象个数通常都很大而非规范化程度很高为表中存放描述性数据维度表是围绕事实表建立的较小的表。优点星模型是非规范化的以加存储空间的代价提高了多维数据的查询速度而范化的关系数据库设计是使数据的冗余保持在最少少当数据改变时系统必须执行的动作。缺：事问发变，来维不满要时需增加的。由于实的主键由所有的围标的主键组成，这种维度的变化带来数据变化将是非常复杂非常耗时的。星形模型的数据冗余量很大。．雪花模型雪花模型是对星形模型的扩展花型对星形模型的维度表进一步层次化来各维度可能被扩展为小的事实表成些局部层”域的点最限的少据存储，及较的度联在起改查性。雪模增了户须理表数，加某查的杂性但种式以系进步业和用，时低系的用度事模型是雪花模型的变种第二章据与处理Whypreprocess

Data清理Data集成Datatransformation变换Data约简Datadiscretization离散化为什要处数据理任务：

丢数处的法两办：噪的理法分箱的两种划分

分享平滑的三种方法：数不致处方：纠正数据成任务：

数据换任务数据归一化的三种方法：

数据简数约简的方法数据立方体维数规约数据压缩建立模型概念分层维数约减的方法：

建立模型：离散化

下面是重要的三个章节：关联规则，分类，聚类第三章联规则关联规则的两种方法FP-GROWYH

平凡项集具体步骤：

产生候选集的方法（剪枝）

算法的缺陷和提高效率的办法

困难：多次扫描数据库大量的候选集候选集重复计数提高策略：减少扫描数据库减少候选集改进候选集的支持度技术的方法

方法1：基于hash表的项集计数

将每个项集通过相应的函数映射hash表中的不的桶中，这样可以通过将桶中的项集计数跟最小支持计数相比较先淘汰一部分项集。

提高Apriori算的有效性2)方法2：事务压缩（压缩进一步迭代的事务数）

不包含任何集的事务不可能包含任何k+1)-集，这种事务在下一步的计算中可以加上标记或删除。

方法3：划分

挖掘频繁项集只需要两次数据扫描D中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。

第一次扫描：将数据划分为多个部分并找到局部频繁项集第二次扫描：评估每个候选项集的实际支持度，以确定全局频繁项集

提高Apriori算的有效性3)方法4：选样（在给定数据的一个子集挖掘）

基本思想：选择原始数据的一个样本，在这个样本上用法挖掘频繁模式通过牺牲精确度来减少算法开销为了提高效率样本大小应该以可以放在内存中为宜，可以适当降低最小支持度来减少遗漏的频繁模式

算法复杂度On*n

可以通过一次全局扫描来验证从样本中发现的模式可以通过第二此全局扫描来找到遗漏的模式FP-GROWTH因此，在挖掘效率上FP-growth算明显优于算，特别是在稠密数据库中，频繁项集的长度很大的情况下FP-growth算的优势越明显FP-growth算法的缺点是需要递归生成条件数据库和条件，此内存开销大，它也只能挖掘单维的布尔关联规则。FP-growth算使用一种紧缩的数据结构来存储查找频繁项目集所需要的全部信息。将提供频繁项目集的数据库压缩到一颗频繁模式树（或树保留项集关联信息；后，将压缩后的数据库分成一组条件数据库，每个关联一个频繁项目集。在年

Rakesh\r\nAgrawal

提出了Apriori算法之后，关联规则挖掘技术的可用性得到了很大的提高且为关联则挖掘与生俱来的商业意义得迅速成为了一个非常热门的研究领域，新的算法也不断地涌现出来。这其中性比较强的一个算法，是韩家玮

教授提出的算。FP-Growth算在年发表的这个paper《

MiningFrequentPatternswithoutCandidateGeneration

》里有详细的介绍。读这篇paper，个人建议一定要同时把引文也都看一看，年之前与关联规则挖相关的重要paper基本上都在里面了。FP-Growth算的核心是FP-TreeFrequent，繁式树）的构建，这个特殊的数据结构，是FP-Growth算法与算相比，性能显著提高的原因所在。不过，仔细分析一下FP-Tree的实现，可以发现它与字符串处理算法中常用的

PrefixTree

算法，有着异曲同工之妙通过合并一些重复路径，实现了数据的压缩从而使得将频繁项集加载到内存中成为可能后树遍历的操作代了

Apriori

算法中最耗费时间的事务记录遍历从而大大提高了运效率详的理论讲解可以阅读上面的论文我这里还是把其中的例子翻译一下。\r\n某据库DB里5条事务记录，取最小支持度（threshold）为，则生成FP-Tree的过程如下：、\r\n扫描一遍数库，获取所有频繁项，删除频率小于最小支持度的项。在此操作的过程中，还可以得到每个项的出现频率，供后续步骤使用。这一步完成之后，我们到以下频繁项，{(c:4),(f:4),(b:3),(p:3)\r\n}表对应项的出现频率。这个结果是排好顺序的首按频率从达到小排序按照字母顺序排序需要注意的是这里的排序非常重要，\r\n后个事务中的项都要按照这个顺序进行排列，这个是有效合并重复路径的前提。处理之后的数据库记录为：

据一果建FP-Tree。1)一数建FP-Tree

第{c,f,a,m,p}

注中项序得项的。2)\r\n取数{c,f,a,b,m}

，不，它部分数据{c,f,a\r\n}。因，可用，只将加，即{(c:2),(f:2),(a:2)\r\n}

。后的，我们的，{(b:1),(m:1)}

，其，b为a，m为b。3)\r\n取数{f,b}复路存在但f点因，用f，个b作为f\r\n路{{f:3},(b:1)}意在的b节父为。4)四数{c,b,p}在，有c点发新{(c:3),(b:1),(p:1)}

。5)五数{c,f,a,m,p}路{(c:4),(f:4),(a:3),(m