机器学习与数据挖掘.ppt

机器学习与数据挖掘,样本准备（2）,2019年12月2日,MachineLearningandDatamining,2,样本准备,对象分割对象在文档中可能只占很小比例用整个文档提取的特征含有大量噪声特征与特征提取使用什么样的特征？如何计算？如何进行预处理？样本选择正负样本数可能严重失衡（1:10，1:100）样本可能包含噪声,2019年12月2日,MachineLearningandDatamining,3,特征,何为特征？Inpatternrecognition,featuresaretheindividualmeasurableheuristicpropertiesofthephenomenabeingobserved.Incomputervisionandimageprocessingtheconceptoffeatureisusedtodenoteapieceofinformationwhichisrelevantforsolvingthecomputationaltaskrelatedtoacertainapplication.,2019年12月2日,MachineLearningandDatamining,4,特征,何为特征？特征：实体（或事物、概念）区别于其它实体（事物、概念）的独特的属性,特征=特+征,性质,独特的特殊的,有比较，才有独特、特殊,2019年12月2日,MachineLearningandDatamining,5,特征,特征的属性独特性目标实体和非目标实体有不同的取值范围确定性特征，概率性特征可计算性以可接受的代价从目标实体采集数据并计算出来特征的成本特征的质量（噪声）,2019年12月2日,MachineLearningandDatamining,6,特征,特征组的属性完备性可以完全区分目标实体和非目标实体必要性对区分目标实体和非目标实体是否必要独立性特征之间是否相关,2019年12月2日,MachineLearningandDatamining,7,特征,特征的种类（应用意义上）多媒体特征（视觉、听觉特征）颜色、纹理、形状频率、节奏文字/关键字特征字频、词频元数据特征目录名、链接、链接文字、日期,2019年12月2日,MachineLearningandDatamining,8,特征提取,何为特征提取？从原始数据计算出特征的数值（或模型）特征提取须考虑的问题可计算性特征提取时，数据采集往往已经完成，特征提取不具备采用不同数据采集手段的灵活性成本计算复杂度，吞吐率，延迟，人力开销噪声很多多媒体特征提取准确率低,2019年12月2日,MachineLearningandDatamining,9,特征提取,像素特征直接用像素的颜色值表示特征实现简单信息质量差仅包含单个像素的信息同时包含需要的信息和不需要的噪声难以表示全局信息后续分类和处理困难,2019年12月2日,MachineLearningandDatamining,10,特征提取,颜色特征颜色是人眼非常敏感的特征如何提取和表示颜色特征？平均颜色把所有像素的颜色值当作矢量，计算所有像素的颜色矢量的算术平均,2019年12月2日,MachineLearningandDatamining,11,特征提取,颜色特征颜色矩如果把像素看成随机变量，则其分布特性可以由矩来描述一阶矩(均值)：二阶中心矩(标准差):三阶中心矩:维数低，易于计算信息量少，对噪声敏感,2019年12月2日,MachineLearningandDatamining,12,特征提取,颜色特征颜色直方图直方图：概率密度函数颜色：三维如何统计直方图？方法1：三维颜色直方图直方图的每个槽对应一组（R,G,B）矢量值RGB均0255直方图有256*256*256=16M个槽图像像素数：704*576=405K,1920*1080=2M统计直方图需要使用较粗的量化一般量化成16级16*16*16=4096个槽维数仍然很高,2019年12月2日,MachineLearningandDatamining,13,特征提取,颜色特征颜色直方图方法2：三个一维直方图对R、G、B三个颜色分别统计一个直方图不进一步量化：256+256+256=768维每种颜色量化成16级：16+16+16=48维优点：维数大大降低缺点：颜色之间的相关信息丢失在较独立的颜色空间统计（如：YUV，HSI）亮度统计一维直方图，色度统计二维直方图直方图的维数仍然较高,2019年12月2日,MachineLearningandDatamining,14,特征提取,颜色特征聚类颜色直方图普通颜色直方图不管图像本身的颜色分布，整个颜色空间的所有颜色都是直方图的槽维数高必须覆盖整个颜色空间精度差对颜色空间的机械分割为了在合理的维数内实现，颜色空间的划分很粗利用图像本身的像素进行聚类，用聚类中心作为直方图的槽不同图像的直方图各维没有统一的物理含义,2019年12月2日,MachineLearningandDatamining,15,特征提取,纹理特征纹理：临近像素的变化趋势和模式一定尺度内的一种分布模式可以是固定的模式：如砖墙可以是概率的模式：如草地与像素的绝对颜色/亮度关系较小与颜色/亮度差异关系大,2019年12月2日,MachineLearningandDatamining,16,特征提取,纹理特征灰度共生矩阵两个有固定空间关系的像素的联合概率密度函数,空间关系,2019年12月2日,MachineLearningandDatamining,17,特征提取,纹理特征灰度共生矩阵超高的维数空间关系有很多个每个空间关系有一个二维直方图在这些二维直方图上作“二次统计”以降低维数角二阶矩（能量）、对比度（惯性矩）、相关、熵、逆差矩等与人类视觉对纹理的心理感知不同,2019年12月2日,MachineLearningandDatamining,18,特征提取,纹理特征Tamura纹理特征依据心理视觉特性定义的纹理特征计算准确率较差，信息量较少,稀疏度对比度方向性线状性规则性粗糙度,2019年12月2日,MachineLearningandDatamining,19,特征提取,纹理特征频率域的纹理特征纹理是“变化趋势和模式”在某个频率上有突出的特征利用频率变换表示纹理特征小波纹理特征对图像作小波变换计算小波的一阶矩和二阶矩作为纹理特征,2019年12月2日,MachineLearningandDatamining,20,特征提取,纹理特征频率域的纹理特征局部傅立叶变换纹理特征在局部邻域(3x3,4x4,5x5窗口)内作傅立叶变换，用傅立叶系数作为纹理特征Gabor变换频率空间中的局部区域特征,2019年12月2日,MachineLearningandDatamining,21,特征提取,纹理特征频率域的纹理特征Gabor变换频率空间中取某个窗口内的系数来提取特征,2019年12月2日,MachineLearningandDatamining,22,特征提取,形状特征面积(A)、周长(P)、质心(O)长度(L)、宽度(W),2019年12月2日,MachineLearningandDatamining,23,特征提取,形状特征矩形度：面积和最小外接矩形面积的比值长宽比：L/W圆度：欧拉数拓扑特征难以精确提取,信息量小,2019年12月2日,MachineLearningandDatamining,24,特征提取,形状特征轮廓的高维特征把轮廓坐标转换成一维复数序列一维复函数可以进行傅立叶变换，提取频率特征傅立叶描述子,2019年12月2日,MachineLearningandDatamining,25,特征提取,文字特征文字的基本单位字/字母，词西方文字：字母并无显著语义中文：“字”接近于词字频早期中文处理技术及少数简单的中文处理应用词频及词频衍生特征大多数文字处理应用如何获得“词”?,2019年12月2日,MachineLearningandDatamining,26,特征提取,分词（Tokenlize/Lexicon）输入：字符串例：“Friends,Romans,countrymen”例：“华东师范大学”输出：词（token）Friends华东Romans师范countrymen大学词经过后处理可以作为提取词频的依据就这么简单？,2019年12月2日,MachineLearningandDatamining,27,分词,问题FinlandscapitalFinland?Finlands?Finlands?Hewlett-Packard1个词？2个？State-of-the-art？thehold-him-back-and-drag-him-away-maneuver?Lensemble1个词？2个？L?L?Le?,不同的系统使用不同的方法,2019年12月2日,MachineLearningandDatamining,28,分词,各种数字形式3/12/91Mar.12,199155B.C.B-52MyPGPkeyis324a3df234cb23e100.2.86.144+86-21-62235089,2019年12月2日,MachineLearningandDatamining,29,分词,基本算法正则式匹配例：普通的英文日期0-91,2“/”0-91,2“/”0-92,4例：普通的英文单词a-zA-Z+一个西欧语言的分词可能需要数十条正则式使用flex或re2c可以方便地开发英语的分词flex程序例：请从主页下载练习：用re2c写一个结构更好的英语分词程序不用提交,2019年12月2日,MachineLearningandDatamining,30,分词,问题SanFrancisco1个词？2个？SanFrancisco-LasVegas德语复合名词不加空格Lebensversicherungsgesellschaftsangestellterlifeinsurancecompanyemployee中文和日文没有空格“华东师范大学软件学院”,分词是一个大问题！,2019年12月2日,MachineLearningandDatamining,31,分词,基于词典的分词,华盛顿有意见分歧,华盛顿/有/意见/分歧,2019年12月2日,MachineLearningandDatamining,32,分词,基于词典的分词“感冒清胶囊”感冒/清/胶囊感冒清/胶囊,感冒感冒清,最大匹配原则：匹配词典中最长的词,2019年12月2日,MachineLearningandDatamining,33,分词,基于词典的分词“有意见分歧”有意/见/分歧有/意见/分歧“中国人民”中国人/民中国/人民,对中文：反向匹配准确率较高,2019年12月2日,MachineLearningandDatamining,34,分词,基于词典的分词“实在感觉英雄无用武之地方能拍案而起”实在/感觉/英雄无用武之地/方/能/拍案而起实在/感觉/英雄/无用/武/之/地方/能/拍案而起,双向匹配：正反两个方向分别分词，选择词数较小的结果,优点：准确率较高缺点：慢,2019年12月2日,MachineLearningandDatamining,35,分词,基于词典的分词其它语言中的应用日语、朝鲜语：相同算法即可英语：识别空格分隔的词（如：LasVegas）把空格分隔的每部分当作“字”即可德语：识别连写的复合名词把字母当作“字”即可练习：实现基于词典的英语常用复词检测不需要提交,2019年12月2日,MachineLearningandDatamining,36,分词,基于词典的分词如何快速查找词典？为词典建立索引结构最简单：二分查找结构：排序的数组复杂度：O(logn)优点：最简单的实现缺点：键插入、删除困难，对不定长键效率不高如何改进？,2019年12月2日,MachineLearningandDatamining,37,分词,基于词典的分词二叉树(binary-tree)结构：二叉树（废话）复杂度：O(logn)优点：键插入、删除较容易，对不定长键效率高缺点：大量插入删除键后可能退化按某个顺序插入，则二叉树可能退化成链表如何解决？,2019年12月2日,MachineLearningandDatamining,38,分词,基于词典的分词B树(B:balance)结构：多叉树每个节点允许a,b个子节点复杂度：O(logn)与二叉树一样！优点：可以一定程度上克服二叉树退化的缺点缺点：复杂度还是较高,2019年12月2日,MachineLearningandDatamining,39,分词,基于词典的分词Hash表Hash函数：把键转换成整数相同的间转换成相同的数不同的键尽可能转换成不同的数把键放在根据键转换出的整数为标号的桶中多个键映射到一个桶？拉链法：用链表组织桶的存储结构其它办法：,桶(bucket),2019年12月2日,MachineLearningandDatamining,40,分词,基于词典的分词Hash表如何设计Hash函数？不知道！常用：移位异或：H(X)=(x1x2)2.8,30-100/s,关,70-200/470mm291s关,瀑布,185520mm41s防红眼,夜间留影,更详细信息参考课程主页给出的论文,2019年12月2日,MachineLearningandDatamining,70,特征提取,元数据特征元数据特征的失败案例元数据特征也不是万能的,2019年12月2日,MachineLearningandDatamining,71,特征提取,多模特征(multi-modalfeature)单一特征难以保留足够信息仅能保留特征所针对的信息结合多个特征，以保留更多信息颜色、纹理、形状维数显著增加特征降维特征选取(FeatureSelection),2019年12月2日,MachineLearningandDatamining,72,样本准备,对象分割对象在文档中可能只占很小比例用整个文档提取的特征含有大量噪声特征与特征提取使用什么样的特征？如何计算？如何进行预处理？样本选择正负样本数可能严重失衡（1:10，1:100）样本可能包含噪声,2019年12月2日,MachineLearningandDatamining,73,样本选择,训练样本分布往往失衡(skewed)正样本通常是少数负样本占绝大多数负样本获取成本低各种计算机视觉应用正样本本身比例小疾病、变异、异常,CYT463NUC429MIT244ME3163ME251ME144EXC37VAC30POX20ERL5,UCIyeast,UCIBalanceScale,balance49left288right288,UCIAnnealing,18288360840560U34,2019年12月2日,MachineLearningandDatamining,74,样本选择,失衡的训练样本导致训练困难例：正负样本1:99把全部样本分类为负样本分类“准确率”99%完全没有应用价值的分类器！机器学习算法的假设训练样本的分布正确地刻画了正负样本在现实世界的分布特性所有样本分类错误的代价相同失衡训练样本的学习困难,2019年12月2日,MachineLearningandDatamining,75,样本选择,有关失衡样本方面的研究AAAI-2000WorkshoponLearningfromImbalancedDataSets“ICML-2000WorkshopCost-SensitiveLearning“ICML2003Workshop:LearningfromImbalancedDataSetsII,2019年12月2日,MachineLearningandDatamining,76,样本选择,目前提出的解决途径Cost-sensitivelearning给每个训练样本指定不同的错分代价但是代价究竟是多少？如何计算？单类学习(one-sidelearning)只对大类的分布进行学习，小类按例外检测来做部分分类器对失衡不太敏感SVM等几何分类器失衡在一定范围、问题难度不太高、样本充足时才不敏感，极度失衡仍然效果不好,2019年12月2日,MachineLearningandDatamining,77,样本选择,目前提出的解决途径样本采样上采样：把少数样