数据挖掘笔记
数据挖掘（KDD）
（1）数据清理（消除噪声和删除不一致数据）
（2）数据集成（多种数据源可以组合在一起）
（3）数据选择（从数据库中提取与分析任务相关的数据）
（4）数据变换（通过汇总或聚集操作，把数据变换和统一成适合挖掘的形式）
（5）数据挖掘（基本步骤，使用智能方法提取数据模式）
（6）模式评估（根据某种兴趣度度量，识别代表知识真正有趣的模式）
（7）知识表示（使用可视化和知识表示技术，向用户提供挖掘的知识）
机器学习
监督学习（分类）：学习中的监督来自训练数据集作用标记的实例。
无监督学习（聚类）：学习过程是无监督的，因为输入实例没有类标记，我们可以使用聚类发现数据中的类。
半监督学习：机器学习技术，在学习模型时，它使用标记的和未标记的实例。在一种方法中，标记的实例用来学习类模型，而未标记的实例用来进一步改进类
边界。可以把属于一个类的实例看做正实例，而属于另一个类的实例为负实例。
主动学习：让用户在学习过程中扮演主动角色。主动学习方法要求用户对一个可能来自未标记的实例集或由学习程序合成的实例进行标记。给定可以要求标记
的实例数量的约束，目的是通过主动地从用户获取知识来提高模型质量。
数据库系统研究关注为单位和最终用户创建、维护和使用数据库，特别是已建立了数据建模、查询语言、查询处理和优化方法、数据存储以及索引和存取方法
的公认原则。
信息检索：
搜索文档或文档中信息的科学。文档可以是文本或多媒体，并且可能驻留在Web上。
信息检索与数据库系统的差别：信息检索假定所搜索的数据是无结构的；信息检索查询主要用关键词，没有复杂的结构。
主题模型：一个文本文档集的主题可以用词汇表上的概率分布建模。
数据挖掘应用：商务智能和搜索引擎。
商务智能提供商务运作的历史、现状和预测视图，例子包括报告、联机分析处理、商务业绩管理、竞争情报、标杆管理和预测分析。商务智能的联机分析处理
依赖于数据仓库和多维数据挖掘。分类和预测技术是商务智能预测分析的核心。
搜索引擎：专门的计算机服务器，在Web上搜索信息，用户查询搜索结果用一张表返给用户。采样可以包含网页、图像和其他类型的文件。它不同于网络目录（
由人工编辑管理），而搜索引擎是按算法运行的，或者是算反和人工输入的混合。本质上是大型挖掘应用，包含爬行（计算机程序，系统、自动浏览网页）、
索引和搜索。
数据挖掘主要问题
挖掘方法
挖掘各种新的知识类型：从数据特征化与区分到关联与相关性分析、分类、回归、聚类、离群点分析、序列分析以及趋势和演变分析。
挖掘多维空间中的知识：在大型数据集中搜索知识时，我们可能在不同抽象层的多维组合中搜索有趣模式，称之为多维数据挖掘
用户界面
交互挖掘：允许用户在挖掘过程中动态的改变搜索的聚焦点，根据返回的结果提炼挖掘请求
结合背景知识：用于模式评估，指引搜索有趣的模式。
数据挖掘结果的表示和可视化：系统采用有表达能力的知识表示，以及用户友好界面和可视化技术。
有效性和可伸缩性
为了有效的从多个数据库或动态数据流的海量数据中提取信息，数据挖掘算法必须是有效的和可伸缩的，也就是运行时机必须是可预计的、短的和可以被应用接受的。
并行、分布式和增量挖掘算法：首先把数据划分成若干“片段”，每个片段并行处理，搜索模式。并行处理可以交互，来自每部分的模式最终合并在一起。
数据库类型的多样性
处理复杂的数据类型
挖掘动态的、网络的、全球的数据库：互联网挖掘、多源数据挖掘和信息网络挖掘。
数据挖掘与社会
保护隐私的数据挖掘
无形的数据挖掘：把数据挖掘合并到它们的组件中，提高功能和性能。用户不需要数据挖掘算法的任何知识，只需点击鼠标就能进行数据挖掘或使用数据挖掘。
属性：数据字段，表示数据对象的一个特征。属性、维、特征和变量可以互换地使用。
标称属性：值是一些符号或事物的名称。又被看做是分类的。在计算机科学中，这些值也被看做是分类的。
二元属性：一种标称属性，只有两个类别或状态：0或1,0代表示该属性不出现，而1表示出现。
序数属性：可能的智之间具有意义的序或秩评定，但是相继值之间的差别是未知的。序数属性得到中心趋势可以用众数和中位数表示，但是不能定义均值。
注意：标称、二元和序数的属性都是定性的。它们描述对象的特征，而不给出实际大小或数量。
数值属性：定量的，计她是可度量的量，用整数或实数值表示。数值属性是可以区间标度的或比率标度的。
区间标度属性；用相等的单位尺度度量。区间属性的值有序，可以为正、0或负。
比率标度属性是具有零点的数值属性。也就是说，如果度量是比率标度的，则我们可以说一个值是另一个的倍数。此外，这些值是有序。
离散属性具有有限或无限可数个值，可以具有数值值。如果一个属性可能的值集合是无限的。但是可以建立一个与自然数的一一对应，则这个属性是无限可数的。
截尾均值：丢弃高低端值后的均值，对于倾斜（非对称）数据，数据中心更好度量是中位数。在概率论和统计学，中位数一般用于数据数值。
具有一个、两个、三个众数的数据集合分别称为单峰、双峰和三峰的。
具有两个或者更多众数的数据是多峰的，在另一种极端情况下，如果每个数据值仅出现一次，则它没有众数。
MapReduce编程模型
迭代（iteration），遍历输入数据，并将之解析成key/value对。
将输入key/value对映射（map）成另外一些key/value对。
依据key对中间数据进行数组（grouping）。
以组为单位对数据进行归约（reduce）。
迭代，将最终产生的key/value对保存到输出文件。
Hadoop是一个数据处理框架，而在当前大多数应用中处理数据的主力是标准的关系数据库。SQL是针对结构化数据设计的，而Hadoop最初的许多应用针对的是
文本这种非结构化数据。SQL是一种查询语言，将Hadoop作为其执行引擎。
具体比较
1.用向外扩展代替向上扩展
Hadoop的设计就是为了能够在商用PC集群上实现向外扩展的架构。添加更多资源，对于Hadoop集群就是增加更多的机器。一个Hadoop群的标配是十至数百台计
算机。
2.用键/值对代替关系表
关系数据库的一个基本原则是让数据按某种模式存放在具有关系型数据结构的表中。大数据集往往是非结构化或半结构化的。Hadoop中的来源可以有任何形式
，但最终会转化为键/值对以供处理。
3.用函数式编程（MapReduce)代替声明式查询(SQL)
SQL从根本上说是一个高级声明式语言，查询数据的手段是，声明想要的查询结果并让数据库引擎判定如何获取数据。在MapReduce中，实际的数据处理步骤是
由开发者指定的，它很类似于SQL引擎的一个执行计划。SQL使用查询语句，而MapReduce则使用脚本和代码。利用MapReduce可以用比SQL查询更为一般化的数
据处理方式。
4.用离线批处理代替在线处理
Hadoop是专为离线处理和大规模数据分析而设计的，它并不适合哪种对几个记录随机读写的在线事务处理模式。Hadoop最适合一次写入，多次读取的数据存储
要求。
例:统计一组文档中每个单词出现的次数
define wordCount as MultiSet;
for each document in documentSet{
T=tokenize(document);
for each token in T{
wordCount[token]++;
}
display(wordCount);
}
这个程序只适合处理少量文档，一旦文档数量激增，就不能胜任。例如想编写一个垃圾邮件过滤器来获取接收到的几百万封垃圾邮件中经常使用的单词。使用
单台计算机遍历所有文档将会非常费时。重写程序，让工作可以分布在多台机器上，每台机器处理这些文档的不同部分。当所有机器都完成时，第二个处
理阶段将合并这些结果。第一阶段要分布到多台机器上去的伪代码为：
define wordCount as Multiset;
for each document in documentSubset{
T=tokensize(document);
for each token in T{
wordCount[token]++;
}
sendToSecondPhase(wordCount);
第二阶段的伪代码为：
define totalWordCount as Mutiset;
for each wordCount received from firstPhase{
multisetAdd(totalWordCount,wordCount);
}
}
该程序的另一个缺点是Wordcount（和totalwordcount）被存储在内存中。当处理大型文档集时，一个特定单词的数量就会超过一台机器的内存容量。
为了使单词统计程序工作在一个分布式计算机集群上，需要添加以下功能。
（1）存储文件到许多台计算机上
（2）编写一个基于磁盘的散列表，使得处理不受存容量限制。
（3）划分来自第一阶段的中间数据（即WordCount）
（4）洗牌这些分区到第二阶段中合适的计算机上。
MapReduce程序的执行分为两个主要阶段，为mapping和reducing。每个阶段均定义为一个数据处理函数，分别被称为mapper和redcucer。在mapping阶段，MapR
educe获取输入数据并将数据单元装入mapper，在reducing阶段，reducer处理来自mapper的所有输出，并给出最终结果。
简而言之，mapper意味着将输入进行过滤盒转换，使reducer可以完成聚合。MapReduce的设计建立在编写可扩展，分布式程序的丰富经验之上。
MapReduce框架中编写的应用程序就是定制化mapper和reducer的过程，其数据流如下
（1）应用的输入必须组织为一个键/值对的列表List（
）。输入格式看起来是不受输入约束的，但在实际中它非常简洁。用于处理多个文件的输入格式通常为list（
。用于处理日志文件这种大文件的输入格式list(Integer line_number,String log_event>)。
（2）含有键/值对的列表被拆分，进而通过调用mapp的map函数对每个单独的键/值对
k1,v1>对并将之放入
这种转换必须是封闭的，使得输出仅依赖于一个单独的键/值对。
对于单词统计，
的列表。基数值将在后续的阶段聚合，我们可以输出一个有重复条目的
散点图是确定两个数值变量之间看上去是否存在联系、模式或趋势的最有效的图形方法之一。为构造散点图，每个值对视为一个代数坐标对，并作为一个点在
平面上。
散点图是一种观察双变量数据有用的方法，用于观察点簇和离群点，或考察相关联系的可能性。两个属性X和Y,如果一个属性蕴含另一个，则它们是相关的。
基本数据描述（如中心趋势度量和散度度量）和图形统计显示(如分位数图、直方图和散点图)
提供了数据总体情况的有价值的洞察。由于有助于识别噪声和离群点，所以它们对数据清理特别有用。
数据可视化旨在通过图形表示清晰有效的表达数据。
基于像素的可视化技术
像素的颜色反映该维的值。对于一个m维数据集，基于像素的技术在屏幕上创建m个窗口。每维一个。记录的m个维值映射到这些窗口中对应位置上的m个像素，
像素的颜色反映对应的值。
在窗口内，数据值按所有窗口共用的某种全局序安排。全局序可以用一种对手头任务有一定意义方法，通过对所有记录排序得到。
在基于像素的技术中，数据记录也可以按查询依赖的方法排序。例如，给定一个点查询，我们可以把所有记录按照与该点查询的相似性的递减序排序。
几何投影可视化技术
帮助用户发现多维数据集的有趣投影。首要挑战是设法解决如何在二维显示上可视化高维空间。
散点图使用笛卡尔坐标显示二维数据点。使用不同的颜色或形状表示不同的数据点，可以增加第三维。对于维数超过4的数据集，散点图一般不太有效。散点图矩阵是散点图的一种有用扩充。对于n维数据集，散点图矩阵是二维散点图的nxn网格，提供给每个维与所有其他维的可视化。
