Data Mining – Knowledge Discovery in Database (1)

1.2 What is data mining?

Data mining is the process of discovering interesting patterns and knowledge from large amount of data
数据挖掘是在大量数据中发现有趣模式和知识的处理过程

包括六个步骤

1. Data Cleaning (to remove noise and inconsistent data)
2. Data integration ( where multiple data source will be combined ) P.s. 现在也有人把这两个步骤合为一个，称作是数据预处理step，这两步完成后的结果将会放置到数据仓库里
3. Data selection ( where data relevant to the analysis task are retrieved from the database )
4. Data transformation ( where data are transformed and consolidated into forms appropriate for mining by performing summary or aggregation operations ) 把数据转换成DM可以的形式
5. Data mining 从数据中提取有用的pattern
6. Pattern evaluation 模式评估
7. Knowledge presentation 可视化展示

1.3 What kinds of Data can be mined？

Data mining can be applied to any kind of data as long as the data are meaningful for the target application 只要对目标应用有用，就可以用到任何data上

可以用来挖掘的基础形式有三种 Database data, data warehouse data, transactional data

1.3.1 Database data

数据库的作用

1. 提供定义数据库结构和数据存储的机制
2. 管理数据库并行，共享，分布的权限
3. 保证数据的一致性以及信息安全，尤其是系统损坏了或者是未授权的访问

关系型数据库就是表的集合=>每个表包含了一些属性列(attribute column)，元组行(tuple rows).每个元组行都有一个unique key. 经常使用ER数据库(Entity-relationship database)

挖掘数据库主要是为了searching for trends or patterns.

1.3.2 Data warehouse

A data warehouse is a repository of information collected from multiple sources, stored under the same schema, and usually residing at a single site.
从多个的信息源收集的信息存储库，把这些存储库的信息通过数据清理，变换，集成，装入来构造一个数据仓库

A data warehouse is usually modeled by a multidimensional data structure, called a data cube, in which each dimension corresponds to an attribute or a set of attributes in the schema, and each cell stores the value of some aggregate measure such as count
数据仓库用数据立方体进行多维数据建模，每个cell存放某种the value of some aggregate measure聚集度量值，比如count/sum，

1.3.3 Transactional data

事务数据就是每个数据都代表着一个事务，买东西，预定，网页点击等事务

1.3.4 Other data

其他的数据，比如有层次结构的树，图等等

1.4 What kind of Patterns can be mined?

Data mining functionalities 数据挖掘方法（功能)

characterization and discrimination 特征化和区分

mining of frequent patterns and associations correlation 频繁模式，关联和相关性挖掘

classification and regression 分类和回归

clustering analysis 聚类分析

outlier analysis 离群点分析

1.4.1 Class/Concept Description: Characterization and Discrimination

用高度概括的语言来描述每个类和概念(class/concept). 描述可以通过Characterization(数据特征化，汇总目标类的数据)或者是Discrimination(数据区分，将目标类与一个或者多个对比类进行比较)

Characterization的方法：

1. OLAP rollup，执行用户控制的，沿着指定维度的数据汇总 可以查询任意维度的数据，从某个维度观察特征
2. attribute-oriented induction 面向属性的归纳

Characterization的结果输出：

1. 传统的统计图表
2. generalized relations / characteristic rules

Data discrimination的方法：

1. 将目标类和对比类进行比较

Data discrimination 结果输出：

1. 特征描述.包括目标类和对比类的比较度量，可以区别目标类和对比类。Discrimination description将被用Discriminant rules描述

本质Charaterization是总结,discrimination是对比

1.4.2 Mining Frequent Patterns, Associations, and Correlations

Mining frequent Patterns are the patterns that occur frequently in data.
频繁模式(frequent patterns)就是在数据中经常出现的模式

frequent patterns 包括 frequent itemsets, frequent subsequences( sequential patterns), frequent substructures. 也就是经常出现的序列或者是其他数据结构。比如买过laptop之后买相机再买内存卡在amazon中经常出现，这样就是一个经常出现的序列。就可以被挖掘出来

1.4.2.1 一个例子

buys(X,"computer") => buys(X,"software") 
[support = 1%, confidence = 50%]

confidence (置信度) pattern相信程度

support (支持度) 有多少数据支持这个pattern

只有一个predicate(谓词)的关联结构叫做 single-dimensional association rules(单维关联规则），去掉predicate可以把上面的结论简化为

computer => software [ 1%,50% ]

age(X,"20..29") AND income(X,"40K...49K") => buys(X,"laptop")

涉及到不止一个predicate/attribute的pattern,我们就称之为multi-dimensional association rule(多维关联规则)

如果association rules不能满足minimum support threshold(最小支持度阈值)以及minimum confidence threshold(最小置信度阈值),我们就要把这个rule抛弃掉。

1.4.3 Classification and Regression for Predictive Analysis

重点在于Classification是在区别每一个class. 例如顾客对商品反应的分类标号，可以提前预知下一个商品的类label。

Regression是根据之前的数据，预测未来的连续值。

Classification: 找到一个model or function,能够描述/区分数据类或者概念. 得到的结果是基于对训练数据集的分析。模型可以用来预测 类label未知 的label。

导出来的模型是怎么表示的？决策树和神经网络

• 决策树decision tree 就是 流程图，可以转换成 if then (classification rules)规则
• 神经网络neural network 就是一组类似于神经元的处理单元，单元之间加权连接
• 朴素贝叶斯分类，支持向量机，k最邻近分类

Classification 是预测label，label则是离散的，无序的。

Regression: 预测缺失的或者难以获得的数据值。Regression预测的值是连续的

Relevance analysis: 在Classification and Regression前进行，选出来相关的attribution，其他不相关的不考虑

书中的例1.8意思是把商店中的商品根据描述特性所对应的反应，导出一个模型，来预测后面新商品的反应。这个模型同时能够提供数据集的描述

1.4.4 Cluster Analysis

Clustering 分析的数据物品不需要考虑class-labeled，Clustering可以被用作产生类标号

Clustering的原则(principle):

• maximizing the intraclass similarity 最大化类内相似性
• Minimizing the interclass similarity 最小化类间相似性

所形成的cluster可以看成一个class of objects, 我们可以知道这个class的规则(rule)

clustering 可以便于 taxonomy formation(分类法形成)

例子是利用地理位置给顾客分类

1.4.5 Outlier Analysis

不遵从general规则的数据称作是outlier。一般outlier被视作噪声，但是fraud detection可以用这个分析

The analysis of outlier data is referred to as outlier analysis(离群点分析) or anomaly mining(异常挖掘)

1.4.6 Are All Patterns Interesting?

A pattern is interesting if it is (1) easily understood by humans, (2) valid on new or test data with some degree of certainty, 有效的 (3) potentially useful, and 潜在有用的 (4) novel. 新颖的 A pattern is also interesting if it validates a hypothesis that the user sought to confirm. An interesting pattern represents knowledge. 有趣的模式就是知识

Objective measures of pattern interestingness 模式兴趣度的客观度量

• support P(X U Y)
• confidence P(Y|X)

Others

If-then 规则的 accurancy and coverage 准确率和覆盖率

accurancy : 按照If-then规则正确分类的数据所占百分比。分类的数据是正确的

coverage : 规则可以作用的数据的百分比。 能用这个规则分类的数据的百分比

Subjective interestingness measures 主观兴趣度量

发现的pattern是出乎意料的或者是可以为用户的行动提供信息的，我们把后者成为actionable

1.5 Which Technologies Are Used?

1.5.1 Statistics

Statistics model是一组数学函数，函数使用随机变量和概率分布来刻画目标类的行为

1.5.2 Machine Learning

• supervised learning = 分类 classification 学习中的监督来自于数据中的label
• unsupervied learning 类似于聚类 clustering 学习过程无监督 如给出一些手写数字图像 机器可以把相似的分类，但是机器无法识别出这些图像有什么意思
• semi-supervised learning 使用标记的和未标记的数据 标记的用来学习 class model, 未标记的用来完善边界。

Reference

Data Mining. Concepts and Techniques 3rd Edition