生活中的数学创新项目市公开课一等奖百校联赛特等奖课件.pptx

生活中数学创新项目汇报人孙振龙7月10日第1页生活衣食住行第2页生活衣食住行网络（信息）网络（信息）第3页理科文科第4页创新？创新？第5页第6页问题：用尽可能简单知识和方法来分析挖掘文本，进而找出有用信息关联问题：用尽可能简单知识和方法来分析挖掘文本，进而找出有用信息关联现况：传统词库，语义分析等现况：传统词库，语义分析等第7页已结婚和还未结婚青年都要实施计划生育已结婚和还未结婚青年都要实施计划生育已结婚和还未结婚青年已结婚和尚未结婚青年第8页现现在在很很多多语语言言模模型型已已经经能能比比较较漂漂亮亮地地处处理理这这一一问问题题了了。但但在在汉汉字字分分词词领领域域里里，还还有有一一个个比比分分词词歧歧义义更更令令人人头头疼疼东东西西未未登登录录词词。汉汉字字没没有有首首字字母母大大写写，专专名名号号也也被被取取消消了了，这这叫叫计计算算机机怎怎样样识识别别人人名名地地名名之之类类东东西西？更更惨惨则则是是机机构构名名、品品牌牌名名、专专业业名名词词、缩缩略略语语、网网络络新新词词等等等等，它它们们产产生生机机制制似似乎乎完完全全无无规规律律可可寻寻。最最近近十十年年来来，汉汉字字分分词词领领域域都都在在集集中中攻攻克这一难关。自动发觉新词成为了关键步骤。克这一难关。自动发觉新词成为了关键步骤。第9页挖挖掘掘新新词词传传统统方方法法是是，先先对对文文本本进进行行分分词词，然然后后猜猜测测未未能能成成功功匹匹配配剩剩下下片片段段就就是是新新词词。这这似似乎乎陷陷入入了了一一个个怪怪圈圈：分分词词准准确确性性本本身身就就依依赖赖于于词词库库完整性，假如词库中根本没有新词，我们又怎么能信任分词结果呢？完整性，假如词库中根本没有新词，我们又怎么能信任分词结果呢？不不依依赖赖于于任任何何已已经经有有词词库库，仅仅仅仅依依据据词词共共同同特特征征，将将一一段段大大规规模模语语料料中中可可能能成成词词文文本本片片段段全全部部提提取取出出来来，不不论论它它是是新新词词还还是是旧旧词词。然然后后，再再把把全部抽出来词和已经有词库进行比较，找出新词。全部抽出来词和已经有词库进行比较，找出新词。第10页怎样算一个词？怎样算一个词？第11页标准标准?文本片段出现次数是否足够多。数据源：人人网年12月前半个月部分用户状态“电影”出现了389次，“电影院”只出现了175次第12页标准标准1词内部凝固程度。数据源：人人网年12月前半个月部分用户状态2400万字数据中，“电影”一共出现了2774次，出现概率约为0.000113。“院”字则出现了4797次，出现概率约为0.0001969。假如二者之间真毫无关系，它们恰好拼在了一起概率就应该是0.0001130.0001969，约为2.22310-8次方。但实际上，“电影院”在语料中一共出现了175次，出现概率约为7.18310-6次方，是预测值300多倍。第13页标准标准1词内部凝固程度。数据源：人人网年12月前半个月部分用户状态类似地，统计可得“”字出现概率约为0.0166，因而“”和“电影”随机组合到了一起理论概率值为0.01660.000113，约为1.87510-6，这与“电影”出现真实概率很靠近真实概率约为1.610-5次方，是预测值8.5倍。计算结果表明，“电影院”更可能是一个有意义搭配，而“电影”则更像是“”和“电影”这两个成份偶然拼到一起。第14页作为一个无知识库抽词程序，我们并不知道“电影院”是“电影”加“院”得来，也并不知道“电影”是“”加上“电影”得来。错误切分方法会过高地预计该片段凝合程度。假如我们把“电影院”看作是“电”加“影院”所得，由此得到凝合程度会更高一些。所以，为了算出一个文本片段凝合程度，我们需要枚举它凝合方式这个文本片段是由哪这个文本片段是由哪两部分组合而来。两部分组合而来。第15页令p(x)为文本片段x在整个语料中出现概率，那么我们定义“电影院”凝合程度就是p(电影院)与p(电)p(影院)比值和p(电影院)与p(电影)p(院)比值中较小值，“电影”凝合程度则是p(电影)分别除以p()p(电影)和p(电)p(影)所得商较小值。第16页能够想到，凝合程度最高文本片段就是诸如“蝙蝠”、“蜘蛛”、“彷徨”、“忐忑”、“玫瑰”之类词了，这些词里每一个字几乎总是会和另一个字同时出现，从不在其它场所中使用。第17页标准标准2词外部表现。考虑“被子”和“辈子”这两个片段。我们能够说“买被子”、“盖被子”、“进被子”、“好被子”、“这被子”等等，在“被子”前面加各种字；但“辈子”使用方法却非常固定，除了“一辈子”、“这辈子”、“上辈子”、“下辈子”，基本上“辈子”前面不能加别字了。“辈子”这个文本片段左边能够出现字太有限，以至于直觉上我们可能会认为，“辈子”并不单独成词，真正成词其实是“一辈子”、“这辈子”之类整体。第18页标准标准2词外部表现。文本片段自由利用程度也是判断它是否成词主要标准。假如一个文本片段能够算作一个词话，它应该能够灵活地出现在各种不一样环境中，含有非常丰富左邻字集合和右邻字集合。第19页Link:信息熵信息熵“信息熵”是一个非常神奇概念，它能够反应知道一个事件结果后平均会给你带来多大信息量。假如某个结果发生概率为p，当你知道它确实发生了，你得到信息量就被定义为-log(p)。p越小，你得到信息量就越大。一颗骰子六个面分别是1、1、1、2、2、3，那么你知道了投掷结果是1时可能并不会那么吃惊，它给你带来信息量是-log(1/2)，约为0.693。知道投掷结果是2，给你带来信息量则是-log(1/3)1.0986。知道投掷结果是3，给你带来信息量则有-log(1/6)1.79。不过，你只有1/2机会得到0.693信息量，只有1/3机会得到1.0986信息量，只有1/6机会得到1.79信息量，因而平均情况下你会得到0.693/2+1.0986/3+1.79/61.0114信息量。这个1.0114就是那颗骰子信息熵。第20页Link:信息熵信息熵“信息熵”是一个非常神奇概念，它能够反应知道一个事件结果后平均会给你带来多大信息量。假如某个结果发生概率为p，当你知道它确实发生了，你得到信息量就被定义为-log(p)。p越小，你得到信息量就越大。现在，假如某颗骰子有100个面，其中99个面都是1，只有一个面上写2。知道骰子抛掷结果是2会给你带来一个巨大无比信息量，它等于-log(1/100)，约为4.605；但你只有百分之一概率获取到这么大信息量，其它情况下你只能得到-log(99/100)0.01005信息量。平均情况下，你只能取得0.056信息量，这就是这颗骰子信息熵。第21页Link:信息熵信息熵“信息熵”是一个非常神奇概念，它能够反应知道一个事件结果后平均会给你带来多大信息量。假如某个结果发生概率为p，当你知道它确实发生了，你得到信息量就被定义为-log(p)。p越小，你得到信息量就越大。一个最极端情况：假如一颗骰子六个面都是1，投掷它不会给你带来任何信息，它信息熵为-log(1)=0。什么时候信息熵会更大呢？第22页信息熵直观地反应了信息熵直观地反应了一个事件结果有多么随机一个事件结果有多么随机第23页标准标准2词外部表现。我们用信息熵来衡量一个文本片段左邻字集合和右邻字集合有多随机。第24页吃葡萄不吐葡萄皮不吃葡萄倒吐葡萄皮吃葡萄不吐葡萄皮不吃葡萄倒吐葡萄皮“葡萄”：4次左邻字：吃,吐,吃,吐右邻字：不,皮,倒,皮左邻字信息熵=-(1/2)log(1/2)-(1/2)log(1/2)0.693右邻字信息熵=-(1/2)log(1/2)-(1/4)log(1/4)-(1/4)log(1/4)1.04第25页“被子”：956次右邻字集合信息熵3.87404“辈子”：2330次右邻字集合信息熵4.11644第26页“被子”左邻字用例非常丰富：用得最多是“晒被子”，它一共出现了162次；其次是“被子”，出现了85次；接下来分别是“条被子”、“在被子”、“床被子”，分别出现了69次、64次和52次；当然，还有“叠被子”、“盖被子”、“加被子”、“新被子”、“掀被子”、“收被子”、“薄被子”、“踢被子”、“抢被子”等100各种不一样使用方法组成长尾全部左邻字信息熵为3.67453第27页“辈子”左邻字就很可怜了，2330个“辈子”中有1276个是“一辈子”，有596个“这辈子”，有235个“下辈子”，有149个“上辈子”，有32个“半辈子”，有10个“八辈子”，有7个“几辈子”，有6个“哪辈子”，以及“n辈子”、“两辈子”等13种更罕见使用方法。全部左邻字信息熵仅为1.25963。“下子”则是更经典例子，310个“下子”用例中有294个出自“一下子”，5个出自“两下子”，5个出自“这下子”，其余都是只出现过一次罕见使用方法。实际上，“下子”左邻字信息熵仅为0.294421，我们不应该把它看作一个能灵活利用词。第28页一些文本片段左邻字没啥问题，右邻字用例却非常贫乏，比如“交响”、“后遗”、“鹅卵”等，把它们看作单独词似乎也不太适当。我们不妨就把一个文本片段自由利用程度定义为它左邻字信息熵和右邻我们不妨就把一个文本片段自由利用程度定义为它左邻字信息熵和右邻字信息熵中较小值。字信息熵中较小值。第29页文本片段凝固程度和自由程度，两种判断标准缺一不可。只看凝固程度话，程序会找出“巧克”、“俄罗”、“颜六色”、“柴可夫”等实际上是“半个词”片段；只看自由程度话，程序则会把“吃了一顿”、“看了一遍”、“睡了一晚”、“去了一趟”中“了一”提取出来，因为它左右邻字都太丰富了。第30页怎么用？怎么用？第31页找出候选词找出候选词我们把文本中出现过全部长度不超出d子串都看成潜在词（即候选词，其中d为自己设定候选词长度上限），再为出现频数、凝固程度和自由程度各设定一个阈值，然后只需要提取出全部满足阈值要求候选词即可。为了提升效率，我们能够把语料全文视作一整个字符串，并对该字符串全部后缀按字典序排序。第32页四是四十是十十四是十四四十是四十四是四十是十十四是十四四十是四十十十十四是十四四十是四十十是十十四是十四四十是四十十是四十十四是十四四十是四十十四四十是四十是十十四是十四四十是四十是十四四十是四十是四十是四十是十十四是十四四十是四十四十四十是十十四是十四四十是四十四十是四十四是十四四十是四十四是四十是十十四是十四四十是四十四四十是四十第33页优势优势相同候选词都集中在了一起，从头到尾扫描一遍便能算出各个候选词频数和右邻字信息熵。将整个语料逆序后重新排列全部后缀，再扫描一遍后便能统计出每个候选词左邻字信息熵。另外，有了频数信息后，凝固程度也都很好计算了。这么，我们便得到了一个无需任何知识库抽词算法，输入一段充分长文本，这个算法能以大致O(nlogn)效率提取出可能词来。第34页结果怎样？结果怎样？第35页西游记西游记上册抽词结果：上册抽词结果：行者、师父、三藏、八戒、大圣、菩萨、悟空、怎么、和尚、唐僧、老孙、溃骸、什么、沙僧、太宗、徒弟、袈裟、妖精、玉帝、今日、弟兄、公主、玄奘、陛下、宝贝、性命、晓得、门外、妖魔、光蕊、观音、花果山、土地、木叉、东土、改变、变做、伯钦、判官、多少、真君、齐天大圣、蟠桃、丞相、魏征、扯住、溃骸澳、抬头、揭谛、言语、猪八戒、兵器、吩咐、安排、叩头、清风、哪吒、左右、美猴王、钉钯、孩儿、女婿、金箍棒、二郎、东西、许多、奈何、人参果、收拾、近前、太保、明月、南海、水帘洞、门首、弼马温、李天王词频数从高到低排序第36页资本论资本论全文抽词结果：全文抽词结果：商品、形式、货币、我们、过程、自己、机器、社会、部分、表现、没有、流通、需要、增加、已经、交换、关系、先令、积累、必须、英国、条件、发展、麻布、儿童、进行、提升、消费、降低、任何、伎俩、职能、土地、特殊、实际、完全、平均、直接、伴随、简单、规律、市场、增加、上衣、决定、什么、制度、最终、支付、许多、即使、棉纱、形态、棉花、法律、绝对、提供、扩大、独立、世纪、性质、假定、天天、包含、物质、家庭、规模、考查、剥削、经济学、甚至、延长、财富、纺纱、购置、开始、代替、便士、怎样、降低、能够、原料、等价物词频数从高到低排序第37页时间简史时间简史全文抽词结果：全文抽词结果：黑洞、必须、非常、任何、膨胀、科学、预言、太阳、观察、定律、运动、事件、奇点、坍缩、问题、模型、方向、区域、知道、开始、辐射、部分、牛顿、产生、夸克、无限、轨道、解释、边界、甚至、自己、类似、描述、最终、旋转、爱因斯坦、绕着、什么、效应、表明、温度、研究、收缩、吸引、按照、完全、增加、开端、基本、计算、结构、上帝、进行、已经、发展、几乎、依然、足够、影响、初始、科学家、事件视界、第二、改变、历史、世界、包含、准确、证实、造成、需要、应该、最少、刚好、提供、经过、似乎、继续、试验、复杂、伽利略词频数从高到低排序第38页人人网用户状态中最常出现词是：人人网用户状态中最常出现词是：哈哈、什么、今天、怎么、现在、能够、知道、喜欢、终于、这么、以为、因为、假如、感觉、开始、回家、考试、老师、幸福、朋友、时间、发觉、东西、高兴、为何、睡觉、生活、已经、希望、最终、各种、状态、世界、突然、手机、其实、那些、同学、孩子、尼玛、木有、然后、以后、学校、所以、青年、晚安、原来、电话、加油、果然、学习、中国、最近、应该、需要、竟然、事情、永远、尤其、北京、他妈、伤不起、必须、呵呵、月亮、毕业、问题、谢谢、英语、生日高兴、工作、即使、讨厌、给力、轻易、上课、作业、今晚、继续、努力、有木有、记得词频数从高到低排序第39页实际上，从人人网状态数据中一共抽出了大约1200个词，里面大多数词也确实都是标准当代汉语词汇。不过别忘了，我们目标是新词抽取。将全部抽出来词与已经有词库作对比，于是得到了人人网特有词汇（一样按频数从高到低排序）：尼玛、伤不起、给力、有木有、挂科、坑爹、神马、淡定、老爸、卧槽、牛逼、肿么、苦逼、无语、微博、六级、高数、选课、悲催、基友、蛋疼、很久、人人网、情何以堪、童鞋、哇咔咔、脑残、吐槽、猥琐、奶茶、我勒个去、刷屏、妹纸、胃疼、飘过、考研、弱爆了、太准了、搞基、忽悠、羡慕嫉妒恨、手贱、柯南、狗血、秒杀、装逼、真特么、碎觉、奥特曼、内牛满面、斗地主、腾讯、灰常、偶遇、拉拉、屌丝、九把刀、高富帅、阿内尔卡、魔兽世界、线代、三国杀、林俊杰、速速、臭美、花痴第40页能再给力点么？能再给力点么？老师老师第41页有意思有意思“玩玩”法法拿每一天状态里词去和前一天状态作对比，从而提取出这一天里特有词呢。这么一来，我们就能从人人网用户状态中提取出每日热点了！第42页选了12个比较含有代表性词，并列出了它们在年12月13日用户状态中出现频数（左列数），以及年12月14日用户状态中出现频数（右列数）：下雪3392那些年139146李宇春14看见145695魔兽2320高数8283生日高兴235210今天14161562北半球218脖子2369悲伤6133电磁炉03第43页“下雪”一词在12月13日只出现了33次，在12月14日却出现了92次，后者是前者2.8倍，这不大可能是巧合，初步判断一定是12月14日真有什么地方下雪了。“那些年”在12月14日频数确实比12月13日更多，但相差并不大，我们没有理由认为它是当日一个热词。问题：问题：我们怎样去量化一个词“当日热度”？第一想法当然是简单地看一看每个词当日频数和昨日频数之间倍数关系，不过细想一下你就发觉问题了：它不能处理样本过少带来偶然性。12月14日“李宇春”一词出现频数是12月13日4倍，这超出了“下雪”一词2.8倍，但我们却更愿意相信“李宇春”现象只是一个偶然。更麻烦则是“电磁炉”一行，12月14日频数是12月13日无穷多倍，但显然我们也不能所以就认为“电磁炉”是12月14日最热词。第44页忽略全部样本过少词？这似乎也不太好，样本少词也有可能真是热词。比如“北半球”一词，即使它在两天里频数都极少，但这个9倍关系确实不容忽略。实际上，人眼很轻易看出哪些词真是12月14日热词：除了“下雪”以外，“看见”、“北半球”和“脖子”也应该是热词。你或许坚信后三个词异峰突起背后一定有什么原因（而且迫切地想知道这个原因终究是什么），但却会果断地把“李宇春”和“电磁炉”这两个“异常”归结为偶然原因。年年 12 月月 14 日发生了极其壮观双子座流星雨，此乃北半球三大流日发生了极其壮观双子座流星雨，此乃北半球三大流星雨之一。白天网友们不停转发新闻，因而星雨之一。白天网友们不停转发新闻，因而“北半球北半球”一词热了一词热了起来；晚上网友们不停发消息说起来；晚上网友们不停发消息说“看见了看见了”、“又看见了又看见了”，“看见看见”一词出现频数猛增；最终呢，仰视天空一晚上，脖子终于一词出现频数猛增；最终呢，仰视天空一晚上，脖子终于出毛病了，于是回家路上一个劲儿地发出毛病了，于是回家路上一个劲儿地发“脖子难受脖子难受”。第45页能再给力点么？能再给力点么？老师老师第46页人人网状态大多数公布者都填写了性别和年纪个人信息，我们为何不把状态重新分成男性和女性两组，或者80后和90后两组，挖掘出不一样属性人都爱说什么？更有意思更有意思“玩玩”法法第47页男性爱说词是：男性爱说词是：弟兄、篮球、男篮、米兰、曼联、足球、蛋疼、皇马、比赛、国足、超级杯、球迷、中国、老婆、政府、航母、踢球、赛季、股市、砸蛋、牛逼、铁道部、媳妇、国际、美国、连败、魔兽、斯内德、红十字、经济、腐败、程序、郭美美、英雄、民主、鸟巢、米兰德比、官员、内涵、历史、训练、评级、金融、体育、记者、事故、程序员、媒体、投资、事件、社会、项目、伊布、主义、决赛、操蛋、纳尼、领导、喝酒、民族、新闻、言论、友好、农民、体制、城管第48页女性爱说词是：女性爱说词是：一起玩、蛋糕、加挚友、老公、呜呜、姐姐、嘻嘻、老虎、讨厌、妈妈、呜呜呜、啦啦啦、廉价、减肥、男朋友、老娘、逛街、无限、帅哥、礼品、相互、奶茶、委屈、各种、高跟鞋、指甲、城市猎人、闺蜜、巧克力、第二、父亲、宠物、箱子、吼吼、大黄蜂、狮子、胃疼、玫瑰、包包、裙子、游戏、遇见、嘿嘿、灰常、眼睛、各位、妈咪、化装、玫瑰花、蓝精灵、幸福、陪我玩、任务、怨念、舍不得、害怕、狗狗、眼泪、温暖、面膜、收藏、李民浩、神经、土豆、零食、痘痘、戒指、巨蟹、晒黑词频数从高到低排序第49页90 后用户爱用词：后用户爱用词：加挚友、作业、各种、乖乖、蛋糕、来访、卧槽、通知书、麻将、聚会、补课、欢乐、刷屏、录用、无限、相互、速度、一起玩、啦啦啦、晚安、求陪同、基友、美女、矮油、巨蟹、五月天、第二、唱歌、老虎、扣扣、啧啧、帅哥、哈哈哈、尼玛、廉价、苦逼、斯内普、写作业、劳资、孩纸、哎哟、炎亚纶、箱子、无聊、求来访、查分、上课、果断、处女、首映、屏蔽、混蛋、暑假、吓死、新东方、组队、下学期、陪我玩、打雷、妹纸、水瓶、射手、搞基、吐槽、同学聚会、出去玩、呜呜、白羊、表明、做作业、署名、姐姐、停机、伏地魔、对象、哈哈、主页、情侣、无压力、共同、摩羯、碎觉、肿么办词频数从高到低排序第50页80 后用户爱用词：后用户爱用词：加班、培训、周末、工作、企业、各位、值班、砸蛋、上班、任务、公务员、工资、领导、包包、办公室、校内、郭美美、时尚、企业、股市、新号码、英国、常联络、试验室、论文、忙碌、项目、部门、祈福、邀请、招聘、顺利、朋友、红十字、男朋友、媒体、产品、标准、号码、存钱、牛仔裤、曼联、政府、简单、立秋、事故、伯明翰、博士、辞职、健康、销售、深圳、奶茶、迁居、试验、投资、节日高兴、坚持、规则、考验、生活、体制、客户、发工资、忽悠、提供、教育、处理、惠存、沟通、团购、缺乏、腐败、启程、红十字会、结婚、管理、环境、暴跌、服务、变形金刚、祝福、银行词频数从高到低排序第51页能再给力点么？能再给力点么？老师老师第52页不少状态还带有地理位置信息，因而我们能够站在空间维度对信息进行观察。这个地方人都爱说些什么？爱说这个词人都分布在哪里？借助这些包含地理位置签到信息，我们也能挖掘出很多有意思结果来。更更有意思更更有意思“玩玩”法法比如，对北京用户签到信息进行抽词，然后对于每一个抽出来词，筛选出全部包含该词签到信息并按地理坐标位置聚类，这么我们便能找出那些地理分布最集中词。结果非常有趣：“考试”一词集中分布在海淀众高校区，“天津”一词集中出现在北京南站，“逛街”一词则全都在西单附近扎堆。北京首都国际机场也是一个非常尤其地点，“北京”、“登机”、“终于”、“再见”等词在这里出现密度极高。第53页从全国范围来看，不一样区域人也有显著用词区分。更更有意思更更有意思“玩玩”法法比如，在节假日时候，“滑雪”一词主要在北方出现，“登山”一词则主要在南方出现。地方特色也是造成词语分布差异一大原因，比如“三里屯”一词几乎只在北京出现，“热干面”一词集中出现在武汉地域，“地铁”一词显著只有个别城市有所包括。方言也会造成用词分布差异，比如“咋这么”主要分布在北方地域，“搞不懂”主要分布在南方城市，“伐”则非常集中地出现在上海地域。第54页还能再给力点么？还能再给力点么？老师老师第55页第56页让我们讨论点其它东西吧让我们讨论点其它东西吧第57页谢谢谢谢第58页