机器学习与数据挖掘.ppt

机器学习与数据挖掘 样本准备 2 2020年3月18日 MachineLearningandDatamining 2 样本准备 对象分割对象在文档中可能只占很小比例用整个文档提取的特征含有大量噪声特征与特征提取使用什么样的特征 如何计算 如何进行预处理 样本选择正负样本数可能严重失衡 1 10 1 100 样本可能包含噪声 2020年3月18日 MachineLearningandDatamining 3 特征 何为特征 Inpatternrecognition featuresaretheindividualmeasurableheuristicpropertiesofthephenomenabeingobserved Incomputervisionandimageprocessingtheconceptoffeatureisusedtodenoteapieceofinformationwhichisrelevantforsolvingthecomputationaltaskrelatedtoacertainapplication 2020年3月18日 MachineLearningandDatamining 4 特征 何为特征 特征 实体 或事物 概念 区别于其它实体 事物 概念 的独特的属性 特征 特 征 性质 独特的特殊的 有比较 才有独特 特殊 2020年3月18日 MachineLearningandDatamining 5 特征 特征的属性独特性目标实体和非目标实体有不同的取值范围 确定性特征 概率性特征可计算性以可接受的代价从目标实体采集数据并计算出来 特征的成本 特征的质量 噪声 2020年3月18日 MachineLearningandDatamining 6 特征 特征组的属性完备性可以完全区分目标实体和非目标实体必要性对区分目标实体和非目标实体是否必要独立性特征之间是否相关 2020年3月18日 MachineLearningandDatamining 7 特征 特征的种类 应用意义上 多媒体特征 视觉 听觉特征 颜色 纹理 形状 频率 节奏 文字 关键字特征字频 词频 元数据特征目录名 链接 链接文字 日期 2020年3月18日 MachineLearningandDatamining 8 特征提取 何为特征提取 从原始数据计算出特征的数值 或模型 特征提取须考虑的问题可计算性特征提取时 数据采集往往已经完成 特征提取不具备采用不同数据采集手段的灵活性成本计算复杂度 吞吐率 延迟 人力开销 噪声很多多媒体特征提取准确率低 2020年3月18日 MachineLearningandDatamining 9 特征提取 像素特征直接用像素的颜色值表示特征实现简单信息质量差仅包含单个像素的信息同时包含需要的信息和不需要的噪声难以表示全局信息后续分类和处理困难 2020年3月18日 MachineLearningandDatamining 10 特征提取 颜色特征颜色是人眼非常敏感的特征如何提取和表示颜色特征 平均颜色把所有像素的颜色值当作矢量 计算所有像素的颜色矢量的算术平均 2020年3月18日 MachineLearningandDatamining 11 特征提取 颜色特征颜色矩如果把像素看成随机变量 则其分布特性可以由矩来描述一阶矩 均值 二阶中心矩 标准差 三阶中心矩 维数低 易于计算信息量少 对噪声敏感 2020年3月18日 MachineLearningandDatamining 12 特征提取 颜色特征颜色直方图直方图 概率密度函数颜色 三维 如何统计直方图 方法1 三维颜色直方图直方图的每个槽对应一组 R G B 矢量值RGB均0 255 直方图有256 256 256 16M个槽 图像像素数 704 576 405K 1920 1080 2M 统计直方图需要使用较粗的量化一般量化成16级 16 16 16 4096个槽维数仍然很高 2020年3月18日 MachineLearningandDatamining 13 特征提取 颜色特征颜色直方图方法2 三个一维直方图对R G B三个颜色分别统计一个直方图不进一步量化 256 256 256 768维每种颜色量化成16级 16 16 16 48维优点 维数大大降低缺点 颜色之间的相关信息丢失在较独立的颜色空间统计 如 YUV HSI 亮度统计一维直方图 色度统计二维直方图直方图的维数仍然较高 2020年3月18日 MachineLearningandDatamining 14 特征提取 颜色特征聚类颜色直方图普通颜色直方图不管图像本身的颜色分布 整个颜色空间的所有颜色都是直方图的槽维数高必须覆盖整个颜色空间精度差对颜色空间的机械分割为了在合理的维数内实现 颜色空间的划分很粗 利用图像本身的像素进行聚类 用聚类中心作为直方图的槽不同图像的直方图各维没有统一的物理含义 2020年3月18日 MachineLearningandDatamining 15 特征提取 纹理特征纹理 临近像素的变化趋势和模式一定尺度内的一种分布模式可以是固定的模式 如砖墙可以是概率的模式 如草地与像素的绝对颜色 亮度关系较小与颜色 亮度差异关系大 2020年3月18日 MachineLearningandDatamining 16 特征提取 纹理特征灰度共生矩阵两个有固定空间关系的像素的联合概率密度函数 空间关系 2020年3月18日 MachineLearningandDatamining 17 特征提取 纹理特征灰度共生矩阵超高的维数空间关系有很多个每个空间关系有一个二维直方图 在这些二维直方图上作 二次统计 以降低维数角二阶矩 能量 对比度 惯性矩 相关 熵 逆差矩等与人类视觉对纹理的心理感知不同 2020年3月18日 MachineLearningandDatamining 18 特征提取 纹理特征Tamura纹理特征依据心理视觉特性定义的纹理特征计算准确率较差 信息量较少 稀疏度对比度方向性线状性规则性粗糙度 2020年3月18日 MachineLearningandDatamining 19 特征提取 纹理特征频率域的纹理特征纹理是 变化趋势和模式 在某个频率上有突出的特征 利用频率变换表示纹理特征小波纹理特征对图像作小波变换计算小波的一阶矩和二阶矩作为纹理特征 2020年3月18日 MachineLearningandDatamining 20 特征提取 纹理特征频率域的纹理特征局部傅立叶变换纹理特征在局部邻域 3x3 4x4 5x5 窗口 内作傅立叶变换 用傅立叶系数作为纹理特征Gabor变换频率空间中的局部区域特征 2020年3月18日 MachineLearningandDatamining 21 特征提取 纹理特征频率域的纹理特征Gabor变换频率空间中取某个窗口内的系数来提取特征 2020年3月18日 MachineLearningandDatamining 22 特征提取 形状特征面积 A 周长 P 质心 O 长度 L 宽度 W 2020年3月18日 MachineLearningandDatamining 23 特征提取 形状特征矩形度 面积和最小外接矩形面积的比值长宽比 L W圆度 欧拉数拓扑特征难以精确提取 信息量小 2020年3月18日 MachineLearningandDatamining 24 特征提取 形状特征轮廓的高维特征把轮廓坐标转换成一维复数序列 一维复函数 可以进行傅立叶变换 提取频率特征 傅立叶描述子 2020年3月18日 MachineLearningandDatamining 25 特征提取 文字特征文字的基本单位字 字母 词西方文字 字母并无显著语义中文 字 接近于词字频早期中文处理技术及少数简单的中文处理应用词频及词频衍生特征大多数文字处理应用 如何获得 词 2020年3月18日 MachineLearningandDatamining 26 特征提取 分词 Tokenlize Lexicon 输入 字符串例 Friends Romans countrymen 例 华东师范大学 输出 词 token Friends华东Romans师范countrymen大学词经过后处理可以作为提取词频的依据就这么简单 2020年3月18日 MachineLearningandDatamining 27 分词 问题Finland scapital Finland Finlands Finland s Hewlett Packard 1个词 2个 State of the art thehold him back and drag him away maneuver L ensemble1个词 2个 L L Le 不同的系统使用不同的方法 2020年3月18日 MachineLearningandDatamining 28 分词 各种数字形式3 12 91Mar 12 199155B C B 52MyPGPkeyis324a3df234cb23e100 2 86 144 86 21 62235089 2020年3月18日 MachineLearningandDatamining 29 分词 基本算法正则式匹配例 普通的英文日期 0 9 1 2 0 9 1 2 0 9 2 4 例 普通的英文单词 a zA Z 一个西欧语言的分词可能需要数十条正则式使用flex或re2c可以方便地开发英语的分词flex程序例 请从主页下载练习 用re2c写一个结构更好的英语分词程序 不用提交 2020年3月18日 MachineLearningandDatamining 30 分词 问题SanFrancisco 1个词 2个 SanFrancisco LasVegas德语复合名词不加空格Lebensversicherungsgesellschaftsangestellter lifeinsurancecompanyemployee 中文和日文没有空格 华东师范大学软件学院 分词是一个大问题 2020年3月18日 MachineLearningandDatamining 31 分词 基于词典的分词 华盛顿有意见分歧 华盛顿 有 意见 分歧 2020年3月18日 MachineLearningandDatamining 32 分词 基于词典的分词 感冒清胶囊 感冒 清 胶囊感冒清 胶囊 感冒感冒清 最大匹配原则 匹配词典中最长的词 2020年3月18日 MachineLearningandDatamining 33 分词 基于词典的分词 有意见分歧 有意 见 分歧有 意见 分歧 中国人民 中国人 民中国 人民 对中文 反向匹配准确率较高 2020年3月18日 MachineLearningandDatamining 34 分词 基于词典的分词 实在感觉英雄无用武之地方能拍案而起 实在 感觉 英雄无用武之地 方 能 拍案而起实在 感觉 英雄 无用 武 之 地方 能 拍案而起 双向匹配 正反两个方向分别分词 选择词数较小的结果 优点 准确率较高缺点 慢 2020年3月18日 MachineLearningandDatamining 35 分词 基于词典的分词其它语言中的应用日语 朝鲜语 相同算法即可英语 识别空格分隔的词 如 LasVegas 把空格分隔的每部分当作 字 即可德语 识别连写的复合名词把字母当作 字 即可练习 实现基于词典的英语常用复词检测不需要提交 2020年3月18日 MachineLearningandDatamining 36 分词 基于词典的分词如何快速查找词典 为词典建立索引结构最简单 二分查找结构 排序的数组复杂度 O logn 优点 最简单的实现缺点 键插入 删除困难 对不定长键效率不高 如何改进 2020年3月18日 MachineLearningandDatamining 37 分词 基于词典的分词二叉树 binary tree 结构 二叉树 废话 复杂度 O logn 优点 键插入 删除较容易 对不定长键效率高缺点 大量插入删除键后可能退化按某个顺序插入 则二叉树可能退化成链表 如何解决 2020年3月18日 MachineLearningandDatamining 38 分词 基于词典的分词B树 B balance 结构 多叉树每个节点允许 a b 个子节点复杂度 O logn 与二叉树一样 优点 可以一定程度上克服二叉树退化的缺点缺点 复杂度还是较高 2020年3月18日 MachineLearningandDatamining 39 分词 基于词典的分词Hash表Hash函数 把键转换成整数相同的间转换成相同的数不同的键尽可能转换成不同的数把键放在根据键转换出的整数为标号的桶中 多个键映射到一个桶 拉链法 用链表组织桶的存储结构其它办法 桶 bucket 2020年3月18日 MachineLearningandDatamining 40 分词 基于词典的分词Hash表如何设计Hash函数 不知道 常用 移位异或 H X x1 x2 1 x3 多少个桶 与键的数量大致相当复杂度 O 1 与键的个数无关 前提 优秀的Hash函数 桶的个数足够多 2020年3月18日 MachineLearningandDatamining 41 分词 基于词典的分词Hash表缺点添加大量键后性能可能下降 桶数量不够了 冲突大的桶检索性能低 如何解决 2020年3月18日 MachineLearningandDatamining 42 分词 基于词典的分词Trie结构 Trie Retrieval 2020年3月18日 MachineLearningandDatamining 43 分词 基于词典的分词Trie结构复杂度以键为基准 O 1 以字符为基准 O m 与Hash表比谁快 不知道 优点性能与插入删除顺序无关性能与键值多少基本无关 2020年3月18日 MachineLearningandDatamining 44 分词 基于词典的分词Trie结构缺点结构较大 占用内存大插入删除算法比较复杂哪种结构最好 应根据实际应用而定小词典 简单文字处理 hash表 二分查找大词典 大规模索引 Trie结构动态词典 经常修改的索引 B树 二叉树 2020年3月18日 MachineLearningandDatamining 45 分词 基于词典的分词 华东师范大学 1词 3词 我的意见 4词 用Trie结构很容易实现 中国人民万岁 中国人 民 万岁中国 人民 万岁新词 首尔 2020年3月18日 MachineLearningandDatamining 46 分词 其它分词技术基于概率可以有很复杂的模型基于自然语言理解更复杂 慢 复合分词结合多种分词技术先用匹配算法 发现歧义再使用复杂技术 2020年3月18日 MachineLearningandDatamining 47 分词 更简单的方法 不分词N gram 中国人民 中 国 人 民中国 国人 人民中国人 国人民中国人民优点 避免了分词的难题缺点 处理很复杂 计算量大可以用于小规模的系统 全部用于计算 2020年3月18日 MachineLearningandDatamining 48 语言问题 最常用的词是无意义的词aanandareasatbebyforfrom 可以没有非常很特别 占总词数的40 50 消耗40 50 的处理时间在特征中占据40 50 的信息噪声 2020年3月18日 MachineLearningandDatamining 49 语言问题 禁用词表 stoplist 一个最常用但是无意义的词的词典不把这个词典中的词加入词典问题Phonecardto fromGermanyAswemaythinkTobeornottobe 2020年3月18日 MachineLearningandDatamining 50 语言问题 禁用词表 stoplist 作为文本特征用较大的禁用词表 以消除噪声影响早期的检索系统用较大的禁用词表 200 300词 硬件能力较低现代检索系统用较小的禁用词表 20词以内 或不用硬件较强使用针对高频词优化的检索算法例 检索关键字按词频排序大型搜索引擎 Google 使用禁用词表 规模未知 2020年3月18日 MachineLearningandDatamining 51 语言问题 一个词可能有不同的形式日语有平假名 片假名 汉字 罗马字Accents 变音符 r sum resumeTuebingenT bingen 500社 情報不足 時間 500K 約6 000万円 2020年3月18日 MachineLearningandDatamining 52 语言问题 变形和同义词U S A U S USA UnitedStatesWindows windowswas were is be中国 中华人民共和国上海 沪 申一月十七日1月17日 月 日正月腊月廿卅 2020年3月18日 MachineLearningandDatamining 53 语言问题 归一化方法1 等价类把所有等价词都归一化到一个等价类索引 特征中只保留等价类对检索应用 查询关键字也要先转换成等价类简单 高效方法2 查询扩展 检索系统 把查询关键字扩展成等价类中所有词的或索引中保留所有词灵活windows Windows windows windowwindow windows window 现实系统 两个方法同时使用 2020年3月18日 MachineLearningandDatamining 54 语言问题 构造等价类词典Accents 变音符 基于字母的单向映射 e ue为何不反向映射 用户一般输入无accent的词查询缩写归一化U S A USA 2020年3月18日 MachineLearningandDatamining 55 语言问题 构造等价类词典小写化 case folding 把所有字母转换成小写US us C A T CAT cat 把句子的第一个字母小写化 把标题中全部大写的词小写化 其它词保留原大小写用户会输入全部小写的查询 2020年3月18日 MachineLearningandDatamining 56 语言问题 构造等价类词典词干 stemming 使用简单规则把词尾变形部分切除Porter算法规则示例 sses ssies iational atetional tion m 1 EMENT replacement replaccement cement 2020年3月18日 MachineLearningandDatamining 57 语言问题 构造等价类词典词干 stemming 好例子colors color坏例子apples appl非常坏的例子operateoperatingoperatesoperationoperativeoperativesoperational oper 2020年3月18日 MachineLearningandDatamining 58 语言问题 构造等价类词典词形分类 lemmatization lemma 进行自然语言处理 分析词的变形需要较高级的技术 处理复杂Isawher Iseeher Ibuyasaw Ibuyasaw 性能提升 与词干比较 英语检索 很少等价类才是检索的关键非英语检索 有一些特征提取 语义处理 非常有用如果结果需要显示给人看的话 2020年3月18日 MachineLearningandDatamining 59 语言问题 构造等价类词典同义词carautomobile上海沪申没有好的办法手工或半手工构造一般使用查询扩展实现 2020年3月18日 MachineLearningandDatamining 60 语言问题 拼写矫正 spellcorrection object pbject ibjectOCR Dbject方法1 编辑距离 editdistance 把一个词通过基本编辑操作转变成另一个词需要的操作个数常用操作 插入 删除 替换例 cat dog3 2020年3月18日 MachineLearningandDatamining 61 语言问题 拼写矫正编辑距离详情见 C 0 Cu du 1 1 Cl dl 1 1 Cul dul c 0 0 12345 123412342123321243215432 插入L 替换U为A 2020年3月18日 MachineLearningandDatamining 62 语言问题 拼写矫正方法2 加权编辑距离o i p l 0 D键盘 o i p l 0OCR o 0 D计算方法类似 2020年3月18日 MachineLearningandDatamining 63 语言问题 近音替换chebyshev tchebycheff使用拼音文字的用户更常犯拼写错误真心诚意 正心诚意后一个 Sogou拼音输入法词库第一条好像现在很多人用 2020年3月18日 MachineLearningandDatamining 64 语言问题 近音替换Soundex保留首字母后续字母转换成数字0 A E I O U H W Y1 B F P V2 C G J K Q S X Z3 D T4 L5 M N6 R 2020年3月18日 MachineLearningandDatamining 65 语言问题 近音替换Soundex保留首字母后续字母转换成数字归并相邻的连续数字删除0末尾补0返回前4个字符 Herman H 06505 H655 000 2020年3月18日 MachineLearningandDatamining 66 语言问题 近音替换同音词典中城药 重城药 中成药落花世界有风军 落花时节又逢君查询词 拼音 查询同音词典 推荐百度特征提取中可以使用吗 如何使用 2020年3月18日 MachineLearningandDatamining 67 特征提取 元数据特征何为元数据 metadata Wikipedia Metadatais dataaboutotherdata 元数据是描述目标文档 实体 对象的数据标题 关键字 分类 文件名 链接 日期 大小 位置 速度 亮度 镜头 焦距 光圈 快门速度 元数据有可能直接或间接描述文档 实体 对象内容元数据无须处理即可较好地作为特征使用元数据也可能与文档 实体 对象内容毫无关系 2020年3月18日 MachineLearningandDatamining 68 特征提取 元数据特征元数据特征应用案例1 实时交通信息目标 实时自动感知整个城市各道路交通状况直接方案 架设大量摄像头 通过计算机视觉计算道路上车辆数量和速度成本较高 算法难度极大 天气不好几乎无法使用间接方案 在汽车上安装GPS和通信装置 通过GPS报告的位置速度信息反演计算算法难度不大 实现精度很高 基本不受天气影响成本极高 大多数汽车不可控所有出租车已经安装 使用出租车已经安装的装置 2020年3月18日 MachineLearningandDatamining 69 特征提取 元数据特征元数据特征应用案例2 照片分类不同类型的照片往往使用非常不同的拍摄参数 镜头焦距光圈快门速度闪光灯 人像 定焦头 50 150mm 2 8 30 100 s 关 70 200 470mm291s关 瀑布 18 5520mm41s防红眼 夜间留影 更详细信息参考课程主页给出的论文 2020年3月18日 MachineLearningandDatamining 70 特征提取 元数据特征元数据特征的失败案例元数据特征也不是万能的 2020年3月18日 MachineLearningandDatamining 71 特征提取 多模特征 multi modalfeature 单一特征难以保留足够信息仅能保留特征所针对的信息 结合多个特征 以保留更多信息颜色 纹理 形状维数显著增加 特征降维特征选取 FeatureSelection 2020年3月18日 MachineLearningandDatamining 72 样本准备 对象分割对象在文档中可能只占很小比例用整个文档提取的特征含有大量噪声特征与特征提取使用什么样的特征 如何计算 如何进行预处理 样本选择正负样本数可能严重失衡 1 10 1 100 样本可能包含噪声 2020年3月18日 MachineLearningandDatamining 73 样本选择 训练样本分布往往失衡 skewed 正样本通常是少数负样本占绝大多数 负样本获取成本低各种计算机视觉应用 正样本本身比例小疾病 变异 异常 CYT463NUC429MIT244ME3163ME251ME144EXC37VAC30POX20ERL5 UCIyeast UCIBalanceScale balance49left288right288 UCIAnnealing 18288360840560U34 2020年3月18日 MachineLearningandDatamining 74 样本选择 失衡的训练样本导致训练困难例 正负样本1 99把全部样本分类为负样本 分类 准确率 99 完全没有应用价值的分类器 机器学习算法的假设训练样本的分布正确地刻画了正负样本在现实世界的分布特性所有样本分类错误的代价相同 失衡训练样本的学习困难 2020年3月18日 MachineLearningandDatamining 75 样本选择 有关失衡样本方面的研究AAAI 2000Workshopon LearningfromImbalancedDataSets ICML 2000Workshop Cost SensitiveLearning ICML 2003Workshop LearningfromImbalancedDataSetsII 2020年3月18日 MachineLearningandDatamining 76 样本选择 目前提出的解决途径Cost sensitivelearning给每个训练样本指定不同的错分代价但是代价究竟是多少 如何计算 单类学习 one sidelearning 只对大类的分布进行学习 小类按例外检测来做部分分类器对失衡不太敏感SVM等几何分类器失衡在一定范围 问题难度不太高 样本充足时才不敏感 极度失衡仍然效果不好 2020年3月18日 MachineLearningandDatamining 77 样本选择 目前提出的解决途径样本采样上采样 把少数样本复制多份增大数据 极大增加训练复杂度下采样 把多数样本随机丢弃一些损失信息更复杂的采样策略无论何种随机采样策略都有一定效果 但都只有一定的适应范围 2020年3月18日 MachineLearningandDatamining 78 样本选择 参考文献 Theclassimbalanceproblem Asystematicstudy IntelligentDataAnalysis 2002 Theclassimbalanceprobleminlearningclassifiersystems apreliminarystudy GECCO 2005 谁做一个报告 2020年3月18日 MachineLearningandDatamining 79 样本选择 一些经验规则过滤某些特征的组合可以明确地确定样本类属手工书写 关联规则 AssociationRule 可以把样本比例大致提高到1 10两级分类第一级 采用简单 对小类召回率接近1的分类器先用此分类器分类 分为小类的样本才进入下一级可以把样本比例大致提高到1 3 1 5第二级 采用复杂的普通分类器 2020年3月18日 MachineLearningandDatamining 80 样本选择 第一级分类器设计单个高斯分量的GMM简单结构 训练 使用易于调整召回率和准确率直接在比较一般召回率可以很高大类结构复杂 单个高斯分量难以覆盖 小类容易被单个高斯分量覆盖 所以分类结果可倾向于小类对使用GMM EM的分类器方便 对其它分类器不一定方便 2020年3月18日 MachineLearningandDatamining 81 样本选择 其它的第一级分类器尚待设计决策树 DecisionTree 贝叶斯 Na veBayes 单类GMM 更多资源