数据挖掘 读书笔记

第1章引论

为什么进行数据挖掘

数据挖掘把大型数据集转换成知识。

案例：http://www.guokr.com/article/438117/
Google的Flu Trends(流感趋势)使用特殊的搜索项作为流感活动的指示器，比传统的系统早两周对流感活动作出评估。

什么是数据挖掘
数据中的知识发现

数据清理 ：消除噪声和删除不一致的数据

数据集成：多种数据源可以组合在一起

数据选择：从数据库中提取与分析任务相关的数据

数据变换：通过汇总或聚集操作，把数据统一成适合挖掘的形式

数据挖掘：基本步骤，使用智能方法提取数据模式

模式评估：根据魔种兴趣度度量，识别代表知识的真正有趣的模式

知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识

数据库数据

数据库管理系统(DBMS)，由一组内部相关的数据（库）和一组管理和存取数据的软件程序组成。关系数据库是表的汇集，每个表都包含一组属性（列或字段），并且存放大量元组（记录或行）。构建语义数据模型，如实体-联系（ER）数据模型。

数据仓库

数据仓库是一种用于长期存储数据的仓库，这些数据来自多个数据源，是经过组织的，以便支持管理决策。数据仓库的核心组件有四个：各源数据库，ETL，数据仓库，前端应用。如下图所示：

数据仓库用称作数据立方体的多维数据结构建模。数据仓库非常适合联机分析处理。OLAP操作包括下钻（drill-down）和上卷（roll-up）。

博文参考：http://www.cnblogs.com/muchen/p/5305658.html

事务数据

事务数据库的每个记录代表一个事务，如顾客的一次购物或一个用户的网页点击。通常，一个事务包含一个唯一的事务标识号（trans_ID）。AllElectronics的销售事务数据库sales表的片段：

trans_ID	商品ID的列表
T100	I1，I3，I8，I16
T200	I2，I8
…	…

sales表是一个嵌套关系，因为属性“商品ID的列表”包含商品的集合。
作为分析者，你可能问“哪些商品一起销售的很好？”这种“购物篮数据分析”是你能够制定促销策略，将商品捆绑销售。

其他类型的数据

类型	例应用
时间相关或序列数据	历史记录、股票交易数据、时间序列和生物学序列数据
数据流	视频监控和传感器数据，他们连续播送
空间数据	地图
工程设计数据	建筑数据、系统部件或集成电路
超文本和多媒体数据	包括文版、图像、视频和音频数据
图和网状数据	如社会和信息网络
万维网	由Internet提供的巨星、广泛分布的信息存储库

具体应用：

就时间数据而言，可以挖掘银行数据的变化趋势，这可以帮助银行根据顾客流量安排出纳员。
可以挖掘股票交易数据，发现趋势，帮助你规划投资策略（例如，购买AllElectronics的股票的最佳时机）。
可以挖掘计算机网络数据，根据消息流的异常进行入侵检测。这种异常可以通过聚类、流模型的动态创建，或把当前的频繁模式与先前的比较发现。
使用空间数据，我们可以得到根据城市离主要公路的距离描述都市贫困率的变化趋势的模式。
可以考察空间对象集之间的联系，发现那些对象子集是空间自相关或关联的。
通过挖掘文本数据，如挖掘过去10年“数据挖掘”方面的文献，可以了解该领域热点课题的演变。
通过挖掘顾客对产品发表的评论（通常，以短文本信息提交），我们可以评估顾客的意见，了解产品被市场接受的程度。
由多媒体数据，我们可以挖掘图像，识别对象，并通过指派语义标号或标签对它们分类。
通过挖掘曲棍球运动的视频数据，可以检测对应于进球的视频序列。
Web挖掘可以帮助我们了解万维网信息的一般分布，刻画网页的特征，对网页进行分类，并发现Web的动态，以及不同网页、用户、社区和基于Web的活动之间的关联和联系。

可以挖掘什么类型的数据

特征化与区分

数据特征化（data characterization）是目标类数据的一般特性或特征的汇总。
例如AllElectronics的客户关系经理可能提出如下数据挖掘任务：“汇总一年之内在AllElectronics花费5000美元以上的顾客特征。”结果可能是顾客的概况，如年龄在40～50岁、有工作、有很好的信用等级。
数据区分（data discrimination）是将目标类数据对象的一般特性与一个或多个对比类对象的一般特性进行比较。
例如频繁购买计算机产品的顾客80%在20～40岁之间，受过大学教育；而不经常购买这种产品的顾客60%或者年龄太大或者太年轻，没有大学学位。

挖掘频繁模式、关联和相关性

频繁模式

频繁项集：如小卖部中被许多顾客频繁地一起购买的牛奶和面包。

频繁子序列：如顾客倾向于先购买便携机，再购买数码相机，然后再购买内存卡这样的模式

频繁子结构：能涉及不同的结构形式（例如，图、树或格），可以与项集或子序列结合在一起。如果一个子结构频繁地出现，则称它为（频繁）结构模式？

关联分析

buys(X,”computer”) ==> buys(X,”software”)[support=1%,confidence=50%]
X是变量，代表顾客。
50%的置信度（confidence）表示，如果一位顾客购买计算机，则购买软件的可能性是50%。
1%的支持度（support）表示，所分析的所有事务的1%显示计算机与软件一起被购买。
这个关联规则涉及单个重复的属性或谓词（即buys）。包含单个谓词的关联规则称作单维关联规则（single-dimensional association rule）。去掉谓词符号，上面的规则可以简单地写成：computer ==> software[1%, 50%]

age(X,”20..29”)∧income(X,”40K..49K”) ==> buys(X,”laptop”)[support=2%,confidence=60%]
这里涉及多个属性或谓词（即age，income和buys）的关联。采用多维数据库使用的属性，每个属性称作一个维，上面的规则可以称作多维关联规则（multidimensional association rule）。

用于预测分析的分类与回归

分类：找出描述和区分数据类或概念的模型（或函数），分类预测类别（离散的、无序的）标号。
如何提供导出的模型？

分类规则（即IF-THEN规则）、决策树、神经网络、朴素贝叶斯分类、支持向量机和k最近邻分类。
回归建立连续值函数模型，回归用来预测缺失的或难以获得的数值数据值，而不是（离散的）类标号。
相关分析（relevance analysis）可能需要在分类和回归之前进行，它视图识别与分类和回归过程显著相关的属性。我们将选取这些属性用于分类和回归过程，其他属性是不相关的，可以不必考虑。

聚类分析

聚类（clustering）与[分类与回归标记类的（训练）数据集]不同，聚类分析数据对象，而不考虑类标号。
对象根据最大化类内相似性、最小化类间相似性的原则进行聚类或分组。

离群点分析

数据集中可能包含一些数据对象，他们与数据的一般行为或模型不一致。这些数据对象是离群点（outlier）。大部分数据挖掘方法都将离群点视为噪声或异常而丢弃。然而，在一些应用中（例如，欺诈检测），罕见的事件可能比正常出现的事件更令人感兴趣。离群点数据分析称作离群点检测或异常挖掘。

使用什么技术

统计学
推理统计学用某种方式对数据建模，解释观测中的随机性和确定性，并用来提取关于所考察的过程或总体的结论。统计假设检验使用实验数据进行统计判决。如果结果不大可能随机出现，则称它为统计显著的。
机器学习
考察计算机如何基于数据学习（或提高它们的性能）。其主要研究领域之一是，计算机程序基于数据自动地学习识别复杂的模式，并做出智能的决断。
- 监督学习（supervised learning）基本是分类的同义词。学习中的监督来自训练数据集中标记的实例。如：邮政编码识别问题。
- 无监督学习（unsupervised learning）本质上是聚类的同义词。学习过程是没有监督的，因为输入实例没有类标识。
- 半监督学习（semi-supervised learning）在学习模型中，它使用标识和未标识的实例。在方法中，标识的实例用来学习类模型，而未标识的实例用来进一步改进类边界。
- 主动学习（active learning）主动学习方法可能要求用户对一个可能来自未标识的实例集或由学习程序合成的实例进行标识。
数据库系统与数据仓库
……
信息检索
信息检索（IR）是搜索文档或文档中信息的科学。信息检索的典型方法是采用概率模型。一个文本文档集的主题可以用词汇表上的概率分布建模，称作主题模型。

面向什么类型的应用

商务智能
BI技术提供商务运作的历史、现状和预测视图，例子包括报告、联机分析处理（依赖于数据仓库和多维数据挖掘）、商务业绩管理、客户关系管理（聚类）、竞争情报、标杆管理和预测分析。
Web搜索引擎
本质上是大型数据挖掘应用

技术应用

爬行决定应该爬过哪些页面和爬行频率

索引选择被索引的页面和决定构建索引的范围

搜索确定如何排列各个页面、加载何种广告、如何把搜索结果个性化。当用户提交一个查询时，搜索引擎试图使用用户的简况和他的查询历史推断查询的环境，以便快速地返回更加个性化的回答

技术	应用
爬行	决定应该爬过哪些页面和爬行频率
索引	选择被索引的页面和决定构建索引的范围
搜索	确定如何排列各个页面、加载何种广告、如何把搜索结果个性化。当用户提交一个查询时，搜索引擎试图使用用户的简况和他的查询历史推断查询的环境，以便快速地返回更加个性化的回答

数据挖掘的主要问题

挖掘方法

挖掘各种新的知识类型：从数据特征化与区分到关联与相关性分析、分类、回归、聚类、离群点分析、序列分析以及趋势和演变分析。
挖掘多维空间中的知识：在不同抽象层的多维（属性）组合中搜索有趣的模式。这种挖掘称作（探索式）数据挖掘。
数据挖掘：通过集成来自多学科的新方法可以显著增强数据挖掘的能力。例如，自然语言文本数据挖掘，把数据挖掘方法与信息检索和自然语言处理的方法融合在一起。
提升网络环境下的发现能力：大部分数据对象驻留在链接或互连的环境中，多个数据对象之间的语义链接可以用来促进数据的挖掘。
处理不确定性、噪声或不完全数据
模式评估和模式或约束指导的挖掘：数据挖掘过程产生的所有模式并非都是有趣的。需要一种技术来评估基于主观度量所发现的模式的兴趣度。
用户交互
有效性与伸缩性

数据挖掘算法的有效性和可伸缩性：为了有效地从多个数据库或动态数据流的海量数据中提取信息，数据挖掘算法的运行时间必须是可预计的、短的和可以被应用接受的。
并行、分布式和增量挖掘算法：首先把数据划分成若干“片段”，每个片段并行处理，搜索模式。并行处理可以交互，来自每部分的模式最终合并在一起。
云计算和集群计算使用分布和协同的计算机处理超大规模计算任务
数据类型的多样性

从结构化数据到半结构化数据和无结构数据
从静态的数据到动态的数据流
从简单的数据对象到时间数据、生物序列数据、传感器数据、空间数据、超文本数据、多媒体数据、Web数据和社会网络数据。
挖掘动态的、网络的、全球的数据库：众多数据源被国际互联网连接起来，形成一个庞大的、分布的和易购的全球信息系统和网络。
数据挖掘与社会

数据挖掘的社会影响
保护隐私的数据挖掘：个人信息隐私
无形的数据挖掘：在线购买商品时，用户可能并未察觉商店可能正在收集顾客的购买模式数据。

第2章认识数据

数据对象与属性类型

属性、维度、特征和变量可以互换。机器学习文献倾向于使用术语特征，统计学家更愿意使用术语变量，数据库和数据挖掘的专业人士一般使用术语属性。

属性	定义
标称属性（nominal attribute）	值是一些符号或事物的名称，每个值代表某种类别、编码或状态，因此标称又被看做是分类的，并不具有有意义的序。
二元属性（binary attribute）	是一种标称属性，又称布尔属性：0或1
序数属性（ordinary attribute）	其可能的值之间具有有意义的序或秩评定（ranking），中心趋势可以用众数和中位数表示，但不能定义均值
数值属性（numeric attribute）	1.区间标度（interval-scaled）用相等的单位尺度度量 2.比率标度属性（retio-scaled）是具有固定零点的数值属性。或比率标度
离散属性与连续属性	离散属性具有有限或无限可数个值

数据的基本统计描述

中心趋势度量

均值
均值对极端值很敏感，为了抵消少数极端值的影响，可以使用截尾平均（trimmed mean）。
中位数
对于倾斜（非对称）数据，数据中心的更好度量是中位数（median）。
众数
可能最高频率对应多个不同的众数，1个-单峰的（unimodal），2个-双峰的（bimodal），3个-三峰的（trimodal）
中列数
正倾斜-众数出现在小于中位数的值上；负倾斜-众数出现在大于中位数的值上。

度量数据散布

极差MAX()-MIN()
四分位极差（IQR）=Q3-Q1
离群点：落在第3个四分位数之上或第1个四分位数之下至少1.5 IQR*
五数概括：中位数、四分位数Q1和Q3、最小和最大观测值组成
箱线图（boxplot）：盒子外两条线延伸到最小和最大观测值。（当最高/低值超过1.5 x IQR时，两条线不超过1.5 x IQR）
方差和标准差

数据基本统计的图形

分位数图
分位数-分位数图
直方图
散点图与数据相关

数据可视化

1. 基于像素

一维值的简单方法是使用像素，其中像素的颜色反映该维的值。

2. 几何投影

散点图，使用不同的颜色或形状表示不同的数据点，可以增加第三维。
散点图矩阵，对于n维数据集，散点图矩阵是二维散点图的n x n网格。
平行坐标（parallel coordinates），绘制n个等距离、相互平行的轴，每维一个。

3. 层次可视化

把所有维划分成子集（子空间），这些子空间按层次可视化。
① 世界中的世界
② 树图

4. 可视化复杂对象和关系-标签云

度量数据的相似性和相异性

1. 数据矩阵和相异性矩阵

数据矩阵（data-matrix）或称对象-属性结构：这种数据结构用关系表的形式或n x p(n个对象 x p个属性)矩阵存放n个数据对象。
数据矩阵由两种实体组成，即行（代表对象）和列（代表属性）。因而，数据矩阵经常被称为二模（two-mode）矩阵。
相异性矩阵（dissimilarity matrix）或称对象-对象结构：存放n个对象两两之间的邻近度（proximity）。
相异性矩阵只包含一类实体，因此被称为单模（one-mode）矩阵。

2. 标称属性的近邻性度量

根据不匹配率：d(i,j)=(p-m)/p
m 是匹配的数目（即i和j取值相同状态的属性数），而p是刻画对象的属性总数。

3. 二元属性的邻近度度量

对于对称的二元属性，每个状态都同样重要，基于对称二元属性的相异性称作对称的二元相异性。
对于非对称的二元属性，每个状态不是同样重要的，称作非对称的二元相异性。

4. 数值属性的邻近度度量

欧几里得距离 L2范数
曼哈顿距离 L1范数
闵可夫斯基距离（Minkowski distance）又称Lp范数（norm）

5. 序数属性的邻近度度量

序数属性的处理与数值属性的非常类似。序数属性的相似值由相异性得到：sim(i,j)=1-d(i,j)
巴拉巴拉

1
2
3


#### 6. 混合类型属性的相异性
难

7. 余弦相似性

文档用以千计的属性表示，每个记录文档中一个特定词或短语的频率。每个文档都被一个所谓的词频向量（term-frequency vector）表示。
词频向量通常很长，并且是稀疏的（即，他们有许多是0值）。使用这种结构的应用包括信息检索、文本文档聚类、生物学分类和基因特征映射。

余弦相似性可以用来比较文档，或针对给定的查询词向量对文档排序。
sim(x,y)=x*y/(||x|| ||y||)

第3章数据预处理

数据质量的三要素：准确性、完整性和一致性
影响数据质量的另外两个因素是可信性和可解释性。

数据清理（data cleaning）

通过填写缺失值，平滑噪声数据，识别或删除离群点，并解决不一致性来“清理”数据。

缺失值

方法	具体做法
1. 忽略元组	① 当缺少类标号时通常这么做 ② 除非元组有多个属性缺少值
2. 人工填写缺少值	费时，数据集大，缺失多时，该方法不可用
3. 使用一个全局常量填充	如”Unknown”，方法简单，但并不十分可靠
4. 使用属性的中心度量（均值或中位数）	对称数据分布应该使用均值，倾斜数据分布应该使用中位数
5. 使用与给定元组属同一类的所有样本的属性均值或中位数	如果将顾客按credit_risk分类，则用相同信用风险的顾客的平均首入替换income中的缺失值
6. 使用最有可能的值填充	用回归、贝叶斯形式化方法的基于推理的工具或决策树归纳确定利用数据集中其他顾客的属性，构造一棵决策树，来预测income的缺失值

方法(3)-方法(6)使数据有偏，填入的值可能不正确，方法(6)是最流行的方法。

噪声数据

被测量的变量的随机误差或方差。如何“光滑”数据？

方法	具体做法
分箱（binning）	1. 划分为（等频的）箱；2. 用箱均值（边界）光滑；
回归（regression）	1. 线性回归：找出拟合两个属性的“最佳”直线，使得一个属性可以用来预测另一个 2. 多元线性回归：涉及的属性多于2个，并且数据拟合到一个多维曲面
离群点分析（outlier analysis）	通过如聚类来检测离群点，落在簇集合之外的值被视为离群点

数据清理过程

数据清理的第一步是偏差检测：人为数据输入错误、有意的错误（不愿意泄露自己的信息）、数据退化（过时的地址）、不一致的数据表示和编码的不一致。偏差检测和数据变换（纠正偏差）的两步过程迭代执行。这一过程容易出错并且费时。

工具	应用
数据清洗工具（data scrubbing tool）	依赖于分析和模糊匹配技术。
数据审计工具（data auditing tool）	通过分析数据发现规则和联系，并检测违反这些条件的数据来发现偏差。使用统计分析来发现相关性，或通过聚类识别离群点。
数据迁移工具（data migration tool）
ETL（Extraction/Transformation/Loading）	工具允许用户通过图形用户界面（GUI）说明变换。

数据集成（data integration）

1. 实体识别问题

数据分析任务多半设计数据集成，数据集成将多个数据源中的数据合并，存放在一个一致的数据存储中，如数据仓库。这些数据源可能包括多个数据库、数据立方体或一般文件。

2. 冗余和相关性分析

给定两个属性，相关分析可以根据可用的数据，度量一个属性能多大程度蕴涵另一个。

属性分析方法

标称数据 X2卡方检验

数值属性 相关系数（correlation coefficient），如果A和B是相关的，并不意味着A导致B或B导致A

数值属性 协方差（covariance）

属性	分析方法
标称数据	X2卡方检验
数值属性	相关系数（correlation coefficient），如果A和B是相关的，并不意味着A导致B或B导致A
数值属性	协方差（covariance）

3. 元组重复

除了检测属性间的冗余外，还应当在元组级检测重复。

4. 数据值冲突的检测与处理

同一实体，来自不同数据源的属性值可能不同。这可能是因为表示、尺度或编码不同。
重量单位/货币单位/学分制度

数据归约（data reduction）

归约策略-得到数据集的简化表示方法

维归约（dimensionality reduction）
减少所考虑的随机变量或属性的个数 1. 数据压缩技术 （小波变换和主成分分析）
2. 属性子集选择 （去掉不相关的属性）
3. 属性构造 （从原来的属性集导出更有用的小属性集）

数据归约（numerosity reduction）
用替代的、较小的数据表示形式替换原数据 4. 参数模型（回归和对数线性模型）
5. 非参数模型（直方图、聚类、抽样或数据聚集）

数据压缩（data compression）
使用变换，以便得到原数据的归约或“压缩”表示 6. 无损的：如果原数据能够从压缩后的数据重构
7. 有损的：如果只能近似重构原数据

归约策略-得到数据集的简化表示	方法
维归约（dimensionality reduction）减少所考虑的随机变量或属性的个数	1. 数据压缩技术（小波变换和主成分分析） 2. 属性子集选择（去掉不相关的属性） 3. 属性构造（从原来的属性集导出更有用的小属性集）
数据归约（numerosity reduction）用替代的、较小的数据表示形式替换原数据	4. 参数模型（回归和对数线性模型） 5. 非参数模型（直方图、聚类、抽样或数据聚集）
数据压缩（data compression）使用变换，以便得到原数据的归约或“压缩”表示	6. 无损的：如果原数据能够从压缩后的数据重构 7. 有损的：如果只能近似重构原数据

1. 小波变换和主成分分析

如果看了此文你还不懂傅里叶变换，那就过来掐死我吧
 傅立叶分析和小波分析之间的关系
 主成分分析（PCA）原理详解

2. 属性子集选择

决策树算法（ID3、C4.5和CART）。当决策树归纳用于属性子集选择时，不出现在树中的所有属性假定是不相关的。出现在树中的属性形成归约后的属性子集。
这些方法的结束条件可以不同，该过程可以使用一个度量阈值来决定何时停止属性选择过程。

3. 属性构造

在某些情况下，可能基于其他属性创建一些新属性。这种属性构造可以帮助提高准确性和对高维数据结构的理解。

4. 参数模型：回归和对数线性

5. 非参数模型

方法	具体实施
直方图	等宽：每个桶的宽度区间是一致的等频（等深）：每个桶的频率粗略的为常数
聚类	用数据的簇代表替换实际数据
抽样	用数据小得多的随机样本（子集）表示大型数据集

数据变换或数据离散化

如果顾客数据包含年龄和年薪属性，年薪属性的取值范围可能比年龄大得多。如果属性未规范化，则距离度量在年薪上所取的权重一般要超过年龄所取的权重。
离散化和概念分层，属性的原始值被区间或较高层的概念所取代。


光滑（smoothing）	分箱、回归、聚类
属性（特征）构造	由给定的属性构造新的属性并添加到属性集中
聚集	计算日销售——>月、年销售数据
规范化用较小的单位表示属性将导致该属性具有较大值域，因此趋向于使这样的属性具有较大的影响或较高的权重。为了避免这种情况，数据应该规范化或标准化，使之落入一个小的区间，如0.0~1.0	*最小-最大规范化、z-score* 规范化、小数定标规范化** ① 神经网络后向传播算法规范化有助于加快学习阶段的速度 ② 基于距离的方法规范化有助于防止具有较大初始值域的属性（income）与具有较小初始值域的属性（如二元属性）相比权重过大
离散化	分箱基于指定的箱个数的自顶向下的分裂技术，用箱的均值或中位数替代箱中的每个值直方图可以递归地用于每个分区，自动地产生多级概念分层聚类决策树监督的，因为是用了类标号，选择最小化熵的属性的值作为划分点，并递归地划分结果区间，得到分层离散化相关分析 ChiMerge是一种基于卡方检验的离散化方法
标称数据产生概念分层	如 street，可以泛化到较高的概念层，如 city 或 country

第1章 引论