Data Mining 简明教程
Data Mining - Overview
信息产业中有大量可用数据。在转换成有用的信息之前,这些数据毫无用处。有必要分析这些海量数据并从中提取有用信息。
信息提取不是我们需要执行的唯一过程;数据挖掘还涉及其他过程,如数据清理、数据集成、数据转换、数据挖掘、模式评估和数据展示。一旦所有这些过程结束,我们就可以在许多应用程序中使用这些信息,例如欺诈检测、市场分析、生产控制、科学探索等。
What is Data Mining?
数据挖掘被定义为从大量数据中提取信息。换句话说,我们可以说数据挖掘是从小知识中挖掘知识的过程。提取的信息或知识可用于以下任何应用程序 -
-
Market Analysis
-
Fraud Detection
-
Customer Retention
-
Production Control
-
Science Exploration
Data Mining Applications
数据挖掘在以下领域极有用处 -
-
Market Analysis and Management
-
公司分析和风险管理
-
Fraud Detection
除此之外,数据挖掘还可用于生产控制、客户保留、科学探索、体育、占星术和互联网 Web Surf-Aid 领域
Market Analysis and Management
以下是数据挖掘使用的各个市场领域 -
-
Customer Profiling - 数据挖掘有助于确定哪类人购买哪类产品。
-
Identifying Customer Requirements - 数据挖掘有助于识别适用于不同客户的最佳产品。它使用预测来找到可能吸引新客户的因素。
-
Cross Market Analysis - 数据挖掘执行产品销售之间的关联/相关性。
-
Target Marketing - 数据挖掘有助于找到具有相同特征(例如兴趣、消费习惯、收入等)的模型客户群。
-
Determining Customer purchasing pattern - 数据挖掘有助于确定客户购买模式。
-
Providing Summary Information − 数据挖掘为我们提供了各种多维摘要报告。
Data Mining - Tasks
数据挖掘涉及可挖掘的模式类型。根据要挖掘的数据类型,数据挖掘涉及两个类别的功能 −
-
Descriptive
-
Classification and Prediction
Descriptive Function
描述功能涉及数据库中数据的常规属性。以下是描述功能列表 −
-
Class/Concept Description
-
Mining of Frequent Patterns
-
Mining of Associations
-
Mining of Correlations
-
Mining of Clusters
Class/Concept Description
类别/概念是指要与类别或概念关联的数据。例如,在一家公司中,销售物品的类别包括计算机和打印机,客户概念包括大额消费者和预算消费者。此类类别或概念的描述称为类别/概念描述。可以通过以下两种方式获取这些描述:
-
Data Characterization − 指总结类研究的数据。此类研究称为目标类。
-
Data Discrimination − 指将类与一些预定义组或类进行映射或分类。
Mining of Frequent Patterns
频繁模式是指在交易数据中经常发生的模式。以下是频繁模式的类型列表 −
-
Frequent Item Set − 指经常一起出现的商品组,例如牛奶和面包。
-
Frequent Subsequence − 经常发生的模式序列,例如先购买相机,然后购买存储卡。
-
Frequent Sub Structure − 子结构是指不同的结构形式,例如图、树或格,可以与项目集或子序列结合。
Classification and Prediction
分类是查找描述数据类别或概念的模型的过程。目的是能够使用此模型来预测类标签未知的对象的类别。此派生模型基于对培训数据集的分析。派生模型可以以下形式呈现:
-
Classification (IF-THEN) Rules
-
Decision Trees
-
Mathematical Formulae
-
Neural Networks
参与这些过程的函数列表如下:
-
Classification - 预测类标签未知的对象的类别。其目的是找到一个描述和区分数据类别或概念的派生模型。派生模型基于培训数据集的分析,即类标签已知的对象。
-
Prediction - 用于预测缺失或不可用的数字数据值,而不是类标签。回归分析通常用于预测。预测还可以用于根据可用数据识别分布趋势。
-
Outlier Analysis - 异常值可以定义为不符合可用数据的总体行为或模型的数据对象。
-
Evolution Analysis - 进化分析是指描述和建模行为随着时间变化的对象的规律性或趋势。
Data Mining Task Primitives
-
我们可以通过数据挖掘查询的形式指定数据挖掘任务。
-
此查询是输入给系统的。
-
数据挖掘查询是根据数据挖掘任务基元定义的。
Note − 这些基础函数允许我们以交互方式与数据挖掘系统进行通信。以下为数据挖掘任务基础函数列表 -
-
要挖掘的相关数据集合。
-
要挖掘的知识类型。
-
发现过程中要使用的背景知识。
-
模式评估的有趣性度量和阈值。
-
表示用于显示发现的模式。
Kind of knowledge to be mined
它指要执行的功能类型。这些功能为 -
-
Characterization
-
Discrimination
-
Association and Correlation Analysis
-
Classification
-
Prediction
-
Clustering
-
Outlier Analysis
-
Evolution Analysis
Data Mining - Issues
数据挖掘不是一项简单的任务,因为所使用的算法可能非常复杂,而且数据并不总是在一个地方可用。它需要从各种异构数据源进行集成。这些因素还产生了一些问题。在本教程中,我们将讨论有关主要问题 −
-
挖掘方法和用户交互
-
Performance Issues
-
Diverse Data Types Issues
下图描述了主要问题。
Mining Methodology and User Interaction Issues
它涉及以下类别的问题 −
-
Mining different kinds of knowledge in databases − 不同的用户可能对不同种类的知识感兴趣。因此,数据挖掘必须涵盖广泛的知识发现任务。
-
Interactive mining of knowledge at multiple levels of abstraction − 数据挖掘过程需要是交互式的,因为它允许用户重点关注模式搜索,并基于返回结果提供和优化数据挖掘请求。
-
Incorporation of background knowledge − 背景知识可用于指导发现过程并表达发现的模式。背景知识可用于不仅以简洁的术语表达发现的模式,而且以多个抽象级别表达。
-
Data mining query languages and ad hoc data mining − 数据挖掘查询语言允许用户描述临时挖掘任务,应该与数据仓库查询语言集成,并针对高效灵活的数据挖掘优化。
-
Presentation and visualization of data mining results − 一旦模式被发现,就需要用高级语言和可视化表示来表达。这些表示应该易于理解。
-
Handling noisy or incomplete data − 在挖掘数据规律时,需要使用数据清洗方法来处理噪声和不完整对象。如果数据清洗方法不存在,那么发现的模式的准确性将较差。
-
Pattern evaluation − 发现的模式应该是有趣的,因为它们要么代表了常识,要么缺乏新颖性。
Data Mining - Evaluation
Data Warehouse
数据仓库表现出以下特征以支持管理层决策过程 −
-
Subject Oriented − 数据仓库面向主题,因为它为我们提供某个主题的信息,而不是组织的持续运营。这些主题可以是产品、客户、供应商、销售、收入等。数据仓库不关注正在进行的业务操作,而是侧重于对数据进行建模和分析以做出决策。
-
Integrated − 数据仓库通过集成来自异构源(如关系数据库、平面文件等)的数据来构建。这种集成增强了对数据的有效分析。
-
Time Variant − 数据仓库中收集的数据已识别为特定时间段。数据仓库中的数据提供历史观点的信息。
-
Non-volatile − 非易失意味着在新数据添加到原有数据时,不会删除前一个数据。数据仓库与操作数据库分开保存,因此操作数据库中的频繁更改不会反映在数据仓库中。
Data Warehousing
数据仓储是构建和使用数据仓库的过程。数据仓库是通过集成来自多个异构源的数据来构建的。它支持分析报告、结构化和/或临时查询以及决策制定。
数据仓储涉及数据清理、数据集成和数据合并。为了集成异构数据库,我们采用了以下两种方法:
-
Query Driven Approach
-
Update Driven Approach
Query-Driven Approach
这是集成异构数据库的传统方法。此方法用于在多个异构数据库之上构建包装和集成器。这些集成器也称为“中介器”。
Update-Driven Approach
当今的数据仓库系统遵循更新驱动方法,而不是前面讨论的传统方法。在更新驱动方法中,来自多个异构源的信息已预先集成并存储在仓库中。此信息可用于直接查询和分析。
From Data Warehousing (OLAP) to Data Mining (OLAM)
在线分析挖掘与在线分析处理通过对多维数据库进行数据挖掘和知识挖掘进行集成。以下是展示了 OLAP 和 OLAM 集成的示意图 −
Importance of OLAM
OLAM 出于以下原因很重要 −
-
High quality of data in data warehouses − 数据挖掘工具需要对已整合、一致且已清理的数据进行处理。这些步骤在数据预处理过程中成本非常高。此类预处理建立的数据仓库也是 OLAP 和数据挖掘的高质量数据的有价值的来源。
-
Available information processing infrastructure surrounding data warehouses − 信息处理基础设施是指对多个异构数据库、网络访问和服务设施、报告和 OLAP 分析工具的访问、集成、合并和转换。
-
OLAP−based exploratory data analysis − 有效的数据挖掘需要探索性数据分析。OLAM 为各种数据子集和不同抽象级别的的数据挖掘提供便利。
-
Online selection of data mining functions − 将 OLAP 与多个数据挖掘函数和在线分析挖掘相集成为用户提供了选择所需数据挖掘函数和动态交换数据挖掘任务的灵活性。
Data Mining - Terminologies
Data Mining
数据挖掘被定义为从大量数据中提取信息。换句话说,我们可以说数据挖掘是从数据中挖掘知识。此信息可用于以下任意应用程序 −
-
Market Analysis
-
Fraud Detection
-
Customer Retention
-
Production Control
-
Science Exploration
Data Mining Engine
数据挖掘引擎对数据挖掘系统至关重要。它由执行以下函数的一组功能模块组成 −
-
Characterization
-
Association and Correlation Analysis
-
Classification
-
Prediction
-
Cluster analysis
-
Outlier analysis
-
Evolution analysis
Knowledge Discovery
有些人将数据挖掘与知识发现视为同义词,而另一些人则将数据挖掘视为知识发现过程中必不可少的一步。以下是知识发现过程中涉及的步骤 −
-
Data Cleaning
-
Data Integration
-
Data Selection
-
Data Transformation
-
Data Mining
-
Pattern Evaluation
-
Knowledge Presentation
Data Mining - Knowledge Discovery
What is Knowledge Discovery?
有的人不区分数据挖掘和知识发现,而另一些人则将数据挖掘视为知识发现过程中至关重要的一步。以下是知识发现过程中涉及的步骤列表−
-
Data Cleaning - 在此步骤中,消除了噪声和不一致的数据。
-
Data Integration - 在此步骤中,将多个数据源合并在一起。
-
Data Selection - 在此步骤中,从数据库中检索与分析任务相关的数据。
-
Data Transformation - 在此步骤中通过执行摘要或汇总操作,将数据转换成适合挖掘的形式。
-
Data Mining - 在此步骤中,采用智能方法以提取数据模式。
-
Pattern Evaluation - 在此步骤中,对数据模式进行评估。
-
Knowledge Presentation - 在此步骤中,表示知识。
下图显示了知识发现的过程 −
Data Mining - Systems
各种数据挖掘系统中可供选择。数据挖掘系统可能集成以下技术 −
-
Spatial Data Analysis
-
Information Retrieval
-
Pattern Recognition
-
Image Analysis
-
Signal Processing
-
Computer Graphics
-
Web Technology
-
Business
-
Bioinformatics
Data Mining System Classification
根据以下条件可以对数据挖掘系统进行分类 −
-
Database Technology
-
Statistics
-
Machine Learning
-
Information Science
-
Visualization
-
Other Disciplines
除此之外,还可以根据所挖掘的(a)数据库、所挖掘的(b)知识、所利用的(c)技术和所适应的(d)应用程序对数据挖掘系统进行分类。
Classification Based on the Databases Mined
我们可以根据所挖掘的数据库类型对数据挖掘系统进行分类。可以根据数据模型、数据类型等不同条件对数据库系统进行分类。相应地,数据挖掘系统也进行分类。
例如,如果我们根据数据模型对数据库进行分类,则可能有一个关系、事务、对象关系或数据仓库挖掘系统。
Classification Based on the kind of Knowledge Mined
我们还可以根据所挖掘的知识类型对数据挖掘系统进行分类。这意味着根据诸如以下功能对数据挖掘系统进行分类−
-
Characterization
-
Discrimination
-
Association and Correlation Analysis
-
Classification
-
Prediction
-
Outlier Analysis
-
Evolution Analysis
Integrating a Data Mining System with a DB/DW System
如果数据挖掘系统未与数据库或数据仓库系统集成,则将没有要通信的系统。此方案称为非耦合方案。在这个方案中,重点放在数据挖掘设计以及为挖掘可用数据集开发高效且有效的算法上。
集成方案如下列出 −
-
No Coupling − 在此方案中,数据挖掘系统不利用任何数据库或数据仓库功能。它从特定数据源中获取数据,然后使用一些数据挖掘算法处理该数据。数据挖掘结果存储在另一个文件中。
-
Loose Coupling − 在此方案中,数据挖掘系统可能使用一些数据库和数据仓库系统功能。它从由这些系统管理的数据源中获取数据,然后对该数据执行数据挖掘。然后它将挖掘结果存储在文件中,或存储在数据库或数据仓库中的指定位置。
-
Semi−tight Coupling − 在此方案中,数据挖掘系统与数据库或数据仓库系统链接,此外,可以在数据库中提供一些数据挖掘原始功能的高效实现。
-
Tight coupling − 在此耦合方案中,数据挖掘系统平顺集成到数据库或数据仓库系统中。数据挖掘子系统被视为信息系统的一个功能组件。
Data Mining - Query Language
数据挖掘查询语言 (DMQL) 由 Han、Fu、Wang 提议用于 DBMiner 数据挖掘系统。数据挖掘查询语言实际上基于结构化查询语言 (SQL)。可以设计数据挖掘查询语言来支持特设和交互式数据挖掘。此 DMQL 提供用于指定原始元素的命令。DMQL 可以与数据库和数据仓库配合使用。DMQL 可用于定义数据挖掘任务。我们特别检查如何在 DMQL 中定义数据仓库和数据市集。
Syntax for Task-Relevant Data Specification
以下是用于指定任务相关数据的 DMQL 语法 −
use database database_name
or
use data warehouse data_warehouse_name
in relevance to att_or_dim_list
from relation(s)/cube(s) [where condition]
order by order_list
group by grouping_list
Syntax for Specifying the Kind of Knowledge
我们在此将讨论表征、辨别、关联、分类和预测的语法。
Characterization
表征语法如下 −
mine characteristics [as pattern_name]
analyze {measure(s) }
analyze 子句,指定聚合测量值,例如 count、sum 或 count%。
例如 -
Description describing customer purchasing habits.
mine characteristics as customerPurchasing
analyze count%
Discrimination
辨别语法如下 −
mine comparison [as {pattern_name]}
For {target_class } where {t arget_condition }
{versus {contrast_class_i }
where {contrast_condition_i}}
analyze {measure(s) }
例如,用户可能会将大额挥霍者定义为平均购买 100 美元或更多商品的客户;而将预算挥霍者定义为平均购买低于 100 美元商品的客户。可以通过 DMQL 将从每个此类别的客户中挖掘的辨别描述指定为 −
mine comparison as purchaseGroups
for bigSpenders where avg(I.price) ≥$100
versus budgetSpenders where avg(I.price)< $100
analyze count
Association
关联语法如下 −
mine associations [ as {pattern_name} ]
{matching {metapattern} }
例如 −
mine associations as buyingHabits
matching P(X:customer,W) ^ Q(X,Y) ≥ buys(X,Z)
其中 X 是客户关系的关键;P 和 Q 是谓词变量;W、Y 和 Z 是对象变量。
Syntax for Concept Hierarchy Specification
要指定概念层次结构,请使用以下语法 −
use hierarchy <hierarchy> for <attribute_or_dimension>
我们使用不同的语法来定义不同类型的层次结构,例如 −
-schema hierarchies
define hierarchy time_hierarchy on date as [date,month quarter,year]
-
set-grouping hierarchies
define hierarchy age_hierarchy for age on customer as
level1: {young, middle_aged, senior} < level0: all
level2: {20, ..., 39} < level1: young
level3: {40, ..., 59} < level1: middle_aged
level4: {60, ..., 89} < level1: senior
-operation-derived hierarchies
define hierarchy age_hierarchy for age on customer as
{age_category(1), ..., age_category(5)}
:= cluster(default, age, 5) < all(age)
-rule-based hierarchies
define hierarchy profit_margin_hierarchy on item as
level_1: low_profit_margin < level_0: all
if (price - cost)< $50
level_1: medium-profit_margin < level_0: all
if ((price - cost) > $50) and ((price - cost) ≤ $250))
level_1: high_profit_margin < level_0: all
Syntax for Interestingness Measures Specification
用户可以使用该语句指定有趣性测量和阈值 −
with <interest_measure_name> threshold = threshold_value
例如 −
with support threshold = 0.05
with confidence threshold = 0.7
Syntax for Pattern Presentation and Visualization Specification
我们有一个语法,允许用户指定一种或多种形式中发现的模式的显示方式。
display as <result_form>
例如 −
display as table
Full Specification of DMQL
作为一名公司的市场经理,您希望对购买价格不少于 100 美元的商品的顾客的购买习惯进行表征;根据顾客的年龄、购买商品的类型以及购买商品的地点。您希望知道具有该特征的顾客的百分比。特别是,您只对在加拿大进行的,并使用美国运通信用卡支付的购买感兴趣。您希望以表格的形式查看结果说明。
use database AllElectronics_db
use hierarchy location_hierarchy for B.address
mine characteristics as customerPurchasing
analyze count%
in relevance to C.age,I.type,I.place_made
from customer C, item I, purchase P, items_sold S, branch B
where I.item_ID = S.item_ID and P.cust_ID = C.cust_ID and
P.method_paid = "AmEx" and B.address = "Canada" and I.price ≥ 100
with noise threshold = 5%
display as table
Data Mining - Classification & Prediction
有两种形式的数据分析可以用于提取描述重要类别的模型或预测未来的数据趋势。这两种形式如下 −
-
Classification
-
Prediction
分类模型预测分类类别标签;预测模型预测连续的值函数。例如,我们可以构建一个分类模型,将银行贷款申请归类为安全或有风险,或构建一个预测模型,根据潜在客户的收入和职业来预测他们在计算机设备上的支出(以美元为单位)。
What is classification?
以下是数据分析任务是分类的案例示例 −
-
银行信贷员希望分析数据以了解哪些客户(贷款申请人)有风险或哪些是安全的。
-
一家公司的营销经理需要分析具有给定配置文件的客户,他们将购买新计算机。
在上述两个示例中,构造了一个模型或分类器来预测分类标签。对于贷款申请数据,这些标签是“有风险”或“安全”,对于市场数据,这些标签是“是”或“否”。
What is prediction?
以下是数据分析任务是预测的案例示例 −
假设营销经理需要预测给定客户在他公司的一次促销中会花费多少钱。在这个示例中,我们很乐意预测一个数字值。因此,数据分析任务是数字预测的示例。在这种情况下,将构造一个模型或预测器来预测连续值函数或有序值。
Note − 回归分析是一种最常用于数字预测的统计方法。
How Does Classification Works?
借助我们上面讨论的银行贷款申请,让我们了解分类的工作原理。数据分类过程包括两个步骤 −
-
构建分类器或模型
-
Using Classifier for Classification
Classification and Prediction Issues
主要问题是为分类和预测准备数据。准备数据包含以下活动:
-
Data Cleaning − 数据清理涉及移除噪声和处理缺失值。通过应用平滑技术来移除噪声,并通过用该属性最常出现的值替换缺失值来解决缺失值问题。
-
Relevance Analysis − 数据库可能还具有无关属性。相关性分析用于了解给定的两个属性是否相关。
-
Data Transformation and reduction − 数据可以通过以下任何一种方法转换。 Normalization − 使用归一化转换数据。归一化涉及缩放给定属性的所有值,以便使它们落在较小的指定范围内。在学习步骤中使用神经网络或涉及测量的其他方法时,使用归一化。 Generalization − 还可以通过将其概括为更高的概念来转换数据。为了这个目的,我们可以使用概念层次结构。
Note − 还可以通过其他一些方法来减少数据,例如小波变换、分箱、直方图分析和聚类。
Data Mining - Decision Tree Induction
决策树是一个包含根节点、分支和叶节点的结构。每个内部节点表示对属性的测试,每个分支表示测试结果,每个叶节点包含一个类标签。树中最高级别的节点是根节点。
以下决策树用于表示 buy_computer 概念,它表示一家公司的客户是否可能会购买计算机。每个内部节点表示对属性的测试。每个叶节点表示一个类。
拥有决策树的好处如下−
-
它不需要任何领域知识。
-
易于理解。
-
决策树的学习和分类步骤简单且快速。
Decision Tree Induction Algorithm
一位名叫 J. Ross Quinlan 的机器研究人员在 1980 年开发了一种名为 ID3(迭代二分器)的决策树算法。随后,他提出了 ID3 的继任者 C4.5。ID3 和 C4.5 采用贪婪方法。在这种演算法中,不存在回溯;以自顶向下的递归分而治之的方式构建树。
Generating a decision tree form training tuples of data partition D
Algorithm : Generate_decision_tree
Input:
Data partition, D, which is a set of training tuples
and their associated class labels.
attribute_list, the set of candidate attributes.
Attribute selection method, a procedure to determine the
splitting criterion that best partitions that the data
tuples into individual classes. This criterion includes a
splitting_attribute and either a splitting point or splitting subset.
Output:
A Decision Tree
Method
create a node N;
if tuples in D are all of the same class, C then
return N as leaf node labeled with class C;
if attribute_list is empty then
return N as leaf node with labeled
with majority class in D;|| majority voting
apply attribute_selection_method(D, attribute_list)
to find the best splitting_criterion;
label node N with splitting_criterion;
if splitting_attribute is discrete-valued and
multiway splits allowed then // no restricted to binary trees
attribute_list = splitting attribute; // remove splitting attribute
for each outcome j of splitting criterion
// partition the tuples and grow subtrees for each partition
let Dj be the set of data tuples in D satisfying outcome j; // a partition
if Dj is empty then
attach a leaf labeled with the majority
class in D to node N;
else
attach the node returned by Generate
decision tree(Dj, attribute list) to node N;
end for
return N;
Data Mining - Bayesian Classification
贝叶斯分类基于贝叶斯定理。贝叶斯分类器是统计分类器。贝叶斯分类器可以预测类成员身份概率,例如给定元组属于特定类的概率。
Baye’s Theorem
贝叶斯定理是以托马斯·贝叶斯命名的。有两种类型的概率 -
-
Posterior Probability [P(H/X)]
-
Prior Probability [P(H)]
其中 X 是数据元组,H 是一些假设。
根据贝叶斯定理,
Bayesian Belief Network
贝叶斯信念网络指定了联合条件概率分布。它们也被称为信念网络、贝叶斯网络或概率网络。
-
信念网络允许在变量子集之间定义类条件独立性。
-
它提供了一个因果关系的图形模型,可以在其上进行学习。
-
我们可以使用训练后的贝叶斯网络进行分类。
定义贝叶斯推理网络的两个组件为:
-
Directed acyclic graph
-
一组条件概率表
Data Mining - Rule Based Classification
IF-THEN Rules
基于规则的分类器使用了一系列的 IF-THEN 规则来进行分类。我们可以使用下面的方式表达规则:
让我们考虑规则 R1,
R1: IF age = youth AND student = yes
THEN buy_computer = yes
Points to remember −
-
规则的 IF 部分称为 rule antecedent 或 precondition 。
-
规则的 THEN 部分称为 rule consequent 。
-
条件的前提部分包括一个或多个属性测试,并且这些测试在逻辑上是 AND 关系。
-
结果部分包括类预测。
Note − 我们还可以将规则 R1 写成:
R1: (age = youth) ^ (student = yes))(buys computer = yes)
如果一个给定的元组的条件成立,则前件得到满足。
Rule Extraction
这里我们将学习如何通过从决策树中提取 IF-THEN 规则来构建基于规则的分类器。
Points to remember −
从决策树中提取规则的步骤:
-
为从根节点到叶节点的每条路径创建一个规则。
-
要形成规则前件,每个分裂标准在逻辑上都是 ANDed。
-
叶节点持有类预测,形成规则结果。
Rule Induction Using Sequential Covering Algorithm
顺序覆盖算法可用于提取 IF-THEN 规则形成训练数据。我们不需要首先生成决策树。在此算法中,给定类的每个规则都涵盖了该类的许多元组。
一些顺序覆盖算法是 AQ、CN2 和 RIPPER。根据一般策略,规则是一次学到的。每次规则被学到时,规则所覆盖的元组都会被移除并继续处理剩余的元组。这是因为决策树中到每个叶子的路径都对应一条规则。
Note - 决策树归纳可以被认为是同时学习一组规则。
以下是用于一次为一个类学习规则的顺序学习算法。当从类 Ci 中学习规则时,我们希望规则仅涵盖类 C 中的所有元组,而不涵盖其他类的元组。
Algorithm: Sequential Covering
Input:
D, a data set class-labeled tuples,
Att_vals, the set of all attributes and their possible values.
Output: A Set of IF-THEN rules.
Method:
Rule_set={ }; // initial set of rules learned is empty
for each class c do
repeat
Rule = Learn_One_Rule(D, Att_valls, c);
remove tuples covered by Rule form D;
until termination condition;
Rule_set=Rule_set+Rule; // add a new rule to rule-set
end for
return Rule_Set;
Miscellaneous Classification Methods
此处我们将讨论其他分类方法,如遗传算法、粗糙集方法和模糊集方法。
Genetic Algorithms
遗传算法的思想源自自然进化。在遗传算法中,首先创建初始种群。这个初始种群由随机生成的规则组成。我们可以用一串位来表示每条规则。
例如,在给定的训练集中,样本由两个布尔属性描述,例如 A1 和 A2。而给定的训练集包含两个类,例如 C1 和 C2。
我们可以将规则 IF A1 AND NOT A2 THEN C2 编码为位串 100 。在此位表示中,最左边的两位分别代表属性 A1 和 A2。
同样,规则 IF NOT A1 AND NOT A2 THEN C1 可编码为 001 。
Note - 如果属性有 K 个值,其中 K>2,则我们可以使用 K 位对属性值进行编码。类也以相同的方式编码。
要点 -
-
基于最适者生存的概念,形成一个新群体,该群体由当前群体中最适应的规则以及这些规则的后代值组成。
-
通过在训练样本集上的分类准确度评估规则的适应性。
-
应用交叉和变异等遗传算子来创建后代。
-
在交叉中,成对规则的子字符串被交换以形成一对新规则。
-
在变异中,规则字符串中的随机选定位被反转。
Rough Set Approach
我们可以使用粗糙集方法来发现不精确和噪声数据中的结构关系。
Note - 此方法只能应用于离散值属性。因此,连续值属性必须在使用之前离散化。
粗糙集理论基于在给定的训练数据中建立等价类。形成等价类的元组是不可辨别的。这意味着样本相对于描述数据的属性是相同的。
在给定的真实世界数据中,有些类不能用可用属性来区分。我们可以使用粗糙集来 roughly 定义这样的类。
对于给定的类 C,粗糙集定义近似为以下两个集合 -
-
Lower Approximation of C - C 的下近似包含所有数据元组,根据属性知识,这些元组肯定属于类 C。
-
Upper Approximation of C - C 的上近似包含所有元组,根据属性知识,不能描述为不属于 C。
下图显示了类 C 的上近似和下近似 -
Fuzzy Set Approaches
模糊集理论也称为可能性理论。该理论是由 Lotfi Zadeh 在 1965 年提出的,作为 two-value logic 和 probability theory 的替代品。该理论允许我们在高层次的抽象中工作。它还为我们提供了处理数据不精确测量的方法。
模糊集理论还允许我们处理模糊或不确切的事实。例如,成为高收入人群的成员是不确切的(例如,如果 50,000 美元很高,那么 49,000 美元和 48,000 美元呢)。与传统的 CRISP 集不同,在传统的 CRISP 集中,元素要么属于 S 或其补集,但在模糊集理论中,元素可以属于多个模糊集。
例如,收入值 49,000 美元属于中等和高模糊集,但程度不同。该收入值的模糊集表示如下 -
mmedium_income($49k)=0.15 and mhigh_income($49k)=0.96
其中“m”是分别对 medium_income 和 high_income 的模糊集进行操作的隶属函数。该符号可以用图表表示如下 -
Data Mining - Cluster Analysis
簇是属于同一类的对象组。换句话说,相似对象被归入一个簇中,而不相似对象被归入另一个簇中。
What is Clustering?
聚类是将一组抽象对象变成相似对象类的过程。
Points to Remember
-
一组数据对象可以被视为一组。
-
在进行聚类分析时,我们首先根据数据相似性将数据集合划分为组,然后为各组分配标签。
-
聚类比分类的主要优势是,它可以适应变化,并有助于明确区分不同组的有用特征。
Applications of Cluster Analysis
-
聚类分析广泛用于许多应用,例如市场研究、模式识别、数据分析和图像处理。
-
聚类还可以帮助营销人员发现客户群中的不同群体。他们还可以根据购买模式来描述他们的客户群。
-
在生物学领域,它可以用于推导植物和动物分类学,对具有相似功能的基因进行分类,并深入了解种群固有的结构。
-
聚类也有助于识别地球观测数据库中相似土地利用区域。它也有助于根据房屋类型、价值和地理位置识别城市中的房屋组。
-
聚类还有助于对网络上的文档进行分类以发现信息。
-
聚类还用于异常检测应用程序,例如信用卡欺诈检测。
-
作为数据挖掘功能,聚类分析充当一个工具,用于深入了解数据分布,以观察每个簇的特征。
Requirements of Clustering in Data Mining
以下要点阐明了为什么需要在数据挖掘中进行聚类 −
-
Scalability − 我们需要高度可扩展的聚类算法来处理大型数据库。
-
Ability to deal with different kinds of attributes − 算法应该能够应用于任何类型的数据,例如基于间隔(数值)的数据、分类数据和二进制数据。
-
Discovery of clusters with attribute shape − 聚类算法应该能够检测出任意形状的簇。它们不应局限于仅寻找小尺寸球形簇的距离度量。
-
High dimensionality − 聚类算法不仅应该能够处理低维数据,还应该能够处理高维空间。
-
Ability to deal with noisy data − 数据库包含有噪声、缺失或错误的数据。有些算法对这些数据敏感,并且会导致质量较差的簇。
-
Interpretability − 聚类结果应该具有可解释性、可理解性且可用。
Clustering Methods
聚类方法可归类为以下类别−
-
Partitioning Method
-
Hierarchical Method
-
Density-based Method
-
Grid-Based Method
-
Model-Based Method
-
Constraint-based Method
Partitioning Method
假设我们给定一个由“n”个对象组成的数据库,并且划分法构建了“k”个数据分区。每个分区都将表示一个簇,并且k ≤ n。这意味着它会将数据分成k个组,满足以下要求−
-
每组至少包含一个对象。
-
每个对象必须恰好属于一组。
Points to remember −
-
对于给定的分区数(例如k),划分法将创建一个初始分区。
-
然后,它使用迭代重定位技术通过将对象从一组移动到另一组来改进分区。
Hierarchical Methods
这种方法对给定的数据对象集创建了一种分层分解。我们可以根据分层分解的形成方式对分层方法进行分类。这里有两种方法−
-
Agglomerative Approach
-
Divisive Approach
Agglomerative Approach
这种方法也称为自下而上的方法。在这种方法中,我们从每个对象形成一个单独的组开始。其不断合并彼此接近的对象或组。其会不断这样做,直到所有组都合并为一个或直到终止条件成立。
Divisive Approach
这种方法也称为自上而下的方法。在这种方法中,我们从同一个簇中的所有对象开始。在连续迭代中,将一个簇分成较小的簇。其会进行此操作,直到一个簇中的每个对象或终止条件成立。该方法是严格的,即一旦合并或分裂完成,则永远无法撤消。
Approaches to Improve Quality of Hierarchical Clustering
以下是用于提高分层聚类质量的两种方法−
-
在每个分层分区中仔细分析对象链接。
-
通过首先使用分层凝聚算法将对象分组到微簇中,整合分层凝聚,然后对微簇执行宏聚类。
Grid-based Method
在此当中,对象共同形成一个网格。对象空间被量子化成有限数量的单元格,形成了网格结构。
Advantages
-
此方法的主要优点是处理速度快。
-
它仅依赖于量子化空间中每个维度中的单元格数量。
Data Mining - Mining Text Data
文本数据库包含大量的文档集合。它们从多种来源收集这些信息,例如新闻文章、书籍、数字图书馆、电子邮件、网页等。由于信息量的增加,文本数据库正在迅速增长。在许多文本数据库中,数据是半结构化的。
例如,一个文档可能包含一些结构化字段,例如标题、作者、出版日期等。但除了结构数据之外,文档还包含非结构化文本组件,例如摘要和内容。在不知道文档中可能包含什么的情况下,很难制定有效的查询来分析和提取数据中有用的信息。用户需要工具来比较文档并对其重要性和相关性进行排名。因此,文本挖掘已变得流行,并成为数据挖掘中的一个基本主题。
Information Retrieval
信息检索涉及从大量文本文档中检索信息。一些数据库系统通常不存在于信息检索系统中,因为两者处理不同类型的数据。信息检索系统示例包括 −
-
Online Library catalogue system
-
Online Document Management Systems
-
Web Search Systems etc.
Note − 信息检索系统的主要问题是根据用户的查询在文档集合中定位相关文档。这种类型的用户查询由一些描述信息需求的关键词组成。
在这种搜索问题中,用户主动从集合中提取相关信息。当用户临时需要信息时,即短期需要时,这种方法比较合适。但是,如果用户长期需要信息,那么检索系统还可以主动将新到达的信息项目推送到用户。
这种访问信息的方式称为信息过滤。相应的系统称为过滤系统或推荐系统。
Basic Measures for Text Retrieval
当系统根据用户的输入检索大量文档时,我们需要检查系统的准确性。将与查询相关的文档集表示为 {Relevant},而将检索到的文档集表示为 {Retrieved}。既相关又检索到的文档集可以表示为 {Relevant} ∩ {Retrieved}。这可以通过以下韦恩图的形式展示 −
评估文本检索质量有三个基本度量 −
-
Precision
-
Recall
-
F-score
Data Mining - Mining World Wide Web
万维网包含大量的信息,为数据挖掘提供了丰富的来源。
Challenges in Web Mining
根据以下观察,网络对资源和知识发现提出了巨大挑战 −
-
The web is too huge −网络的规模非常庞大并且增长迅速。这表明网络对于数据仓库和数据挖掘来说太大。
-
Complexity of Web pages −网页没有统一的结构。与传统文本文档相比,它们非常复杂。网络的数字图书馆中有大量文档。这些图书馆没有按照任何特定排序顺序排列。
-
Web is dynamic information source −网络上的信息更新速度很快。诸如新闻、股票市场、天气、体育、购物等数据会定期更新。
-
Diversity of user communities −网络上的用户群正在迅速扩大。这些用户有着不同的背景、兴趣和使用目的。有超过 1 亿个工作站在连接互联网,并且仍在迅速增长中。
-
Relevancy of Information −据认为,特定的人通常只对网络的一小部分感兴趣,而网络的其余部分包含与用户不相关的信息,并且可能会淹没所需的结果。
Data Mining - Applications & Trends
数据挖掘在不同领域被广泛使用。现如今有许多可用的商业数据挖掘系统,但该领域仍面临许多挑战。在本教程中,我们将讨论数据挖掘的应用和趋势。
Data Mining Applications
以下列举了数据挖掘被广泛使用的领域 −
-
Financial Data Analysis
-
Retail Industry
-
Telecommunication Industry
-
Biological Data Analysis
-
Other Scientific Applications
-
Intrusion Detection
Financial Data Analysis
银行和金融业中的财务数据通常可靠且质量上乘,可促成系统化的数据分析和数据挖掘。一些典型情况如下 −
-
设计和构建用于多维数据分析和数据挖掘的数据仓库。
-
贷款支付预测和客户信贷政策分析。
-
对客户进行分类和分群,以进行有针对性的营销活动。
-
检测洗钱和其他金融犯罪行为。
Retail Industry
数据挖掘在零售业有很大的应用空间,因为它从销售、客户购买历史记录、货物运输、消费和服务中收集了大量数据。由于网络越来越方便、可用,并且越来越受欢迎,收集的数据量会继续快速增长,这是理所当然的。
零售业的数据挖掘有助于识别客户购买模式和趋势,从而提高客户服务质量,提升客户保留率和满意度。以下列举了零售业中数据挖掘的示例 −
-
基于数据挖掘优势设计和构建数据仓库。
-
对销售额、客户、产品、时间和区域进行多维分析。
-
分析销售活动的效果。
-
Customer Retention.
-
产品推荐和商品的交叉引用。
Telecommunication Industry
如今,电信行业是提供各种服务的最蓬勃发展的行业之一,例如传真、寻呼机、蜂窝电话、互联网信使、图像、电子邮件、网络数据传输等。由于新计算机和通信技术的发展,电信行业正在迅速扩张。这就是数据挖掘变得非常重要的原因,有助于业务的理解和开展。
电信行业的数据挖掘有助于识别电信模式、捕捉欺诈活动、更好地利用资源以及提高服务质量。以下列出了数据挖掘改善电信服务的一些示例:
-
电信数据的多维分析。
-
Fraudulent pattern analysis.
-
Identification of unusual patterns.
-
多维关联和序列模式分析。
-
Mobile Telecommunication services.
-
在电信数据分析中使用可视化工具。
Biological Data Analysis
近来,我们在生物学领域取得了巨大的发展,如基因组学、蛋白质组学、功能基因组学和生物医学研究。生物数据挖掘是生物信息学的重要组成部分。以下列出了数据挖掘在生物数据分析中发挥作用的方面:
-
异构、分布式基因组和蛋白质组数据库的语义集成。
-
多个核苷酸序列的对齐、索引、相似性搜索和比较分析。
-
结构模式的发现以及遗传网络和蛋白质途径的分析。
-
Association and path analysis.
-
遗传数据分析中的可视化工具。
Data Mining System Products
有许多数据挖掘系统产品和特定领域的数据挖掘应用程序。新的数据挖掘系统和应用程序正在添加到以前系统中。此外,我们正在努力对数据挖掘语言进行标准化。
Choosing a Data Mining System
数据挖掘系统取决于以下特性:
-
Data Types - 数据挖掘系统可以处理格式化文本、基于记录的数据和关系数据。数据还可以采用 ASCII 文本、关系数据库数据或数据仓库数据。因此,我们应该检查数据挖掘系统可以处理的确切格式。
-
System Issues −我们必须考虑数据挖掘系统与不同操作系统之间的兼容性。一个数据挖掘系统可能只运行在一个操作系统上或几个操作系统上。还有一些数据挖掘系统提供基于 Web 的用户界面,并将 XML 数据作为输入。
-
Data Sources −数据源是指数据挖掘系统将操作的数据格式。一些数据挖掘系统可能只处理 ASCII 文本文件,而另一些系统则处理多个关系数据源。数据挖掘系统还应该支持 ODBC 连接或 OLE DB for ODBC 连接。
-
Data Mining functions and methodologies −一些数据挖掘系统仅提供一个数据挖掘功能,例如分类,而另一些系统提供了多个数据挖掘功能,例如概念描述、发现驱动的 OLAP 分析、关联探矿、关联分析、统计分析、分类、预测、聚类、离群值分析、相似性搜索等。
-
Coupling data mining with databases or data warehouse systems −数据挖掘系统需要与数据库或数据仓库系统相结合。耦合组件集成到统一的信息处理环境中。以下是列出的耦合类型−无耦合松散耦合半紧耦合紧耦合
-
Scalability −在数据挖掘中有两个可扩展性问题− Row (Database size) Scalability −当行数增加 10 倍时,数据挖掘系统被认为是行可扩展的。执行查询所需的时间不超过 10 倍。 Column (Dimension) Salability −如果挖掘查询执行时间随列数线性增加,则数据挖掘系统被认为是列可扩展的。
-
Visualization Tools −数据挖掘中的可视化可以分类如下−数据可视化挖掘结果可视化挖掘过程可视化可视数据挖掘
-
Data Mining query language and graphical user interface −一个易于使用的图形用户界面对于促进用户指导的互动数据挖掘非常重要。与关系数据库系统不同,数据挖掘系统不共享底层数据挖掘查询语言。
Trends in Data Mining
数据挖掘的概念仍在不断发展,以下是我们在这个领域看到的最新趋势−
-
Application Exploration.
-
可扩展且交互的数据挖掘方法。
-
将数据挖掘与数据库系统、数据仓库系统和 web 数据库系统相集成。
-
数据挖掘查询语言标准化
-
Visual data mining.
-
挖掘复杂类型的数据新方法
-
Biological data mining.
-
数据挖掘和软件工程
-
Web mining.
-
Distributed data mining.
-
Real time data mining.
-
Multi database data mining.
-
数据挖掘中的隐私保护和信息安全
Data Mining - Themes
Theoretical Foundations of Data Mining
数据挖掘的理论基础包括以下概念 −
-
Data Reduction − 此理论的基本思想是减少数据表示,它为获得对大型数据库中查询的快速近似答案的需要带来了准确性以换取速度。一些数据缩减技术如下 − 奇异值分解 小波 回归 对数线性模型 直方图 聚类 采样 构造索引树
-
Data Compression − 此理论的基本思想是通过以下方式对给定数据进行编码来压缩给定数据 − 位 关联规则 决策树 集群
-
Pattern Discovery − 此理论的基本思想是在数据库中发现出现的模式。以下是对该理论有帮助的领域 − 机器学习 神经网络 关联挖掘 顺序模式匹配 聚类
-
Probability Theory − 此理论基于统计理论。该理论背后的基本思想是发现随机变量的联合概率分布。
-
Probability Theory − 根据该理论,数据挖掘仅会找到那些能够在某些企业的决策过程中使用的模式,并且具有有趣的特点。
-
Microeconomic View − 根据该理论,数据库模式包含存储在数据库中的数据和模式。因此,数据挖掘就是在数据库中执行归纳的任务。
-
Inductive databases − 除了面向数据库的技术之外,还可以使用统计技术进行数据分析。这些技术可以运用到科学数据、经济数据以及社会科学数据中。
Statistical Data Mining
以下是一些统计数据挖掘技术:
-
Regression − 回归方法用于根据一个或多个预测变量(其中变量为数字)预测自变量的值。下面列出回归的形式: 线性 多重 加权 多项式 非参数 稳健
-
Generalized Linear Models − 广义线性模型包括: 逻辑回归泊松回归该模型的推广允许对离散响应变量与一组预测变量相关,其方式类似于使用线性回归对数字响应变量建模的方式。
-
Analysis of Variance − 此技术分析: 经由数字响应变量描述的两个或更多总体之间的实验数据。一个或多个离散变量(因子)。
-
Mixed-effect Models − 这些模型用于分析分组数据。这些模型描述了响应变量与数据中某些协变量之间的关系,这些数据根据一个或多个因子分组。
-
Factor Analysis − 因子分析用于预测离散响应变量。此方法假设自变量遵循多元正态分布。
-
Time Series Analysis − 以下是用于分析时间序列数据的几种方法: 自回归方法。单变量 ARIMA(自回归综合移动平均值)建模。长记忆时间序列建模。
Visual Data Mining
可视化数据挖掘使用数据和/或知识可视化技术从大型数据集发现隐含知识。可视化数据挖掘可以看作以下学科的整合:
-
Data Visualization
-
Data Mining
可视化数据挖掘与以下内容密切相关:
-
Computer Graphics
-
Multimedia Systems
-
Human Computer Interaction
-
Pattern Recognition
-
High-performance Computing
通常,数据可视化和数据挖掘可以通过以下方式整合:
-
Data Visualization − 数据库或数据仓库中的数据可以用以下几种可视形式查看: 箱线图 3D 立方体 数据分布图 曲线曲面 链接图等。
-
Data Mining Result Visualization − 数据挖掘结果可视化是以可视形式呈现数据挖掘结果。这些可视形式可能是散点图、箱线图等。
-
Data Mining Process Visualization − 数据挖掘过程可视化展示了数据挖掘的几个过程。它能让用户了解如何提取数据。它还允许用户查看数据从哪个数据库或数据仓库中进行清理、整合、预处理和挖掘。