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