1、数据挖掘中的数据归约问题数据挖掘中的数据归约问题为什么需要数据挖掘为什么需要数据挖掘n数据爆炸问题数据爆炸问题 q自动数据收集工具和成熟的数据库技术使得大量自动数据收集工具和成熟的数据库技术使得大量的数据被收集，存储在数据库、数据仓库或其他的数据被收集，存储在数据库、数据仓库或其他信息库中以待分析。信息库中以待分析。n我们拥有丰富的数据，但却缺乏有用的信息我们拥有丰富的数据，但却缺乏有用的信息n数据爆炸但知识贫乏 http:/ http:/ http:/ (CRM)，市场占有量分析，交叉销售，目标市，市场占有量分析，交叉销售，目标市场场q风险分析和管理风险分析和管理n风险预测，客户保持，保险业
2、的改良，质量控制，竞争分析风险预测，客户保持，保险业的改良，质量控制，竞争分析q欺骗检测和异常模式的监测欺骗检测和异常模式的监测 (孤立点孤立点)n其他的应用其他的应用q文本挖掘文本挖掘 (新闻组，电子邮件，文档新闻组，电子邮件，文档) 和和Web挖掘挖掘q流数据挖掘流数据挖掘qDNA 和生物数据分析和生物数据分析2022-6-8数据挖掘中的特征选择5数据挖掘数据挖掘: : 数据库中的知识挖掘数据库中的知识挖掘(KDD)(KDD)n数据挖掘数据挖掘知识挖掘的核心知识挖掘的核心数据清理数据清理数据集成数据集成数据库数据库数据仓库数据仓库任务相关数据任务相关数据选择选择数据挖掘数据挖掘模式评估模式
3、评估2022-6-8数据挖掘中的特征选择6数据挖掘的步骤数据挖掘的步骤u了解应用领域了解应用领域u了解相关的知识和应用的目标了解相关的知识和应用的目标u创建目标数据集创建目标数据集: : 选择数据选择数据u数据清理和预处理数据清理和预处理: (: (这个可能要占全过程这个可能要占全过程6060的工作的工作量量) )u数据缩减和变换数据缩减和变换u找到有用的特征，维数缩减找到有用的特征，维数缩减/ /变量缩减，不变量的表示变量缩减，不变量的表示u选择数据挖掘的功能选择数据挖掘的功能 u数据总结数据总结, , 分类模型数据挖掘分类模型数据挖掘, , 回归分析回归分析, , 关联规则挖关联规则挖掘掘
4、, , 聚类分析等聚类分析等2022-6-8数据挖掘中的特征选择7u选择挖掘算法选择挖掘算法u数据挖掘数据挖掘: : 寻找感兴趣的模式寻找感兴趣的模式u模式评估和知识表示模式评估和知识表示u可视化，转换，消除冗余模式等等可视化，转换，消除冗余模式等等u运用发现的知识运用发现的知识2022-6-8数据挖掘中的特征选择8数据挖掘和商业智能数据挖掘和商业智能支持商业决策的支持商业决策的潜能不断增长潜能不断增长最终用户最终用户商业分析家商业分析家 数据分析家数据分析家DBA 决策支持决策支持数据表示数据表示可视化技术可视化技术数据挖掘数据挖掘信息发现信息发现数据探索数据探索在线分析处理（在线分析处理（
5、OLAP)OLAP)，多维分析，多维分析(MDA(MDA)统计分析，查询和报告统计分析，查询和报告数据仓库数据仓库/ /数据市场数据市场数据源数据源论文论文, , 文件文件, , 信息提供商信息提供商, , 数据库系统数据库系统, , 联机事务处理系统联机事务处理系统(OLTP(OLTP)2022-6-8数据挖掘中的特征选择9典型数据挖掘系统典型数据挖掘系统数据仓库数据仓库数据清洗数据清洗过滤过滤数据库数据库数据库或数据仓库服务器数据挖掘引擎模式评估图形用户界面知识库数据集成数据集成2022-6-8数据挖掘中的特征选择10数据挖掘数据挖掘: :多个学科的融合多个学科的融合数据挖掘数据挖掘数据库
6、系统统计学其他学科算法机器学习可视化2022-6-8数据挖掘中的特征选择11u预言预言（Predication）：）：用历史预测用历史预测未来未来u描述（描述（Description）：）：了解数据中了解数据中潜在的规律潜在的规律2022-6-8数据挖掘中的特征选择12u分类（分类（Classification）u聚类聚类(Clustering)u相关规则相关规则(Association Rule)u回归回归(Regression)u其他其他2022-6-8数据挖掘中的特征选择13u因为在文本分类、信息检索和生物信息学等数据挖掘的因为在文本分类、信息检索和生物信息学等数据挖掘的应用领域中，数据
7、的维数往往是很高的。应用领域中，数据的维数往往是很高的。u高维的数据集中包含了大量的特征高维的数据集中包含了大量的特征(属性属性)。比如一个文。比如一个文本数据集中，每一个文本都可以用一个向量来表示，向本数据集中，每一个文本都可以用一个向量来表示，向量中的每一个元素就是每一个词在该文本中出现的频率。量中的每一个元素就是每一个词在该文本中出现的频率。在这种情况下，这个数据集中就存在着成千上万的特征。在这种情况下，这个数据集中就存在着成千上万的特征。这种高维的数据给数据挖掘带来了这种高维的数据给数据挖掘带来了“维灾难维灾难”(The Curse of Dimensionality)问题。问题。 2
8、022-6-8数据挖掘中的特征选择14u特征选择和特征降维是两类特征归约方法。特征选择和特征降维是两类特征归约方法。2022-6-8数据挖掘中的特征选择15u特征选择的一般过程包括：首先从特征全集中产生出一特征选择的一般过程包括：首先从特征全集中产生出一个特征子集，然后用评价函数对该特征子集进行评价，个特征子集，然后用评价函数对该特征子集进行评价，评价的结果与停止准则进行比较，若评价结果比停止准评价的结果与停止准则进行比较，若评价结果比停止准则好就停止，否则就继续产生下一组特征子集，继续进则好就停止，否则就继续产生下一组特征子集，继续进行特征选择。选出来的特征子集一般还要验证其有效性。行特征选
9、择。选出来的特征子集一般还要验证其有效性。2022-6-8数据挖掘中的特征选择16n n特征选择的过程特征选择的过程 ( M. Dash and H. Liu 1997 )2022-6-8数据挖掘中的特征选择17u特征选择大体上可以看作是一个搜索过程，搜索空间中特征选择大体上可以看作是一个搜索过程，搜索空间中的每一个状态都可以看成是一个可能特征子集。的每一个状态都可以看成是一个可能特征子集。u搜索的算法分为完全搜索搜索的算法分为完全搜索(Complete)，启发式搜索，启发式搜索(Heuristic)，随机搜索，随机搜索(Random) 3大类。大类。 2022-6-8数据挖掘中的特征选择18
10、n完全搜索分为穷举搜索与非穷举搜索两类。完全搜索分为穷举搜索与非穷举搜索两类。n(1) 广度优先搜索广度优先搜索(BFS )n(2) 分支限界搜索分支限界搜索(BAB) n(3) 定向搜索定向搜索 (BS)n(4) 最优优先搜索最优优先搜索(Best First Search) 2022-6-8数据挖掘中的特征选择19n启发式搜索启发式搜索n(1) 序列前向选择序列前向选择(SFS)n(2) 序列后向选择序列后向选择(SBS)n(3) 双向搜索双向搜索(BDS)n(4) 增增L去去R选择算法选择算法 (LRS)n(5) 序列浮动选择序列浮动选择(Sequential Floating Sele
11、ction)n(6) 决策树决策树(DTM)2022-6-8数据挖掘中的特征选择20 随机算法随机算法n(1) 随机产生序列选择算法随机产生序列选择算法(RGSS)n(2) 模拟退火算法模拟退火算法(SA)n(3) 遗传算法遗传算法(GA)2022-6-8数据挖掘中的特征选择21u特征的评估函数分为五类：相关性，距离，信息增益，特征的评估函数分为五类：相关性，距离，信息增益，一致性和分类错误率。一致性和分类错误率。 u常 用 的 有 平 方 距 离 ， 欧 氏 距 离 ， 非 线 性 测 量 ，常 用 的 有 平 方 距 离 ， 欧 氏 距 离 ， 非 线 性 测 量 ，Minkowski距离
12、，信息增益，最小描述长度，互信息，距离，信息增益，最小描述长度，互信息，依赖性度量或相关性度量，一致性度量，分类错误率依赖性度量或相关性度量，一致性度量，分类错误率 ，分类正确率分类正确率 2022-6-8数据挖掘中的特征选择22u一般地，特征选择方法可以分为三种模型，分别是：过一般地，特征选择方法可以分为三种模型，分别是：过滤模型、封装模型和混合模型。滤模型、封装模型和混合模型。2022-6-8数据挖掘中的特征选择23u过滤模型：过滤模型：根据训练集进行特征选择，在特征选择的根据训练集进行特征选择，在特征选择的过程中并不涉及任何学习算法。即特征子集在学习算法过程中并不涉及任何学习算法。即特征
13、子集在学习算法运行之前就被单独选定。但学习算法用于测试最终特征运行之前就被单独选定。但学习算法用于测试最终特征子集的性能。子集的性能。u过滤模型简单且效率很高。由于过滤模型中的特征选择过滤模型简单且效率很高。由于过滤模型中的特征选择过程独立于学习算法，这就容易与后面的学习算法产生过程独立于学习算法，这就容易与后面的学习算法产生偏差，因此为了克服这个缺点提出了封装模型。偏差，因此为了克服这个缺点提出了封装模型。2022-6-8数据挖掘中的特征选择242022-6-8数据挖掘中的特征选择25u基于过滤模型的算法主要有两类：特征权重和子集搜索。基于过滤模型的算法主要有两类：特征权重和子集搜索。u这两
14、类算法的不同之处在于是对单个特征进行评价还是这两类算法的不同之处在于是对单个特征进行评价还是对整个特征子集进行评价。对整个特征子集进行评价。2022-6-8数据挖掘中的特征选择26u特征权重算法对每个特征指定一个权值，并按照它与目特征权重算法对每个特征指定一个权值，并按照它与目标概念的相关度对其进行排序，如果一个特征的相关度标概念的相关度对其进行排序，如果一个特征的相关度权值大于某个阈值，则认为该特征优秀，并且选择该特权值大于某个阈值，则认为该特征优秀，并且选择该特征。该算法缺点在于：他们可以捕获特征与目标概念间征。该算法缺点在于：他们可以捕获特征与目标概念间的相关性，却不能发现特征间的冗余性
15、。而经验证明除的相关性，却不能发现特征间的冗余性。而经验证明除了无关特征对学习任务的影响，冗余特征同样影响学习了无关特征对学习任务的影响，冗余特征同样影响学习算法的速度和准确性，也应尽可能消除冗余特征。算法的速度和准确性，也应尽可能消除冗余特征。Relief算法是一个比较著名的特征权重类方法。算法是一个比较著名的特征权重类方法。2022-6-8数据挖掘中的特征选择27u子集搜索算法通过在一定的度量标准指导下遍历候选特子集搜索算法通过在一定的度量标准指导下遍历候选特征子集，对每个子集进行优劣评价，当搜索停止时即可征子集，对每个子集进行优劣评价，当搜索停止时即可选出最优（或近似最优）的特征子集。选
16、出最优（或近似最优）的特征子集。2022-6-8数据挖掘中的特征选择28u封装模型：封装模型：在此模型中，学习算法封装在特征选择的在此模型中，学习算法封装在特征选择的过程中，用特征子集在学习算法上得到的挖掘性能作为过程中，用特征子集在学习算法上得到的挖掘性能作为特征子集优劣的评估准则。在初始特征空间内进行多次特征子集优劣的评估准则。在初始特征空间内进行多次搜索，直至得到最佳的特征子集。搜索，直至得到最佳的特征子集。u与过滤模型相比，封装模型具有更高的精度，但效率较与过滤模型相比，封装模型具有更高的精度，但效率较低，运行速度慢于过滤模型。低，运行速度慢于过滤模型。2022-6-8数据挖掘中的特征
17、选择292022-6-8数据挖掘中的特征选择30u过滤模型与包裹模型的根本区别在于对学习算法的使用过滤模型与包裹模型的根本区别在于对学习算法的使用方式。方式。 u混合模型：混合模型：由于过滤模型与封装模型之间的互补性，混合模型把这两种模型进行组合，也就是先用过滤模式进行初选，再用封装模型来获得最佳的特征子集。2022-6-8数据挖掘中的特征选择312022-6-8数据挖掘中的特征选择32u数据降维是指通过线性或非线性映射将样本空间从高维数据降维是指通过线性或非线性映射将样本空间从高维空间映射到低维空间。空间映射到低维空间。u降维方法主要分为两类：线性或非线性。降维方法主要分为两类：线性或非线性
18、。 2022-6-8数据挖掘中的特征选择33u数据降维是指通过线性或非线性映射将样本空间从高维数据降维是指通过线性或非线性映射将样本空间从高维空间映射到低维空间。空间映射到低维空间。u降维方法主要分为两类：线性或非线性。而非线性降维降维方法主要分为两类：线性或非线性。而非线性降维方法又可分为基于核函数和基于特征值的方法。方法又可分为基于核函数和基于特征值的方法。 2022-6-8数据挖掘中的特征选择34u线性降维方法有：线性降维方法有：u主成分分析主成分分析(PCA)，独立成分分析，独立成分分析(ICA)，线性判别分，线性判别分析析(PCA)，局部特征分析，局部特征分析(LFA) 。2022-
19、6-8数据挖掘中的特征选择35u基于核函数的非基于核函数的非线性降维方法有：线性降维方法有：u基于核函数的基于核函数的主成分分析主成分分析(KPCA)，基于核函数基于核函数独立成独立成分分(KICA)，基于核函数的基于核函数的判别分析判别分析(KLDA) 。u基于特征值基于特征值(流形流形)的非的非线性降维方法有：线性降维方法有：uISOMAP(Isometric feature mapping)，局部线，局部线性嵌入性嵌入(LLE)，拉普拉斯特征映射，拉普拉斯特征映射(LE) 。 2022-6-8数据挖掘中的特征选择36u结合结合LDA与二分与二分K均值聚类的特点，提出了针对高维数均值聚类的
20、特点，提出了针对高维数据集的自适应聚类方法。利用线性判别分析据集的自适应聚类方法。利用线性判别分析(LDA)来实来实现维归约，然后在低维数据集上执行二分现维归约，然后在低维数据集上执行二分k均值聚类来生均值聚类来生成类。低维空间的聚类结果又可以通过某种机制构造出成类。低维空间的聚类结果又可以通过某种机制构造出原数据集上的类。然后在此基础上再利用原数据集上的类。然后在此基础上再利用LDA进行维归进行维归约，这个过程反复进行下去，不断地修正前面得到的聚约，这个过程反复进行下去，不断地修正前面得到的聚类结果，直到得到全局最优。类结果，直到得到全局最优。 2022-6-8数据挖掘中的特征选择37u结合
21、某种基于标准化互信息和遗传算法提出所谓的两结合某种基于标准化互信息和遗传算法提出所谓的两阶段特征选择方法。该方法首先采用标准化的互信息阶段特征选择方法。该方法首先采用标准化的互信息对特征进行排序，然后使用排序在前的特征初始化第对特征进行排序，然后使用排序在前的特征初始化第二阶段遗传算法的部分种群，使得遗传算法的初始种二阶段遗传算法的部分种群，使得遗传算法的初始种群中含有较好的搜索起点，使遗传算法只采用较小的群中含有较好的搜索起点，使遗传算法只采用较小的进化代数就可搜寻到较优的特征子集。进化代数就可搜寻到较优的特征子集。 2022-6-8数据挖掘中的特征选择38u结合某种特征选择和智能优化算法研究新型的结合某种特征选择和智能优化算法研究新型的两阶段特征选择方法。利用已有的特征选择算两阶段特征选择方法。利用已有的特征选择算法得出一个特征子集，从而为智能优化算法提法得出一个特征子集，从而为智能优化算法提供一个较好的初始的搜索起点，然后利用智能供一个较好的初始的搜索起点，然后利用智能优化算法只采用较小的进化代数就可搜寻到较优化算法只采用较小的进化代数就可搜寻到较优的特征子集。优的特征子集。2022-6-8数据挖掘中的特征选择39
