数据挖掘学习笔记一：引论

数据挖掘（又称从数据中发现知识，KDD）
例1.1 数据挖掘把大型数据集转换成知识。Google的Flu Trends（流感趋势）使用特殊的搜索项作为流感活动的指示器。它发现了搜索流感相关信息的人数与实际具有流感症状的人数之间的紧密联系。当与流感相关的所有搜索都聚集在一起时，一个模式就出现了。使用聚集的搜索数据，Google的Flu Trends可以比传统的系统早两周对流感活动作出评估。
数据挖掘 == 数据中的知识发现。只是发现的过程由一下步骤的迭代序列组成：

1. 数据清理（消除噪声和删除不一致数据）
2. 数据集成（多种数据源可以组合在一起）
3. 数据选择（从数据库中提取与分析人物相关的数据）
4. 数据变换（通过汇总和聚集操作，把数据变换和统一成适合挖掘的形式）
5. 数据挖掘（基本步骤，使用智能方法提取数据模式）
6. 模式评估（根据某种兴趣度度量，识别代表知识的真正有趣的模式）
7. 知识表示（使用可视化和知识表示技术，向用户提供挖掘的知识）

广义的数据挖掘功能的观点：数据挖掘是从大量数据中挖掘有趣模式和知识的过程。
数据源包括数据库、数据仓库、Web、其他信息存储库或动态地流入系统的数据。

1.3 可以挖掘什么类型的数据

数据库数据，数据仓库数据，事务数据，其他类型的数据

1.3.1 数据库数据

例1.2 AllElectronics的关系数据库。本书虚构的AllElectronics商店用于解释概念。该公司用下列关系表描述：customer，item，employee和breanch。

• 关系customer由一组描述顾客信息的属性组成，包括顾客的唯一标识号（cust_ID）、顾客的姓名、地址、年龄、职业、年收入、信用信息、类别等。
• 关系employee，branch和item都包含一组属性，描述这些实体的性质。
• 表也可以用来表示多个实体之间的联系。在例子中，这种表包括purchases（顾客购买商品，创建一个由雇员处理的销售事务）、item_sold（给定事务销售的商品列表）和work_at（雇员在AllElectronics的一个部门工作）。

customer	(cust_ID,name,address,age,occupation,annual_income,credit_information,category,...)
item		(item_ID,brand,category,type,price,place_made,supplier,cost,...)
employee	(empl_ID,name,category,group,group,salary,commission,...)
branch		(branch_ID,name,address,...)
purchases	(trans_ID,cust_ID,empl_ID,date,time,method_paid,amount)
item_sold	(trans_ID,item_ID,gty)
works_at	(empl_ID,branch_ID)

假设你的工作是分析AllElectronics的数据。通过使用关系查询，你可以提这样一个问题：“显示一个列有上个季度销售的所有商品的列表”。关系查询语言也可以包含聚合函数，如sum、avg（平均）、count、max（最大）和min（最小）。这些使得你可以问“现实上个月按部门分组的总销售”、“多少销售事务出现在12月份”或“哪一位销售人员的销售量最高”这样的问题。

当数据挖掘用于关系数据库时，你可以进一步搜索趋势或数据模式。例如，数据挖掘系统可以分析顾客数据，根据顾客的收入、年龄和以前的信用信息预测新顾客的信用风险。数据挖掘系统也可以检测偏差：例如，与以前的年份相比，哪些商品的销售出人预料。可以进一步考察这种偏差：例如，数据挖掘可能发现这些商品的包装的变化，或价格的大幅度提高。
关系数据库是数据挖掘的最常见、最丰富的信息源，因此它是我们数据挖掘研究的一种主要数据新式。

1.3.2 数据仓库 假设AllElectronics是一个成功的跨国公司，分部遍布全世界。每个分部都有一组自己的数据库。AllElectronics的总裁要你提供公司第三季度每种类型的商品及每个分部的销售分析。这是一项困难的任务，特别是当相关数据散布在多个数据库，物理地驻留在许多站点时尤其如此。
如果AllElectronics有一个数据仓库，该任务将是容易的。 数据仓库是一个从多个数据源收集的信息存储库，存放在一致的模式下，并且通常驻留在单个站点上。数据仓库通过数据清理、数据变换、数据集成、数据装入和定期数据刷新来构造。
为便于决策，数据仓库中的数据围绕主题（如顾客、商品、供应商和活动）组织。数据存储从历史的角度（如过去的6~12个月）提供信息，并且通常是汇总的。例如，数据仓库不是存放每个销售事物的细节，而是存放每个商店、每类商品的销售事务的汇总，或汇总到较高层次，即每个销售地区、每类商品的销售事务的汇总。
通常，数据仓库用称作数据立方体（data cube）的多维数据结构建模。其中，每个维对应于模式中的一个或一组属性，而每个单元存放某种聚集度量值，如count或sum(sales_amount)。数据立方体提供数据的多维视图，并允许预计算和快速访问汇总数据。

例1.3 AllElectronics的数据立方体。AllElectronics的汇总销售数据的数据立方体有三个维：address（城市值芝加哥、纽约、多伦多、温哥华），time（季度值Q1、Q2、Q3、Q4），item（商品类型值家庭娱乐、计算机、电话、安全）。存放在立方体的每个单元的聚集值是sales_amount（单位：千美元）。例如，在第一季度Q1，与安全系统相关的商品在温哥华的总销售为400，存放在单元<温哥华,Q1,安全>中。其他立方体可以用于存放每个维上的聚集和，对应于使用不同的SQL分组的道德聚集值（例如，每个城市和季度的，或每个季度和商品的，或每一微的总销售量）。

通过提供多维数据视图和汇总数据的与计算，数据仓库非常适合联机分析处理。OLAP操作的例子包括下钻（drill-down）和上卷（roll-up），它们允许用户在不同的汇总级别观察数据。
例如，可以对按季度汇总的销售数据下钻，观察按月汇总的数据。类似的，可以按城市汇总的销售数据上卷，观察按国家汇总的数据。
多维数据挖掘（又称探索式多维数据挖掘）以OLAP风格在多维空间进行数据挖掘。也就是说，在数据挖掘中，允许在各种粒度进行多维组合探查，因此更有可能发现代表知识的有趣模式。

1.3.3 事务数据 一般地说，事务数据库的每个记录代表一个事务，如顾客的一次购物、一个航班订票，或一个用户的网页点击。通常，一个事务包含一个唯一的事务标识符（trans_ID），以及一个组成事物的项（如，交易中购买的商品）的列表。事务数据库可能有一些与之相关联的附加表，包含关于事物的其他信息，如商品描述、关于销售人员或部门等的信息。

例1.4 AllElectronics的事务数据库。食物可以存放在表中，每个事务一个记录。
AllElectronics的书屋数据库的片段：

trans_ID	商品ID的列表/th>
T100	I1,I3,I8,I16
T200	I2,I8
...	...

sales表是一个嵌套关系，因为属性“商品ID的列表”包含商品的集合。 作为AllElectronics数据库的分析者，你可能问“哪些商品一起销售得很好？”。这种“购物篮数据分析”使你能够指定促销策略，将商品捆绑销售。
例如，有了“打印机与计算机经常一起销售”的知识，你可以向购买指定计算机的顾客以较大的折扣（甚至免费）提供魔种打印机，以期销售更多较贵的计算机（通常比打印机更贵）。传统的数据库系统不能进行购物篮数据分析。事务数据上的数据挖掘可以通过挖掘频繁项集来做这件事。频繁项集是频繁地一起销售的商品的集合。

1.3.4 其他类型的数据 除关系数据库数据、数据仓库数据、事务数据外，还有许多其他类型的数据：

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

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

1.4 可以挖掘什么类型的模式

数据挖掘功能： 特征化与区分,频繁模式、关联和相关性区分,分类与回归,聚类分析,离群点分析
数据挖掘功能用于指定数据挖掘任务发现的模式。可分为两类：描述性（descriptive）和预测性（predictive）。

• 描述性挖掘任务刻画目标数据中数据的一般性质。
• 预测性挖掘任务在当前数据上进行归纳，以便做出预测。

1.4.1 类/概念描述：特征化与区分

数据可以与类或概念相关联。例如，在AllElectronics商店，销售的商品类包括计算机和打印机，顾客概念包括bigSpenders和budgetSpenders。用汇总的、间接地、精确地表达方式描述每个类和概念是有用的。这种类或概念的描述成为类/概念描述。这种描述可以通过下述方法得到：

1. 数据特征化，一般地汇总所研究类（通常称为目标类）的数据；
2. 数据区分，将目标类与一个或多个可比较类（通常称为对比类）进行比较；
3. 数据特征化和区分。

数据特征化（data characterization）是目标类数据的一般特征或特征的汇总。通常，通过查询来收集对应于用户指定类的数据。例如，为研究上一年销售增加10%的软件产品的特征，可以通过在销售数据库上执行一个SQL查询来手机关于这些产品的数据。
  数据特征化的输出可以用多种形式提供，例如饼图、条图、曲线、多维数据立方体和包括交叉表在内的多维表。结果描述也可以用广义关系或规则（称作特征规则）形式提供。
例1.5 数据特征化。AllElectronics的客户关系经理可能提出如下数据挖掘任务：“汇总一年之内在AllElectronics花费5000美元以上的顾客特征。”结果可能是顾客的概况，如年龄在40~50岁、有工作、有很好的信等级。数据挖掘系统应当允许用户在任意维下钻，如在occupation维下钻，以便根据这些顾客的职业类型来观察他们。
数据区分(data discrimination)是将目标类数据对象的一般特征与一个或多个对比类对象的一般特性进行比较。目标类和对比类可以由用户指定，而对应的数据对象可以通过数据库查询检索。例如，用户可能希望将上一年销售增加10%的软件产品与同一时期销售至少下降30%的软件产品进行比较。用于数据区分的方法与用于数据特征化的方法类似。
区分描述应当包括比较度量，以便帮助区别目标类和对比类。用规则表示的区分描述称为区分规则（discriminant rule）。
例1.6 数据区分。AllElectronics的客户关系经理可能想比较两组顾客——定期（例如，每月多于两次）购买计算机产品的顾客和不经常（例如，每年少于3次）购买这种产品的客户。结果描述提供这些顾客比较的情况，例如频繁购买计算机产品的顾客80%在20~40岁之间，受过大学教育；而不经常购买这种产品的顾客60%或者年龄太大或者太年轻，没有大学学位。沿着维下钻，如沿occupation维下钻，或添加新的维，如income_level维，可以帮助发现两类之间的更多区分特征。

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

频繁模式（frequent pattern）是在数据中频繁出现的模式。
存在多种类型的频繁模式，包括频繁项集、频繁子序列（又称序列模式）和频繁子结构。
频繁项集指频繁地在事务数据集中出现的商品的集合，如小卖部中被许多顾客频繁地一起购买的牛奶和面包。
频繁子序列，如顾客倾向于先购买便携机，再购买数码相机，然后再购买内存卡这样的模式就是一个频繁序列模式。
频繁子结构可能涉及不同的结构形式（例如，图、树或格），可以与项集或子序列结合在一起。如果一个子结构频繁地出现，则称它为（频繁）结构模式。挖掘频繁模式导致返现数据中有趣的关联和相关性。

例1.7 关联分析。假设作为AllElectronics的市场部经理，你想知道那些商品经常一块被购买（即，在相同的事务中）。从AllElectronics的事务数据库中挖掘出来的这种规则的一个例子是：
        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%]
假定给定涉及购买的AllElectronics关系数据库。数据挖掘系统还可以发现如下形式的规则：
        age(X,"20..29")∧income(X,"40K..49K") ==> buys(X,"laptop")[support=2%,confidence=60%]
这里涉及多个属性或谓词（即age，income和buys）的关联。采用多维数据库使用的属于，每个属性称作一个维，上面的规则可以称作多维关联规则（multidimensional association rule）。

通常，如果一个关联规则不能同时满足最小支持度阈值和最小置信度阈值，则该关联规则被认为是无趣的而被丢弃。
还可以做进一步分析，发现相关联的属性-值对之间的有趣的统计相关性(correlation)。

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

分类：找出描述和区分数据类或概念的模型（或函数），以便能够使用模型预测类标号未知的对象的类标号。导出模型是基于训练数据集（即，类标号已知的数据对象）的分析。该模型用来预测类标号未知的对象的类标号。
“如何提供导出的模型？”：分类规则（即IF-THEN规则）、决策树、数学公式或神经网络。
决策树是一种类似于流程图的树结构，其中每个节点代表在一个属性值上的测试，每个分支代表测试的一个结果，而输液代表类或者类分布。容易把决策树转换成分类规则。
当用于分类时，神经网络是一组类似于神经元的处理单元，单元之间加权连接。
还有很多构造分类模型的其他方法：朴素贝叶斯分类（我竟然打成了朴树被噎死）、支持向量机和k最近邻分类。
分类预测类别（离散的、无序的）标号，而回归建立连续值函数模型。
也就是说：回归用来预测缺失的或难以获得的数值数据值，而不是（离散的）类标号。
回归分析（regression analysis）是一种最长是用的数值预测的统计学方法。
回归也包含基于可用数据的分布趋势识别。
相关分析（relevance analysis）可能需要在分类和回归之前进行，它视图识别与分类和回归过程显著相关的属性。我们将选取这些属性用于分类和回归过程，其他属性是不相关的，可以不必考虑。

例1.8 分类与回归。假设作为AllElectronics的销售经理，你想根据对处销活动的三中反应，对商品的商品集合分类：好的反应，中等反应和没有反应。你想根据商品的描述特性，如price、brand、place_made和category，对这三类的每一种导出模型。结果分类将最大限度地区别每一类，提供有组织的数据集描述。
假设结果分类模型用决策树的形式表示。例如，决策树可能把price看做最能区分三个类的因素。该树可能揭示，除了price之外，帮助进一步区分每类对象的其他特征包括brand和place_made。这样的决策树可以帮助你理解给定促销活动的影响，并帮助你设计未来更有效的促销活动。
假设你不是预测顾客对每种商品反应的分类标号，而是想根据先前的销售数据，预测在AllElectronics的未来销售中每种商品的收益。这是一个回归分析的例子，因为所构造的模型将预测一个连续函数（或有序值）。

1.4.4 聚类分析

聚类（clustering）与[分类与回归标记类的（训练）数据集]不同，聚类分析数据对象，而不考虑类标号。在许多情况下，开始并不存在标记类的数据。可以使用聚类产生数据群组的类标号。对象根据最大化类内相似性、最小化类间相似性的原则进行聚类或分组。也就是说，对象的簇（cluster）这样形成，使得相比之下在同一个簇中的对象具有很高的相似性，而与其他簇中的对象很不相似。所形成的每个簇都可看做一个对象类，由它可以导出规则。聚类也便于分类法形成(taxonomy formation)，即将观测组织成类分层结构，把类似的时间组织在一起。
例1.9 聚类分析。可以在AllElectronics的顾客数据上进行聚类分析，识别顾客的同类子群。这些簇可以表示每个购物目标群。

1.4.5 离群点分析

数据集中可能包含一些数据对象，他们与数据的一般行为或模型不一致。这些数据对象是离群点（outlier）。大部分数据挖掘方法都将离群点视为噪声或异常而丢弃。然而，在一些应用中（例如，欺诈检测），罕见的事件可能比正常出现的事件更令人感兴趣。离群点数据分析称作离群点检测或异常挖掘。
可以假定一个数据分布概率模型，使用统计检验来检测离群点；
或者使用距离度量，将远离任何簇的对象视为离群点； 或者不使用统计或距离度量，基于密度的方法皆可以识别局部区域中的离群点。
例1.10 离群点分析。通过检测一个给定账号与正常的付费相比付款数额特别大，离群点分析可以发现信用卡欺骗性使用。离群点还可以通过购物地点和类型或购物频率来检测。

1.4.6 所有模式都是有趣的吗

“什么样的模式是有趣的？”

一个模式是有趣的（interesting），如果它：

1. 易于被人理解；
2. 在某种确信度上，对于新的或检验数据使有效的；
3. 是潜在有用的；
4. 是新颖的。

如果一个模式证实了用户寻求正式的某种假设，则它也是有趣的。
有趣的模式代表知识。
模式兴趣度的客观度量：

• 支持度（support）：support(X ==> Y) = P(X ∪ Y)
• 置信度（confidence）：confidence(X ==> Y) = P(Y|X)

            其他数据度量包括分类（IF-THEN）规则的准确率与覆盖率。
                一般而言，准确率告诉我们被一个规则正确分类的数据所占的百分比。
                覆盖率类似于“支持度”，告诉我们规则可以作用的数据所占的百分比。
主观兴趣度度量基于用户对数据的信念。这种度量发现模式是有趣的，如果他们是出乎意料的（与用户的信念相矛盾），或者提供用户可以采取行动的至关重要的信息。在后一种情况下，这样的模式成为可行动的（actionable）。意料之内的模式也可能是有趣的，如果他们证实了用户希望正式的假设，或与用户的预料相似。

“数据挖掘系统能够产生所有有趣的模式吗？”

“数据挖掘系统能够产生所有有趣的模式吗？” —— 涉及数据挖掘算法的完全性。

“数据挖掘系统能够仅产生有趣的模式吗？”

“数据挖掘系统能够仅产生有趣的模式吗？” —— 是数据挖掘的优化问题。

使用什么技术

统计学、机器学习、模式识别、数据库和数据仓库、信息检索、可视化、高性能计算……

1.5.1 统计学

统计学研究数据的手机、分析、解释和表示。数据挖掘与统计学具有天然联系。
统计模型是一组数学函数，它们用随机变量及概率分布刻画目标类对象的行为。

1.5.2 机器学习

机器学习考察计算机如何基于数据学习（或提高他们的性能）。其主要研究领域之一是，计算机程序基于数据自动地学习复杂的模式，并作出智能的决断。例如，一个典型的机器学习问题是为计算机编制程序，使之自动地识别邮件上的手写体邮政编码。
一些与数据挖掘高度相关的、经典的机器学习问题：

• 监督学习（supervised learning）基本上是分类的同义词。学习中的监督来自训练数据集中标记的实例。例如，在邮政编码识别问题中，一组手写邮政编码图像与其对应的机器可读的转换物用作训练实例，监督分类模型的学习。
• 无监督学习（unsupervised learning）本质上是聚类的同义词。学习过程是无监督的，因为输入实例没有类标记。典型地，我们可以使用聚类发现数据中的类。例如，一个无监督学习方法可以取一个手写数字图像集合作为输入。假设它找出了10个数据簇，这些簇可以分别对应于0~9这10个不同的数字。然而，由于训练数据并无标记，因此学习到的模型并不能告诉我们所发现的簇的语义。
• 半监督学习（semi-supervised learning）：在学习模型时，它使用标记的和未标记的实例。在一种方法中，标记的实例用来学习类模型，而未标记的实例用来进一步改进类边界。对于两类问题，我们可以把属于一个类的实例看做正实例，而属于另一个类的实例为负实例。
• 主动学习（active learning）：然用户在学习过程中扮演主动角色。主动学习方法可能要求用户（例如领域专家）对一个可能来自未标记的实例集或由学习程序合成的实例进行标记。给定可以要求标记的势力数量的约束，目的是主动通过从用户获取知识来提高模型质量。

1.5.3 数据库系统与数据仓库

……

1.5.4 信息检索

信息检索（IR）是搜索文档或文档中信息的科学。
信息检索的典型方法是采用概率模型。
一个文本文档集的主题可以用词汇表上的概率分布建模，称作主题模型。

数据挖掘的主要问题：挖掘方法、用户交互、有效性与可伸缩性、数据类型的多样性、数据挖掘与社会。

1.8 小结

需要是发明之母。
数据挖掘是从海量数据中发现有趣模式的过程。作为知识发现过程，它通常包括数据清理、数据集成、数据选择、数据变换、模式发现、模式评估和知识表示。
一个模式是有趣的，如果它在某种确信度上对于检验数据是有效的、新颖的、潜在有用的（例如，可以据之行动，或者验证了用户关注的某种预感），并且易于被人理解。有趣的模式代表知识。模式兴趣度度量，无论是客观的还是主观的，都可以用来知道发现过程。
数据挖掘的多维视图。主要的维是数据、知识、计数和应用。
只要数据对于目标应用是有意义的，数据挖掘可以在任何类型的数据上进行，如数据库管理、数据仓库数据、事务数据和高级数据类型等。高级数据类型包括时间相关的序列数据、数据流、空间和时空数据、文本和多媒体数据、图和网络数据、Web数据。
数据仓库是一种用于长期存储数据的仓库，这些数据来自多个数据源，是经过组织的，以便支持管理决策。这些数据在一中统一的模式下存放，并且通常是汇总的。数据仓库提供一些数据分析能力，称作联机分析处理。
多维数据挖掘（又称探索式多维数据挖掘）把数据挖掘的核心技术与基于OLAP的多维分析结合在一起，搜索有趣的模式，探索多维空间。
数据挖掘功能用来指定数据挖掘任务发现的模式或知识类型，包括特征化和区分，频繁模式、关联和相关性挖掘，分类和回归，聚类分析和离群点检测。
作为一个应用驱动的领域，数据挖掘融汇莱西其它一些领域的技术。这些领域包括统计学、机器学习、数据库和数据仓库系统，以及信息检索。
数据挖掘有许多成功的应用，如商务智能、Web搜索、生物信息学、卫生保健信息学、金融、数字图书馆和数字政府。
数据挖掘研究存在许多挑战性问题。领域包括挖掘方法、用户交互、有效性和可伸缩性，以及处理多种多样的数据类型。