《课件生活中的数学创新项目研究报告》由会员分享，可在线阅读，更多相关《课件生活中的数学创新项目研究报告（58页珍藏版）》请在金锄头文库上搜索。
1、生活中的数学创新项目,报告人孙振龙2013年7月10日,网络（信息）,互联网的文本数据挖掘,问题：用尽可能简单的知识和方法来分析挖掘文本，进而找出有用的信息关联,现况：传统的词库，语义分析等,已结婚的和尚未结婚的青年都要实行计划生育,已结婚的和尚未结婚的青年,已结婚的和尚未结婚的青年,现在很多语言模型已经能比较漂亮地解决这一问题了。但在中文分词领域里，还有一个比分词歧义更令人头疼的东西未登录词。中文没有首字母大写，专名号也被取消了，这叫计算机如何辨认人名地名之类的东西？更惨的则是机构名、品牌名、专业名词、缩略语、网络新词等等，它们的产生机制似乎完全无规律可寻。最近十年来，中文分词领域都在集中攻
2、克这一难关。自动发现新词成为了关键的环节。,挖掘新词的传统方法是，先对文本进行分词，然后猜测未能成功匹配的剩余片段就是新词。这似乎陷入了一个怪圈：分词的准确性本身就依赖于词库的完整性，如果词库中根本没有新词，我们又怎么能信任分词结果呢？,不依赖于任何已有的词库，仅仅根据词的共同特征，将一段大规模语料中可能成词的文本片段全部提取出来，不管它是新词还是旧词。然后，再把所有抽出来的词和已有词库进行比较，找出新词。,如何算一个词？,标准?文本片段出现的次数是否足够多。,数据源：人人网2011年12月前半个月部分用户的状态,“的电影”出现了389次，“电影院”只出现了175次,标准1词的内部凝固程度。,
3、数据源：人人网2011年12月前半个月部分用户的状态,2400万字的数据中，“电影”一共出现了2774次，出现的概率约为0.000113。“院”字则出现了4797次，出现的概率约为0.0001969。如果两者之间真的毫无关系，它们恰好拼在了一起的概率就应该是0.0001130.0001969，约为2.22310-8次方。但事实上，“电影院”在语料中一共出现了175次，出现概率约为7.18310-6次方，是预测值的300多倍。,标准1词的内部凝固程度。,数据源：人人网2011年12月前半个月部分用户的状态,类似地，统计可得“的”字的出现概率约为0.0166，因而“的”和“电影”随机组合到了一起的
4、理论概率值为0.01660.000113，约为1.87510-6，这与“的电影”出现的真实概率很接近真实概率约为1.610-5次方，是预测值的8.5倍。计算结果表明，“电影院”更可能是一个有意义的搭配，而“的电影”则更像是“的”和“电影”这两个成分偶然拼到一起的。,作为一个无知识库的抽词程序，我们并不知道“电影院”是“电影”加“院”得来的，也并不知道“的电影”是“的”加上“电影”得来的。错误的切分方法会过高地估计该片段的凝合程度。如果我们把“电影院”看作是“电”加“影院”所得，由此得到的凝合程度会更高一些。因此，为了算出一个文本片段的凝合程度，我们需要枚举它的凝合方式这个文本片段是由哪两部分组
5、合而来的。,令p(x)为文本片段x在整个语料中出现的概率，那么我们定义“电影院”的凝合程度就是p(电影院)与p(电)p(影院)比值和p(电影院)与p(电影)p(院)的比值中的较小值，“的电影”的凝合程度则是p(的电影)分别除以p(的)p(电影)和p(的电)p(影)所得的商的较小值。,可以想到，凝合程度最高的文本片段就是诸如“蝙蝠”、“蜘蛛”、“彷徨”、“忐忑”、“玫瑰”之类的词了，这些词里的每一个字几乎总是会和另一个字同时出现，从不在其他场合中使用。,标准2词的外部的表现。,考虑“被子”和“辈子”这两个片段。我们可以说“买被子”、“盖被子”、“进被子”、“好被子”、“这被子”等等，在“被子”前
6、面加各种字；但“辈子”的用法却非常固定，除了“一辈子”、“这辈子”、“上辈子”、“下辈子”，基本上“辈子”前面不能加别的字了。“辈子”这个文本片段左边可以出现的字太有限，以至于直觉上我们可能会认为，“辈子”并不单独成词，真正成词的其实是“一辈子”、“这辈子”之类的整体。,标准2词的外部的表现。,文本片段的自由运用程度也是判断它是否成词的重要标准。如果一个文本片段能够算作一个词的话，它应该能够灵活地出现在各种不同的环境中，具有非常丰富的左邻字集合和右邻字集合。,Link:信息熵,“信息熵”是一个非常神奇的概念，它能够反映知道一个事件的结果后平均会给你带来多大的信息量。如果某个结果的发生概率为p，
7、当你知道它确实发生了，你得到的信息量就被定义为-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的信息量。这
8、个1.0114就是那颗骰子的信息熵。,Link:信息熵,“信息熵”是一个非常神奇的概念，它能够反映知道一个事件的结果后平均会给你带来多大的信息量。如果某个结果的发生概率为p，当你知道它确实发生了，你得到的信息量就被定义为-log(p)。p越小，你得到的信息量就越大。,现在，假如某颗骰子有100个面，其中99个面都是1，只有一个面上写的2。知道骰子的抛掷结果是2会给你带来一个巨大无比的信息量，它等于-log(1/100)，约为4.605；但你只有百分之一的概率获取到这么大的信息量，其他情况下你只能得到-log(99/100)0.01005的信息量。平均情况下，你只能获得0.056的信息量，这就是
9、这颗骰子的信息熵。,Link:信息熵,“信息熵”是一个非常神奇的概念，它能够反映知道一个事件的结果后平均会给你带来多大的信息量。如果某个结果的发生概率为p，当你知道它确实发生了，你得到的信息量就被定义为-log(p)。p越小，你得到的信息量就越大。,一个最极端的情况：如果一颗骰子的六个面都是1，投掷它不会给你带来任何信息，它的信息熵为-log(1)=0。什么时候信息熵会更大呢？,信息熵直观地反映了一个事件的结果有多么的随机,标准2词的外部的表现。,我们用信息熵来衡量一个文本片段的左邻字集合和右邻字集合有多随机。,吃葡萄不吐葡萄皮不吃葡萄倒吐葡萄皮,“葡萄”：4次,左邻字：吃,吐,吃,吐,右邻字
10、：不,皮,倒,皮,左邻字的信息熵=-(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,“被子”：956次,右邻字集合的信息熵3.87404,“辈子”：2330次,右邻字集合的信息熵4.11644,“被子”的左邻字用例非常丰富：用得最多的是“晒被子”，它一共出现了162次；其次是“的被子”，出现了85次；接下来分别是“条被子”、“在被子”、“床被子”，分别出现了69次、64次和52次；当然，还有“叠被子”、“盖被子”、“加被子”、“新被子”、“掀被子”、“收被子”、“薄被
11、子”、“踢被子”、“抢被子”等100多种不同的用法构成的长尾所有左邻字的信息熵为3.67453,“辈子”的左邻字就很可怜了，2330个“辈子”中有1276个是“一辈子”，有596个“这辈子”，有235个“下辈子”，有149个“上辈子”，有32个“半辈子”，有10个“八辈子”，有7个“几辈子”，有6个“哪辈子”，以及“n辈子”、“两辈子”等13种更罕见的用法。所有左邻字的信息熵仅为1.25963。,“下子”则是更典型的例子，310个“下子”的用例中有294个出自“一下子”，5个出自“两下子”，5个出自“这下子”，其余的都是只出现过一次的罕见用法。事实上，“下子”的左邻字信息熵仅为0.294421
12、，我们不应该把它看作一个能灵活运用的词。,一些文本片段的左邻字没啥问题，右邻字用例却非常贫乏，例如“交响”、“后遗”、“鹅卵”等，把它们看作单独的词似乎也不太合适。我们不妨就把一个文本片段的自由运用程度定义为它的左邻字信息熵和右邻字信息熵中的较小值。,文本片段的凝固程度和自由程度，两种判断标准缺一不可。只看凝固程度的话，程序会找出“巧克”、“俄罗”、“颜六色”、“柴可夫”等实际上是“半个词”的片段；只看自由程度的话，程序则会把“吃了一顿”、“看了一遍”、“睡了一晚”、“去了一趟”中的“了一”提取出来，因为它的左右邻字都太丰富了。,怎么用？,找出候选词,我们把文本中出现过的所有长度不超过d的子串
13、都当作潜在的词（即候选词，其中d为自己设定的候选词长度上限），再为出现频数、凝固程度和自由程度各设定一个阈值，然后只需要提取出所有满足阈值要求的候选词即可。为了提高效率，我们可以把语料全文视作一整个字符串，并对该字符串的所有后缀按字典序排序。,四是四十是十十四是十四四十是四十,十十十四是十四四十是四十十是十十四是十四四十是四十十是四十十四是十四四十是四十十四四十是四十是十十四是十四四十是四十是十四四十是四十是四十是四十是十十四是十四四十是四十四十四十是十十四是十四四十是四十四十是四十四是十四四十是四十四是四十是十十四是十四四十是四十四四十是四十,优势,相同的候选词都集中在了一起，从头到尾扫描一
14、遍便能算出各个候选词的频数和右邻字信息熵。将整个语料逆序后重新排列所有的后缀，再扫描一遍后便能统计出每个候选词的左邻字信息熵。另外，有了频数信息后，凝固程度也都很好计算了。这样，我们便得到了一个无需任何知识库的抽词算法，输入一段充分长的文本，这个算法能以大致O(nlogn)的效率提取出可能的词来。,结果如何？,西游记上册的抽词结果：,行者、师父、三藏、八戒、大圣、菩萨、悟空、怎么、和尚、唐僧、老孙、溃骸、什么、沙僧、太宗、徒弟、袈裟、妖精、玉帝、今日、兄弟、公主、玄奘、陛下、宝贝、性命、晓得、门外、妖魔、光蕊、观音、花果山、土地、木叉、东土、变化、变做、伯钦、判官、多少、真君、齐天大圣、蟠桃、
15、丞相、魏征、扯住、溃骸澳、抬头、揭谛、言语、猪八戒、兵器、吩咐、安排、叩头、清风、哪吒、左右、美猴王、钉钯、孩儿、女婿、金箍棒、二郎、东西、许多、奈何、人参果、收拾、近前、太保、明月、南海、水帘洞、门首、弼马温、李天王,词的频数从高到低排序,资本论全文的抽词结果：,商品、形式、货币、我们、过程、自己、机器、社会、部分、表现、没有、流通、需要、增加、已经、交换、关系、先令、积累、必须、英国、条件、发展、麻布、儿童、进行、提高、消费、减少、任何、手段、职能、土地、特殊、实际、完全、平均、直接、随着、简单、规律、市场、增长、上衣、决定、什么、制度、最后、支付、许多、虽然、棉纱、形态、棉花、法律、绝对
16、、提供、扩大、独立、世纪、性质、假定、每天、包含、物质、家庭、规模、考察、剥削、经济学、甚至、延长、财富、纺纱、购买、开始、代替、便士、怎样、降低、能够、原料、等价物,词的频数从高到低排序,时间简史全文的抽词结果：,黑洞、必须、非常、任何、膨胀、科学、预言、太阳、观察、定律、运动、事件、奇点、坍缩、问题、模型、方向、区域、知道、开始、辐射、部分、牛顿、产生、夸克、无限、轨道、解释、边界、甚至、自己、类似、描述、最终、旋转、爱因斯坦、绕着、什么、效应、表明、温度、研究、收缩、吸引、按照、完全、增加、开端、基本、计算、结构、上帝、进行、已经、发展、几乎、仍然、足够、影响、初始、科学家、事件视界、第二、改变、历史、世界、包含、准确、证明、导致、需要、应该、至少、刚好、提供、通过、似乎、继续、实验、复杂、伽利略,词的频数从高到低排序,人人网用户状态中最常出现的词是：,哈哈、什么、今天、怎么、现在、可以、知道、喜欢、终于、这样、觉得、因为、如果、感觉、开始、回家、考试、老师、幸福、朋友、时间、发现、东西、快乐、为什么、睡觉、生活、已经、希望、最后、各种、状态、世界、突然、手机
