机器学习与数据挖掘 样本准备（2）

Machine Learning and Datamining 样本准备 对象分割 对象在文档中可能只占很小比例 用整个文档提取的特征含有大量噪声 特征与特征提取 使用什么样的特征？如何计算？如何进行预处理？ …… 样本选择 正负样本数可能严重失衡（1:10，1:100） 样本可能包含噪声 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征 何为特征？ In pattern recognition, features are the individual measurable heuristic properties of the phenomena being observed. In computer vision and image processing the concept of feature is used to denote a piece of information which is relevant for solving the computational task related to a certain application. 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征 何为特征？ 特征：实体（或事物、概念……）区别于其它实体（事物、概念……）的独特的属性 特征 = 特 + 征 独特的 特殊的 性质 有比较，才有独特、特殊 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征 特征的属性 独特性 目标实体和非目标实体有不同的取值范围 确定性特征，概率性特征 可计算性 以可接受的代价从目标实体采集数据并计算出来 特征的成本 特征的质量（噪声） 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征 特征组的属性 完备性 可以完全区分目标实体和非目标实体 必要性 对区分目标实体和非目标实体是否必要 独立性 特征之间是否相关 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征 特征的种类（应用意义上） 多媒体特征（视觉、听觉特征） 颜色、纹理、形状…… 频率、节奏…… 文字/关键字特征 字频、词频…… 元数据特征 目录名、链接、链接文字、日期…… 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 何为特征提取？ 从原始数据计算出特征的数值（或模型） 特征提取须考虑的问题 可计算性 特征提取时，数据采集往往已经完成，特征提取不具备采用不同数据采集手段的灵活性 成本 计算复杂度，吞吐率，延迟，人力开销…… 噪声 很多多媒体特征提取准确率低 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 像素特征 直接用像素的颜色值表示特征 实现简单 信息质量差 仅包含单个像素的信息 同时包含需要的信息和不需要的噪声 难以表示全局信息 后续分类和处理困难 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 颜色特征 颜色是人眼非常敏感的特征 如何提取和表示颜色特征？ 平均颜色 把所有像素的颜色值当作矢量，计算所有像素的颜色矢量的算术平均 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 颜色特征 颜色矩 如果把像素看成随机变量，则其分布特性可以由矩来描述 一阶矩(均值)： 二阶中心矩(标准差): 三阶中心矩: 维数低，易于计算 信息量少，对噪声敏感 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 颜色特征 颜色直方图 直方图：概率密度函数 颜色：三维如何统计直方图？ 方法1：三维颜色直方图 直方图的每个槽对应一组（R,G,B）矢量值 RGB均0~255直方图有256*256*256=16M个槽 图像像素数：704*576=405K, 1920*1080=2M 统计直方图需要使用较粗的量化 一般量化成16级 16*16*16=4096个槽 维数仍然很高 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 颜色特征 颜色直方图 方法2：三个一维直方图 对R、G、B三个颜色分别统计一个直方图 不进一步量化：256+256+256=768维 每种颜色量化成16级：16+16+16=48维 优点：维数大大降低 缺点：颜色之间的相关信息丢失 在较独立的颜色空间统计（如：YUV，HSI） 亮度统计一维直方图，色度统计二维直方图 直方图的维数仍然较高 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 颜色特征 聚类颜色直方图 普通颜色直方图不管图像本身的颜色分布，整个颜色空间的所有颜色都是直方图的槽 维数高 必须覆盖整个颜色空间 精度差 对颜色空间的机械分割 为了在合理的维数内实现，颜色空间的划分很粗 利用图像本身的像素进行聚类，用聚类中心作为直方图的槽 不同图像的直方图各维没有统一的物理含义 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 纹理特征 纹理：临近像素的变化趋势和模式 一定尺度内的一种分布模式 可以是固定的模式：如砖墙 可以是概率的模式：如草地 与像素的绝对颜色/亮度关系较小 与颜色/亮度差异关系大 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 纹理特征 灰度共生矩阵 两个有固定空间关系的像素的联合概率密度函数 0 1 … 255 1 … 255 空间关系 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 纹理特征 灰度共生矩阵 超高的维数 空间关系有很多个 每个空间关系有一个二维直方图 在这些二维直方图上作“二次统计”以降低维数 角二阶矩（能量）、对比度（惯性矩）、相关、熵、逆差矩等 与人类视觉对纹理的心理感知不同 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 纹理特征 Tamura 纹理特征 依据心理视觉特性定义的纹理特征 计算准确率较差，信息量较少 稀疏度 对比度 方向性 线状性 规则性 粗糙度 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 纹理特征 频率域的纹理特征 纹理是“变化趋势和模式” 在某个频率上有突出的特征 利用频率变换表示纹理特征 小波纹理特征 对图像作小波变换 计算小波的一阶矩和二阶矩作为纹理特征 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 纹理特征 频率域的纹理特征 局部傅立叶变换纹理特征 在局部邻域(3x3, 4x4, 5x5…窗口)内作傅立叶变换，用傅立叶系数作为纹理特征 Gabor变换 频率空间中的局部区域特征 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 纹理特征 频率域的纹理特征 Gabor变换 频率空间中取某个窗口内的系数来提取特征 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 形状特征 面积(A)、周长(P)、质心(O) 长度(L)、宽度(W) 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 形状特征 矩形度：面积和最小外接矩形面积的比值 长宽比：L/W 圆度： 欧拉数 拓扑特征 难以精确提取 信息量小 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 形状特征 轮廓的高维特征 把轮廓坐标转换成一维复数序列一维复函数 可以进行傅立叶变换，提取频率特征 傅立叶描述子 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 文字特征 文字的基本单位 字/字母，词 西方文字：字母并无显著语义 中文：“字”接近于词 字频 早期中文处理技术及少数简单的中文处理应用 词频及词频衍生特征 大多数文字处理应用 如何获得“词”? 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 分词（Tokenlize/Lexicon） 输入：字符串 例：“Friends, Romans, countrymen” 例：“华东师范大学” 输出：词（token） Friends 华东 Romans 师范 countrymen 大学 词经过后处理可以作为提取词频的依据 就这么简单？ 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 问题 Finland’s capital  Finland? Finlands? Finland’s ? Hewlett-Packard  1个词？2个？ State-of-the-art？ the hold-him-back-and-drag-him-away-maneuver? L'ensemble 1个词？2个？ L ? L’ ? Le ? 不同的系统使用不同的方法 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 各种数字形式 3/12/91 Mar. 12, 1991 55 B.C. B-52 My PGP key is 324a3df234cb23e 100.2.86.144 +86-21-62235089 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 基本算法 正则式匹配 例：普通的英文日期 [0-9]{1,2}“/” [0-9]{1,2}“/” [0-9]{2,4} 例：普通的英文单词 [a-zA-Z]+ 一个西欧语言的分词可能需要数十条正则式 使用flex或re2c可以方便地开发 英语的分词flex程序例：请从主页下载 练习：用re2c写一个结构更好的英语分词程序 不用提交 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 问题 San Francisco  1个词？2个？ San Francisco-Las Vegas 德语复合名词不加空格 Lebensversicherungsgesellschaftsangestellter ‘life insurance company employee’ 中文和日文没有空格 “华东师范大学软件学院” 分词是一个大问题！ 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 基于词典的分词 意见 分歧 华盛顿 …… 词典 华盛顿有意见分歧 华盛顿/有/意见/分歧 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 基于词典的分词 “感冒清胶囊” 感冒/清/胶囊 感冒清/胶囊 感冒 感冒清 …… 最大匹配原则： 匹配词典中最长的词 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 基于词典的分词 “有意见分歧” 有意/见/分歧 有/意见/分歧 “中国人民” 中国人/民 中国/人民 反向匹配 正向匹配 对中文：反向匹配准确率较高 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 基于词典的分词 “实在感觉英雄无用武之地方能拍案而起” 实在/感觉/英雄无用武之地/方/能/拍案而起 实在/感觉/英雄/无用/武/之/地方/能/拍案而起 双向匹配： 正反两个方向分别分词，选择词数较小的结果 优点：准确率较高 缺点：慢 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 基于词典的分词 其它语言中的应用 日语、朝鲜语：相同算法即可 英语：识别空格分隔的词（如：Las Vegas） 把空格分隔的每部分当作“字”即可 德语：识别连写的复合名词 把字母当作“字”即可 练习：实现基于词典的英语常用复词检测 不需要提交 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 基于词典的分词 如何快速查找词典？ 为词典建立索引结构 最简单：二分查找 结构：排序的数组 复杂度：O(log n) 优点：最简单的实现 缺点：键插入、删除困难，对不定长键效率不高 如何改进？ 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 基于词典的分词 二叉树(binary-tree) 结构：二叉树（废话……） 复杂度：O(log n) 优点：键插入、删除较容易，对不定长键效率高 缺点：大量插入删除键后可能退化 按某个顺序插入，则二叉树可能退化成链表 如何解决？ 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 基于词典的分词 B树(B: balance) 结构：多叉树 每个节点允许[a, b]个子节点 复杂度：O(log n) 与二叉树一样！ 优点：可以一定程度上克服二叉树退化的缺点 缺点：复杂度还是较高 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 桶(bucket) 基于词典的分词 Hash表 Hash函数：把键转换成整数 相同的间转换成相同的数 不同的键尽可能转换成不同的数 把键放在根据键转换出的整数为标号的桶中 多个键映射到一个桶？ 拉链法：用链表组织桶的存储结构 其它办法：…… 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 基于词典的分词 Hash表 如何设计Hash函数？ 不知道！ 常用：移位异或：H(X) = ((x1^ x2)<<1)^x3…… 多少个桶？ 与键的数量大致相当 复杂度：O(1) 与键的个数无关！ 前提：优秀的Hash函数，桶的个数足够多 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 基于词典的分词 Hash表 缺点 添加大量键后性能可能下降（桶数量不够了） 冲突大的桶检索性能低 如何解决？ 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 基于词典的分词 Trie结构(Trie: Retrieval) 啊 阿 … 北 啄 啊 阿 … 京 啄 啊 阿 … 木 啄 1 16 … 啊 阿 … 鸟 啄 2 7 … 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 基于词典的分词 Trie结构 复杂度 以键为基准：O(1) 以字符为基准：O(m) 与Hash表比谁快？不知道！ 优点 性能与插入删除顺序无关 性能与键值多少基本无关 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 基于词典的分词 Trie结构 缺点 结构较大，占用内存大 插入删除算法比较复杂 哪种结构最好？ 应根据实际应用而定 小词典、简单文字处理：hash表，二分查找 大词典、大规模索引：Trie结构 动态词典、经常修改的索引：B树，二叉树 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 基于词典的分词 “华东师范大学” 1词？3词？ 我的意见：4词！（用Trie结构很容易实现） “中国人民万岁” 中国人/民/万岁 中国/人民/万岁 新词? 首尔 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 其它分词技术 基于概率 可以有很复杂的模型 基于自然语言理解 更复杂 慢！ 复合分词 结合多种分词技术 先用匹配算法，发现歧义再使用复杂技术 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 分词 更简单的方法：不分词 N-gram “中国人民” 中/国/人/民 中国/国人/人民 中国人/国人民 中国人民 优点：避免了分词的难题 缺点：处理很复杂，计算量大 可以用于小规模的系统 全部用于计算 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 最常用的词是无意义的词 a an and are as at be by for from…… 可以 没有 非常 很 特别…… 占总词数的40-50%！ 消耗40-50%的处理时间 在特征中占据40-50%的信息 噪声！ 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 禁用词表(stop list) 一个最常用但是无意义的词的词典 不把这个词典中的词加入词典 问题 Phone card to/from Germany As we may think To be or not to be 这个可以有 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 禁用词表(stop list) 作为文本特征 用较大的禁用词表，以消除噪声影响 早期的检索系统 用较大的禁用词表（200-300词） 硬件能力较低 现代检索系统 用较小的禁用词表（20词以内）或不用 硬件较强 使用针对高频词优化的检索算法 例：检索关键字按词频排序 大型搜索引擎(Google) 使用禁用词表，规模未知 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 一个词可能有不同的形式 日语有平假名、片假名、汉字、罗马字 Accents (变音符？) résumé resume Tuebingen Tübingen フォーチュン500社は情報不足のため時間あた$500K(約6,000万円) 片假名 平假名 汉字 罗马字 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 变形和同义词 U.S.A., U.S., USA, United States Windows, windows was, were, is, be 中国， 中华人民共和国 上海， 沪， 申 一月十七日 1月17日 １月１７日 正月 腊月 廿 卅 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 归一化 方法1：等价类 把所有等价词都归一化到一个等价类 索引/特征中只保留等价类 对检索应用，查询关键字也要先转换成等价类 简单，高效 方法2：查询扩展（检索系统） 把查询关键字扩展成等价类中所有词的或 索引中保留所有词 灵活 windows  Windows, windows, window window  windows, window 现实系统：两个方法同时使用 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 构造等价类词典 Accents (变音符？) 基于字母的单向映射 é  e ü  ue 为何不反向映射？ 用户一般输入无accent的词查询 缩写归一化 U.S.A.  USA 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 构造等价类词典 小写化(case-folding) 把所有字母转换成小写 US  us ? C.A.T.  CAT  cat ? 把句子的第一个字母小写化，把标题中全部大写的词小写化，其它词保留原大小写 用户会输入全部小写的查询！ 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 构造等价类词典 词干(stemming) 使用简单规则把词尾变形部分切除 Porter算法规则示例： sses  ss ies  i ational  ate tional  tion (m>1) EMENT → replacement → replac cement → cement 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 构造等价类词典 词干(stemming) 好例子 colors  color 坏例子 apples  appl 非常坏的例子 operate operating operates operation operative operatives operational  oper 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 构造等价类词典 词形分类？(lemmatization, lemma) 进行自然语言处理，分析词的变形 需要较高级的技术，处理复杂 I saw her.  I see her. I buy a saw.  I buy a saw. 性能提升（与词干比较） 英语检索：很少 等价类才是检索的关键 非英语检索：有一些 特征提取/语义处理：非常有用 如果结果需要显示给人看的话 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 构造等价类词典 同义词 car automobile 上海 沪 申 没有好的办法 手工或半手工构造 一般使用查询扩展实现 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 拼写矫正(spell correction) object  pbject/ibject OCR:  Dbject 方法1：编辑距离(edit distance) 把一个词通过基本编辑操作转变成另一个词需要的操作个数 常用操作：插入，删除，替换 例：cat  dog 3 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 拼写矫正 编辑距离 详情见：http://www.merriampark.com/ld.htm G U M B O A L = C = 0 0 1 2 3 4 5 123456 1 2 3 4 1 2 3 4 2 1 2 3 3 2 1 2 4 3 2 1 5 4 3 2 Cu = du+1 = 2 12345 Cl = dl+1 = 2 Cul = dul+ c = 0 插入L 替换U为A 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 拼写矫正 方法2：加权编辑距离 o  i/p/l/0/D 键盘： o  i/p/l/0 OCR： o  0/D 计算方法类似 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 近音替换 chebyshev  tchebycheff 使用拼音文字的用户更常犯拼写错误 真心诚意  正心诚意 后一个：Sogou拼音输入法词库第一条 好像现在很多人用？ 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 近音替换 Soundex 保留首字母 后续字母转换成数字 0: A, E, I, O, U, H, W, Y 1: B, F, P, V 2: C, G, J, K, Q, S, X, Z 3: D,T 4: L 5: M, N 6: R 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 Herman 近音替换 Soundex 保留首字母 后续字母转换成数字 归并相邻的连续数字 删除0 末尾补0 返回前4个字符 H 06505 H655 000… 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 语言问题 近音替换 同音词典 中城药/重城药  中成药 落花世界有风军  落花时节又逢君 查询词  拼音  查询同音词典  推荐 百度 特征提取中可以使用吗？ 如何使用？ 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 元数据特征 何为元数据（metadata）？ Wikipedia: Metadata is "data about other data“ 元数据是描述目标文档/实体/对象的数据 标题、关键字、分类…… 文件名、链接、日期、大小…… 位置、速度、亮度…… 镜头、焦距、光圈、快门速度…… 元数据有可能直接或间接描述文档/实体/对象内容 元数据无须处理即可较好地作为特征使用 元数据也可能与文档/实体/对象内容毫无关系 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 元数据特征 元数据特征应用案例1：实时交通信息 目标：实时自动感知整个城市各道路交通状况 直接方案：架设大量摄像头，通过计算机视觉计算道路上车辆数量和速度 成本较高，算法难度极大，天气不好几乎无法使用 间接方案：在汽车上安装GPS和通信装置，通过GPS报告的位置速度信息反演计算 算法难度不大，实现精度很高，基本不受天气影响 成本极高，大多数汽车不可控 所有出租车已经安装使用出租车已经安装的装置 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 元数据特征 元数据特征应用案例2：照片分类 不同类型的照片往往使用非常不同的拍摄参数 镜头 焦距 光圈 快门速度 闪光灯 人像 定焦头 ~50-150mm >2.8 ~30-100/s 关 瀑布 70-200/4 70mm 29 1s 关 夜间留影 18~55 20mm 4 1s 防红眼 更详细信息参考课程主页给出的论文 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 元数据特征 元数据特征的失败案例 元数据特征也不是万能的 2018年12月4日 Machine Learning and Datamining

Machine Learning and Datamining 特征提取 多模特征(multi-modal feature) 单一特征难以保留足够信息 仅能保留特征所针对的信息 结合多个特征，以保留更多信息 颜色、纹理、形状 维数显著增加 特征降维 特征选取(Feature Selection) 2018年12月4日 Machine Learning and Datamining