2012年12月1日星期六

搜索引擎三巨头之争 Google凭借两项改进胜出


搜索引擎三巨头之争 Google凭借两项改进胜出

2009-03-26 07:55:59 来源: 赛迪网(北京) 跟帖 3 条
3月26日消息,Google凭借其两项改进性技术在为网络用户提供更优服务的比拼中胜出。
Google尽管一直以来都被视为搜索届的巨头,但其面临来自微软和雅虎的日益严峻的挑战,为此Google推出了两项更新为网络用户提供更优的搜索服务。
第一项改进包括,当用户输入三个以上的关键词后,系统会给出更长的结果描述。Google表示,为搜索用户提供包含关键词的更长的片断或摘录描述,可以更加有助于用户决定是否要浏览相关网页。
第二项改进则使用了新的“语义搜索”技术,可以更好地理解与搜索词相关的概念等,以便在搜索页面底部提供更有用的相关搜索。
Google在公司博客中写道:“例如搜索‘物理原理’,我们的算法将认为‘角动量’,‘相对论’,‘大爆炸理论’和‘量子力学’等相关词句都将有助于找到用户需要的。”
这两项改进意味着用户会一直停留在Google的网页内,而无须浏览其他网站。由于数以万计的网站都仰仗Google搜索向网络用户提供信息,所以一旦搜索量减少,就意味着该搜索相当具争议性。
Google在博客中表示:“我们一直在努力寻求更佳的方法为用户提供最高效的网络搜索服务。即使你没有发觉我们的变化,我们也保证坚持努力工作为用户提供高品质的网络搜索体验。”
微软最近证实其确实在对Kumo语义搜索服务测试,以期其能替代微软实时搜索(Live Search)服务,而后者一直都位列Google和雅虎之后。雅虎最近也宣布其SearchMonkey的新特性可以在搜索结果中增加Flash视频和游戏。 (本文来源:赛迪网 作者:李一静)

从精准到推荐:大数据时代重构网络广告商业模式


从精准到推荐:大数据时代重构网络广告商业模式

——2012-10-29 10:57来源:互联网周刊作者:姜奇平

  现在的网络广告,发展空间还很大,因为他们把99%的赚钱空间都扔了。随着大数据的发展,这些钱会被下一代一一捡回来。到那时,人们对于从精准到推荐的道理,会认识得更清楚。
  未来广告将是这样的,广告对于不同的人,呈现不同的内容。按照这个精准标准衡量,现在几乎所有的广告,在将来都已经被淘汰了。
  精准是相对于消费者需要而言的。由于不精准,所以消费者不需要。精准的问题,就是如何真正挖掘出消费者个性化需求的问题。大数据时代提供了什么样的契机?精准广告是否将向生活方式推荐的方向发展?让我们从未来学观点展望一下网络广告商业模式的重构。

  马上将时髦起来的RTB
  我们首先从最传统的说起。当然,从未来学尺度看,明年才流行的,就是我们这里说的最传统的(或叫正当红的、最时髦的等等)。否则未来淘汰什么呢?
  据说今年是中国广告的RTB元年。RTB(Real Time Bidding),即实时竞价广告,是正当红、最时髦的广告热点。
  RTB跟传统形式比较起来,广告批发市场(Ad Exchange)上卖的不是传统意义上的广告位了,而是访问这个广告位的具体用户。这个看起来,比过去的广告位精准多了。以前,如果电梯里,上来一个没牙的老头,你在电梯里打的牙膏广告肯定瞎了。现在,相当于盯住的不是广告,而是那个看广告的人。需要盯住这个用户的兴趣爱好,投其所好,才能产生最大的收益。RTB相当于把炙手可热的用户,拍卖给广告商。广告主冲的是购买更好的广告位和广告曝光率。
  新的精准广告形式的出现,也带来广告管理方式的变革。在海外,人们建设了需求端平台DSP,帮助广告代理公司实现互联网广告的优化投放。随后,广告供应端平台SSP、数据管理平台DMP等细分平台也不断出现和发展,使广告管理手段越来越先进。
  数据化进程也在加快,DMP(数据管理平台)和Data Exchange(数据交易平台)的出现,会帮助广告主、广告代理商和媒体主更好地整理数据和应用数据,从而为RTB中用户的价值计算、广告的针对性投放提升效果,进一步推动RTB产业的发展。
  RTB是怎么实现精准的呢?假设潜在客户在浏览某网页面,某网向广告交易平台(Ad Exchange)请求广告。交易平台向所有需求端平台(DSP)发出公告,“某网有访客,要不要向他发广告”。DSP请求数据管理平台(DMP)帮助分析这位访客,并根据结果进行出价决策。Ad Exchange为出价高的DSP匹配相关广告代码。
  在中国,易传媒为代表的新型网络广告企业正成为这一领域的佼佼者。易传媒先后推出了包括AdManager广告操作系统 、ASP供应端广告平台和ADP需求端广告平台在内的整合数字广告平台。ADP整合DAS和DSP二大需求端广告操作系统,是专为广告主/代理商开发的需求端广告技术平台;ASP是专为中国互联网和移动互联网媒体主打造的技术平台。
  据Pubmatic数据,2011年RTB方式的购买在美国已超过10亿。IDC预计2012年RTB会占全部展示类广告的20%。到今年7月为止,根据Accordant Media统计的2012年第二季度的全球RTB市场份额较去年同期提升128%。
  当前,广告商围着RTB分田分地正忙,整天惦记着如何在RTB方式中向Ad Exchange,Ad Network,DSP之间分配资源以发大财。
  因为是在谈未来学,我们得谈谈这种即将时髦的东东,将来过时在什么地方。
  RTB和所有传统广告一样,仍然是生产者的大喇叭。是以生产者为中心,用推技术向消费者强推的广告。只不过,过去打的是散弹,一打一片,现在比较能一枪一准了。消费者接受广告的方式,仍然跟“躺着挨枪”差不多。他不是找上门来,而是实在躲不过去。
  当真正的大数据(而不仅仅是“很大的数据”)到来后,广告业会发生什么进一步的变化呢?

  基于语义网的广告  
  其实,要说大数据,也不过是它背后一直在拱的那个力量,推动到表面上的东西。要说清大数据,就需要把同样跟它一样浮在表面上的东西,如WEB、移动、定位、2.0等等,联系在一起看,还原出推动变化的背后之手。
  现在还没有一个更好的词,比语义网(Semantic Web)这个概念更适合把上面的东西串起来。语义网是伯纳斯·李——就是伦敦奥运会开幕式上那位互联网传奇人物——提出来的。语义网首先符合大数据的标准,是异构数据的聚合;其次它又是2.0的,代表着从WEB的P2P到移动互联网的Html5的前沿;它还是自组织自协调的社会网络计算,还是其它许多许多。不过,语义网就象概念跑车,它不是开到马路上实用的。它更象一种气场,把各种众生之物笼罩在它之下,发出灵光。
  当我们用语义网这盏聚光灯,照向广告的时候,会发现广告的根基在动摇。
  现有广告的原型,仍然是“纸”这样的媒介,这张“纸”(无论是文字、音频、视频)只不过是一块屏幕,是打给受众看(被动接受)的。语义网却完全颠覆了介质本身,它不再仅仅是一张纸,或一块屏,更象是中医的经络,只不过是语义的经络,“意义经络”,用网络串接起来的语义的经络。任何广告人也没有见过这样的事:你见过纸长了经络吗,你见过电梯屏能通向经络吗?俗称大数据、WEB之类的东东,最终都可以被用于打通,广告的任督二脉。只有把消费者心中的意义打通,精准才有的放矢。下一代广告的精准就不再仅仅象RTB、LBS这样定位到人,而是顺着意义经络,直接定位到心,作用于人心的向背。
  这样说,可能显得比较空玄。让我们还是从身边容易理解的事情说起。口碑广告,大家都是知道的。口碑广告在技术上不算先进,但是有一点,它钻入人心的能力非常强,可以把人心打通。这就是意义的感应在起作用,也就是人心与人心,在一定信息通道作用下,彼此信任产生认同。口碑传播在低技术条件下,效率有限。因为,口耳相传效果虽好,但比不上广播、电视、报纸传播得快,传播得广。广告业虽也利用口碑传播,但更多是作为辅助手段。
  但如果同语义网结合起来,就彻底不同了。它将对现在传统的广告中间商构成冲击。广告将演化为一场把广告商边缘化的大众狂欢。
  我们观察到,口碑传播正是没有技术的P2P,是点对点互动传播。现有的广告不是点对点模式的,而是主从模式,更象老师对学生(RTB之前是学生满地跑,老师抓不住;RTB以后是老师逮住学生,一通猛灌);点对点相当于学生告诉学生(喻用户告知用户),没有老师(喻广告商)在场。
  大数据时代第一个巨大变化,是把P2P改造成了Html5,相当于可以在技术层面之上,把应用P2P化。将来移动互联网上的应用,可以象口碑传播那样,彼此之间发生感应,产生泛广告化的趋势。Html5相当于把所有水库的大坝(比喻操作系统、客户端甚至平台)都毁掉,让WEB应用自己与自己产生拓扑联系,就象终端不走服务器,自己与自己相联一样。博客、微博、微信等,只不过是这个浪潮在原始阶段的时髦预演。这些自媒体都正在通向“自广告”。
  没有大坝把水组织起来,水(喻应用)不就泛滥成灾了吗?换句话说,没有广告商居间,广告不就乱套了吗?不会,语义网规划了一条应用自组织的路,我称之为应用感应,也就是Web App与Web App之间,只要打通意义经络,就可以象心灵感应那样,自组织、自协调起来。SNS就是这场变革的预演。我们已经从中看到了规律,小世界网络反映的就是这种明显的规律,这样的规律在这类去中心化的组织形态中,发挥着过去只有统治者、AGENT才能起到的关键作用。将来的广告,也是Real Time的,只不过不是RTB,而是TRE(实时一切)的。它更加强调此时、此地的精准对撞,并且快聚快散,速配化。
  广告除了不会大乱外,还会向更加精准的方向自发演进。因为还有大数据在。
  精准不精准,对于大数据来说,不能满足于仅仅锁定人——LBS也可以锁定到人,支付也可以锁定到人——它的真正长处是可以锁定意义,也就是被LBS、支付、RTB锁定的那些人的头脑里的想法,这些想法在当地与此下的焦聚点。简单说,就是实现从人身的精准到人心的精准。
  在这一过程中,网络广告将会发生从1.0向2.0的飞跃,这既是机遇,更是挑战。
  首先,万维网本身升级为语义网,会彻底改变网络广告的生存环境。现有万维网与电视、大街等的广告环境,都是圈占一块人来人往的热闹之处,相对集中地投放广告。语义网采用给内容加入标记的方式构筑WEB环境,相当于将使广告屏之内和广告屏之外的界限被打破,如果你能想像这样的事发生,你就会明白这种界限的打破意味着什么:你走在大街上,低头系鞋带,发现鞋带断了,这时忽然脚前的砖亮了,上面显示你右前方50米第一个柜台有配你这双鞋的鞋带。实际上,语义网会使每个网页都成为这样一块智能的广告砖。广告人必须适应从集中投放,向离散化投放的转变。
  其次,现有的数据都是集中在数据中心(如数据平台)进行计算,这种中央计算模式相对于2.0仍然是传统模式,真正的一对一精准广告是不可能用这种方式完成的。有人可能会说,一对一只是(对细分到某一程度)比喻的说法,真正的一个对一个网上营销永远也不可能经济地实现。错,这只是中央计算模式的单方面结论。如果考虑到语义网泛在化,包括移动化的事实后,数据分析发生的一个戏剧性的变化,可能是从中央计算模式,向本地计算的转移。也就是说,每个人的手机,可能成为自主计算中心。广告的最核心计算,可能在去中心化的地方完成。你可能会摸我的脑门,看我是不是发烧或说胡话。如果是这样,我只好说,这笔钱要等你12岁以下的后代去挣了。
  我们的后代,跟我们的做法有什么不一样呢?他们的大数据,是两点计算(本地+中心计算),而不是我们的一点计算(中心计算)。举个例子就清楚了。比如拿一道题来考我们两代人:细分到条数来卖咖啡,广告该怎么打?我们这一代可能这样回答,我们从数据中心计算结果中,把顾客分为10条装的一类,40条装的一类,分开打广告;稍为改进,还可以算出常买40条装的人,活动规律是什么,给他来个RTB;我们的后代可能根本不是这么想的:他们的想法很可能是用优惠券诱使顾客打开(本地)手机chick in(那时的隐私保护是很严的哟),开放咖啡数据0.001秒,根据每个人手机私有云上独一无二的专属数据计算结果,直接告诉你,我知道你,是17条咖啡的常客;你,今天下午有个会,而今晨5点才睡觉,需要2条特浓咖啡发给你一个只属于你一个人的广告。让一个产品的广告,对每个人内容都不一样,这个超级难题,只花0.000001度电的成本就轻松实现了。
  日本野村证券分析这种趋势,辨识出这是一种叫“产消逆转”的大趋势。意思是,过去集中模式中,我们的经济过程,都以生产者为起点,以消费者为终点;未来分散模式中,消费者成了起点,生产者成了终点。对大数据,对广告来说,产消逆转将导致头脚倒立的新型广告的出现。我们不知道还会有什么新鲜事情会发生,也许PUSH技术将成为过街老鼠,建立在客户服务器基础上的广告公司将象建立在沙滩上的房子一样垮掉,而基于PULL技术的广告将成为新的时尚。
  
  重构网络广告商业模式的远景  
  再次声明一下,这里作为重构对象的网络广告,还并没过时,准确说,还有待未来两三年去发生、去时髦。这里之所以提前解构它们,是为了帮助读者看清几十集后的大结局,好提前做好心理准备;也为错过当前这网鱼的人们,预测一下未来。
  上面说过,未来广告的核心变化方向,是从现在每个人看同样内容的广告,演化为每个人看不同内容的广告。语义网之所以重要,就在于它使内容,从死的(无标记的),变为活的(有标记的)。从难以加工出意义的(非智慧的),变为容易加工出意义的(智慧的)。但语义网究竟只是技术。生产力再牛,也得靠商业帮忙落地。大数据对网络广告商业模式的冲击,最终将落脚于何处?我们不妨大胆想象,让实践来小心求证。
  广告说到底,要做的事情就是推荐。考虑商业模式的变化,先要从根子上想一想,同样是做推荐这件事,还有什么样更好的方法。过去没有条件想,现在有了大数据,有更好的工具和手段了,我们可以去想改变做事的方式。至少可以思考,新概念的推荐,可能或可以是什么样。
  从广告界忙晕了头的状态中跳出来,跳到庐山之外来想广告这件事,不免会发现广告这件事作为推荐活动的与生俱来的一些缺点。我们观察自然的推荐活动,可以发现人们在接受推荐的时候,真正需要的是什么。两相对比,就会得到一些未来更贴近消费者的商业模式的线索。有时候,行内人也许会觉得这些不是问题,或是问题但永远解决不了,但有了大数据,谁知道呢?不要让钱都跑了,才明白。
  首先,为什么只有1%的人忙活广告,而不是99%的人参与广告服务?实际意思是:广告推荐为什么总是生产者教导模式,为什么不能是让所有消费者参与推荐呢?
  比如分析一个女友挽着另一个女友挑衣服这个常见的场景。如果我们把帮助挑衣服的女友,视为一个广告服务者。她的角色中至少包含了两个没花广告公司成本的职能:一是她在介绍产品信息,这是广告提供的基础产品,其属性是媒体功能;二是她在帮助女友拿主意(咨询),这是广告提供的增值服务,其属性是渠道功能。两者都是一对一精准化的,因此是高附加值的。
  美国IT女王戴森在名著《2.0版——数字化时代的生活设计》中,曾把上面那种帮人家挑衣服的女孩,称为“生活方式设计师”。未来会出现成千上万个这样的自由职业。那时众包模式还没有出现,广告商还不可能大规模组织这种不要工资的生活设计师,加入到推荐者的行业中来。未来,进入人人时代,无组织的组织力量,会以产消逆转的方式,把消费者组织起来,投入到2.0的广告中。在这个模式中,广告商挣的主要不是媒体的钱,而是商务的钱。换句话说,他以前以为互联网只是媒体(挣广告费),未来可以当作渠道了(挣服务费)。把看漏的那一半互联网,找补回来。
  你不可能为每个上街购物的人速配出自小长大的发小相伴,办法是用众包的方式,在地球村上为她找出最合适的生活方式设计师。具体分析可以看出,这一模式的实现,完全依赖于大数据。因为要让一位陌生的生活方式设计师为你的顾客推荐方案,设计师需要了解这个顾客与别的顾客有什么不同。我们前面说的手机数据语义网本地计算,就可以提供充分的数据支持。未来广告商要在商业模式上做的工作,是搭建与顾客本地数据对接的数据采集与分析平台,并且同拥有众多生活方式设计师接口的众包平台进行对接。
  其次,为什么只有1%的公司打广告,99%的公司不打广告。这是上一个疑问,反过来问。现有广告的商业模式,因为是集中模式,最大的商业缺陷,是丧失了99%打广告的企业。99%的企业极为渴望打广告,从哪里看出来呢?他们中的一些人,整天在电线杆和车站牌上贴狗皮膏药,并与市容城管进行艰苦卓绝的战斗。如果没有打广告的强烈愿望作支撑,是不可能有这种近乎爬雪山过草地的劲头的。
  但是,这99%的企业,并不想往中央电视台投广告,他们心目中的理想媒体,应该具有电线杆的某种特征。下一代的网络广告,就是要模仿出具有同样分散程度的分布式的、符合HTML5特点的“电线杆子”。例如,日本有6000万用户,习惯了二维码的广告形式。只要一个简单的刷的动作,整个过程就完成了。我看照片,有的还真是把二维码印在商店门口的电线杆上。内容估计是:来吧,向右两门,某某打折。当然,别真的把思路局限在电线杆上了。比方,也可以创新出一种形式,每个柜台上安一个按纽,模仿我第二炮兵部队发射精确致导“导弹”——打折券,对LBS锁定的50米范围的目标客户的手机,进行定向发射。背后的功课是,这部手机携带的号码,被系统cookie监测到出发前,曾上网集中搜索阿迪达斯某新款的价格,而那一款现在正趴在你柜台后第三排第二个格子里。
  由于篇幅所限,不能展开谈,但仅从有限谈到的这些,我们看到,现在的网络广告,发展空间还很大,因为他们把99%的赚钱空间都扔了。随着大数据的发展,这些钱会被下一代一一捡回来。到那时,人们对于从精准到推荐的道理,会认识得更清楚。 

语义技术让大数据变成“智慧数据”


语义技术让大数据变成“智慧数据”

image
美国State Street金融服务公司的首席科学家David Saul
State Street是美国最大的金融服务公司之一。 两年前在公司首席科学家David Saul的领导下, State Street 开始采用语义技术来整合公司各种数据库,使得大数据真正变成了“智慧数据”。 在接受SearchCIO采访时,David Saul介绍了State Street的经验,以下是访谈的主要内容整理:
语义技术实际上是把已有的数据加上语义。 可以把它想象成在现有结构化或者非结构化的数据库上的一个语义叠加层。 在State Street, 对同一个客户, 因为我们的庞大系统在不同的时间, 有不同的人员开发。 导致了我们在各个地方都散落着同一用户的不同数据。 语义技术所做的就是在这些数据之上添加一个语义映射层, 告诉我们“在这儿的这部分数据和在那儿的那部分数据, 都是指的同一个客户”。
这样做的好处非常多, 举个例子来说, 当我们在做风险评估的时候, 我们经常需要对某个企业或者某个地区的风险做出评估报告。 在没有用语义技术之前, 这样的报告是很花时间的。我们需要把不同地点不同结构的的相关风险数据导入一个新的数据库。 然后由专人进行分析, 把关联的部分整合。 从而生成一系列的报告。 而采用了语义技术, 我们只需要根据语义映射,把相关的数据整合起来,很快就能够出一系列临时或者常规的报告。 而我们不需要实际去移动数据。 这样可以节省了大量的时间。 尤其是类似于风险评估这样的工作, 对时间要求很高。如果我们能够很快的完成评估, 就可能避免风险, 避免金融损失。
进行语义数据库搜索有点类似于在Google使用关键字搜索。 Google的搜索使你可以关联两个不相关的网站。语义搜索有点类似, 它可以使在数据层面关联不同的数据。 不过语义技术与搜索不同, 它实际上对数据进行了标签化处理。 这种标签化处理的好处是, 一次投资, 长期有效。日后如果添加新的数据库, 甚至公司合并其他公司的数据库, 这些标签化的数据仍然有效。
最近两年, 市场上开始有了语义技术的商业工具, 现在的工具可以支持语义映射, 存储及合并的功能。 可以支持大数据。 数据分析不仅仅体现在数据量上,更应该体现为数据的含义上。 从这个意义上说,“智慧数据”更有意义一些。
语义技术的采用, 使得State Street获益匪浅。 不过, 要是在整个行业都能够采用的话, 那么不但State Street, 行业内的其他伙伴, 以及客户都会从中获益。 目前, 类似于 EDM Council (企业数据管理协会)的组织正在致力于一些标准化的工作(如在金融行业的某些产品的语义映射标准化)。 如果有了这些标准化的推动,那么语义技术在大数据时代的起飞将指日可待。

从奇异值分解(SVD)看潜在语义索引(LSI)


从奇异值分解(SVD)看潜在语义索引(LSI)

 上篇文章简单形象地介绍了LSI 以及LSI 的用途。从中可以看到LSI 的核心运算在于SVD(Singular Value Decomposition),本文希望通过介绍SVD以及LSI对SVD的用法,补充分析 LSI 的本质及对不同问题的适用性。(不过限于本人数学修养有限,并没有对“本质”一挖到底。不过文章末尾的附注留下了足够的向导信息,希望继续探寻数学本质的同学可以依之展开学习)

   1. SVD 简介
    SVD中文称为“奇异值分解”,是一种矩阵分解方法。其公式如下:
    定理:设A为m*n阶复矩阵,则存在m阶矩阵U和n阶矩阵V,使得:
   A = U*S*V’     其中S=diag(σi,σ2,……,σr),σi>0 (i=1,…,r),r=rank(A)。
     其中 A 矩阵是我们初始的特征矩阵,在文本挖掘中:A就是 t (term) 行 d (document) 列的矩阵,每列是一篇文章,每行是一个单词,每个单元格的当前单词在当前文章里的出现次数。 U 是一个 t 行 r 列 的矩阵, V 是一个 r 行 d 列 的矩阵, S 是一个 r 行 r 列的对角矩阵。这里 r 的大小是 A的秩。那么U和V中分别是A的奇异向量,而S是A的奇异值。AA'的正交单位特征向量组成U,特征值组成S'S,A'A的正交单位特征向量组成V,特征值(与AA'相同)组成SS'。( 关于秩是什么,特征值是什么,这个分解是怎么得到的,可以暂不去管)
      注意,这个公式是等号,也就是等号左边完全等价于等号右边。换句话说我们只是把原来的A换了一种表示形式而已,并没有丢失任何信息。就好像 24 = 2 * 3 * 4 一样。 也正是因此,如果 LSI 直接使用 SVD 的话,不仅 r 是不可控的,而且 r 很可能很大以至于起不到降维效果,事实上这样做不仅没降维而且耗费了大量的运算时间。而 SVD 作为一种矩阵分解方法,也并非仅仅用在 LSI 中。Matlab中有直接的svd函数可以使用:[U,S,V] = svd(A) 

   2. LSI 对 SVD 的使用
   LSI 对 SVD 做了一点改变,就是对 S 的 r 个对角线元素进行了排序,并只保留前 k 个值 ( k < r ), 后 r - k 个置零。此时,可以证明等式右边是在最小二乘意义下对等式左边的最佳近似。事实上这个过程是把数据集的特征值(在SVD中用奇异值表征)按照重要性排列,降维的过程就是舍弃不重要的特征向量的过程,而剩下的特征向量张成空间为降维后的空间。
   看到这里,我们能得到最重要的启发就是,LSI 是通过舍弃不重要的特征向量来达到降维效果的,而又由于特征向量是根据矩阵运算得出的,因此 LSI 在降维的过程中不仅丢失了信息,而且还改变了信息。降维后的数据集仅仅是对原数据集的一种近似而非等价形式。且降维幅度越大,与原信息的偏离就越大。

  3. LSI 的适用性
  1) 特征降维
   LSI 本质上是把每个特征映射到了一个更低维的子空间(sub space),所以用来做降维可以说是天造地设。在降维这块土地上还有另一位辛勤的耕耘者那就是TFIDF,TFIDF通过一个简单的公式(两个整数相乘)得到不同单词的重要程度,并取前k个最重要的单词,而丢弃其它单词,这里只有信息的丢失,并没有信息的改变。从执行效率上 TFIDF 远远高于 LSI,不过从效果上(至少在学术界)LSI 要优于TFIDF。
   不过必须提醒的是,无论是上述哪一种降维方法,都会造成信息的偏差,进而影响后续分类/聚类的准确率。 降维是希望以可接受的效果损失下,大大提高运行效率和节省内存空间。然而能不降维的时候还是不要降维(比如你只有几千篇文档要处理,那样真的没有必要降维)

  2)单词相关度计算
   LSI 的结果通过简单变换就能得到不同单词之间的相关度( 0 ~ 1 之间的一个实数),相关度非常高的单词往往拥有相同的含义。不过不要被“潜在语义”的名称所迷惑,所谓的潜在语义只不过是统计意义上的相似,如果想得到同义词还是使用同义词词典靠谱。LSI 得到的近义词的特点是它们不一定是同义词(甚至词性都可能不同),但它们往往出现在同类情景下(比如“魔兽” 和 “dota”)。不过事实上直接使用LSI做单词相关度计算的并不多,一方面在于现在有一些灰常好用的同义词词典,另外相对无监督的学习大家还是更信任有监督的学习(分类)得到的结果。

    3)聚类
    直接用 LSI 聚类的情景我还没有见过,但使用该系列算法的后续变种 PLSI, LDA 进行聚类的的确有一些。其中LDA聚类还有些道理(因为它本身就假设了潜在topic的联合概率分布),用 LSI 进行聚类其实并不合适。本质上 LSI 在找特征子空间,而聚类方法要找的是实例分组。 LSI 虽然能得到看起来貌似是聚类的结果,但其意义不见得是聚类所想得到的。一个明显的例子就是,对于分布不平均的样本集(比如新闻类的文章有1000篇,而文学类的文章只有10篇), LSI/PLSI 得到的往往是相对平均的结果(A类500篇,B类600篇),这种情况下根本无法得到好的聚类结果。相对传统聚类方法k-means, LSI 系列算法不仅存在信息的偏差(丢失和改变),而且不能处理分布不均的样本集。
    对于 LSI/PLSI 来说,聚类的意义不在于文档,而在于单词。所以对于聚类的一种变型用法是,当 k 设的足够大时,LSI/PLSI 能够给出落在不同子空间的单词序列,基本上这些单词之间拥有较为紧密的语义联系。其实这种用法本质上还是在利用降维做单词相关度计算。

附注:
本文部分信息来自百度百科。对数学知识感兴趣的同学可以参照以下链接展开阅读:奇异值分解矩阵特征值行列式
Tip: 行列式是一切问题的渊源,如果下图行列式的公式大家看不懂的话,就可以考虑赞不深入探索了:

隐性语义索引


发信人: walt@ncicbbs (瓦尔特), 信区: chinese
标  题: ◎ 隐性语义索引
发信站: 国家智能机中心曙光站 (Thu Apr 11 12:02:51 1996)
转信站: ncicbbs

                隐性语义索引

                   .Walt.

1. 引言
        

自然语言文本中的词汇(术语)具有一词多义(polysemy)和一义多词(synonymy)的特点. 
由于一词多义, 基于精确匹配的检索算法会报告许多用户不要的东西; 由于一义多词, 
基于精确匹配的检索算法又会遗漏许多用户想要的东西.

下面是一个例子:

设Doc1, Doc2, Doc3是三个文件. 一些术语在这三个文件中的出现情况如下表:


            Doc1          Doc2         Doc3
--------------------------------------------------
access       X                                          document     X
retrieval    X                          X
information                X*           X*
theory                     X
database     X
indexing     X
computer                   X*           X*
--------------------------------------------------

这里, 假定用"information" 和"computer"作为主题词进行检索, 那么Doc2和Doc3与之
精确匹配, 因而中选. 然而, Doc2是用户并不想要的文件, Doc1才是想要的查不出来, 
不想要的倒查了出来. 这说明精确匹配不能很好地反映用户的意图. 那么有没有更好的
办法呢?

当然, 如果能基于自然语言理解来做这件事, 那一切问题就都没有了. 问题是:
(1) 自然语言理解的目前水平还是有限度的; (2) 即使用自然语言理解, 效率也会很低.
 我们希望找到一种办法, 既能反映术语之间内在的相关性, 又具有较高的效率.

Bellcore以Dumais为首的研究小组提出了一种称为"隐性语义索引"的方法, 试图绕过
自然语言理解, 用统计的办法达到同样的目标. "隐性语义索引"的英文名字为
"Latent Semantic Indexing", 简称LSI.                         

2. LSI的做法

首先, 以术语(terms)为行, 文件(documents)为列做一个大矩阵(matrix). 设一共有
t行d列, 矩阵名为X. 矩阵的元素为术语在文件中的出现频度.

数学上可以证明: X可以分解为三个矩阵T0, S0, D0'(D0的转置)的积. 其中T0和D0的
列向量都是正交归一化的, S0是对角矩阵. T0是t*m矩阵, S0是m*m矩阵,D0是d*m矩阵, 
m是X的秩. 这种分解叫做单值分解(singlar value decomposition,简称SVD).

                        X=T0*S0*D0'

一般要求T0, S0, D0都是满秩的. 不难做到把S0的元素沿对角线从大到小排列.

现在, 把S0的m个对角元素的前k个保留, 后m-k个置0, 我们可以得到一个新的近似的
分解:

                        Xhat=T*S*D'                     

奇妙的是, Xhat在最小二乘意义下是X的最佳近似! 这样, 我们实际上有了一个"降维"的
途径. 下面要说明, T, S, D三个矩阵在文件检索中有重要的应用价值.

一个遗留问题是k到底取多大. k越大失真越小, 但开销越大. k的选择是按实际问题的
要求进行平衡的结果.      
                                     
给定矩阵X, 基于X可以问三类同文件检索密切有关的问题:

(1) 术语i和j有多相似?

(2) 文件i和j有多相似?

(3) 术语i和文件j有多相关?

第一类问题是术语的类比和聚类问题;

第二类问题是文件的类比和聚类问题;

第三类问题是术语和文件的关联问题.

下面我们用Xhat来进行这三类比较.

3.1 比较两个术语
                          
做"正向"乘法:

                Xhat*Xhat'=T*S*D'*D*S*T'=T*S^2*T'

(D'*D=I, 因为D已经是正交归一的). 它的第i行第j列表明了术语i和j的相似程度.

3.2 比较两个文件

做"逆向"乘法:

                Xhat'*Xhat=D*S*T'*T*S*D'=D*S^2*D'

(T'*T=I, 因为T已经是正交归一的). 它的第i行第j列表明了文件i和j的相似程度.

3.3 比较一个文件和一个术语

恰巧就是Xhat本身. 它的第i行第j列表明了术语i和文件j的相关联程度.

3.4 查询

可以把主题词的集合认为是一个虚拟的文件. 查询的任务说白了是把这个虚拟的文
件和其他文件做相似性比较, 挑选最相似的出来(挑选到什么程度打住, 要看实际问题
的要求) 

*********************


以上极简略地介绍了LSI的做法. 实验表明, 这一做法可以收到很好的效果, 在基于
内容的查询和信息过滤等方面有很好的前景.

Google推出语义食谱搜索


Google推出语义食谱搜索

 发表于 2011/02/25/ 10:54 | 分类标签: 
评论    

Google也贪吃,但吃得更讲究。周四Google推出了一个食谱搜索引擎,不仅可以根据食材推荐食谱,而且还可以告诉你含热量多高,甚至需要多长时间才能做好。
Google上有百分之一的搜索词和食谱相关,Google此次推出的食谱垂直搜索旨在让人们通过互联网发现美食。并且厚道的Google并不在搜索结果中显示食谱,而是链接到美食网站。
食谱搜索出现在搜索结果页面的左侧边栏,排在购物、新闻、图片、视频等垂直搜索的下面,并提供了一些过滤选项,比如找到一种红咖喱食谱,然后从中选出一种含热量在300卡路里以内,里面放辣椒的红咖喱。
但真正的创新在后台:整个搜索引擎都建立在结构化数据基础之上,这些数据是由站长在网页中通过标记代码添加的,人看不见,但对机器非常有用。所谓语义网的梦想就是让所有的网页都充满相关的底层标签,这样所有搜索引擎都可以通过对网页的语义分析得出用户的Email、餐馆的营业时间等信息。
Google称这对目前的互联网来说是个挑战,因为人们还在探索自然语言搜索。这是互联网现存的方式,互联网如此之大,如此不确定。这个不可改变的庞然大物需要自己改变自己,不会听从你的安排。
结构化网络的理想几乎无法实现,因为它要求人们合作制定标准,并且要求网页制作者花时间通过复杂的XML对网页进行标记。一种被称为“微格式(Microformats)”的更加平民化的做法则取得了更大成功,因为它只关注某几类数据,并创造性地通过HTML简化了元数据的发布。Google曾在2009年提出了类似的富文本摘要(Rich Snippets)。
而现在终于有一家主流搜索引擎开始完全采纳微格式和其它结构化数据。
但语义网也面临着一个鸡和蛋的问题:如果对任何人都没用的话,为什么要在网页中添加结构化的元数据呢?如果没有结构化的元数据,那么怎么会有公司花费时间和精力在网上找到元数据呢?
“这其实是对语义网之梦的现实回应。如果真有一个XML世界存在的话,我们当然高兴,那会让搜索引擎更靠谱,可是没人会做那样的事情。但我们需要在某个地方切入,互联网的很多内容都是人们手动创建的,他们的时间非常宝贵。”Google如是说。

漫话中文自动分词和语义识别(下):句法结构和语义结构


漫话中文自动分词和语义识别(下):句法结构和语义结构
icon2 Brain Storm | icon4 2012-01-05 16:25| icon351 Comments | 本文内容遵从CC版权协议 转载请注明出自matrix67.com
    这篇文章是漫话中文分词算法的续篇。在这里,我们将紧接着上一篇文章的内容继续探讨下去:如果计算机可以对一句话进行自动分词,它还能进一步整理句子的结构,甚至理解句子的意思吗?这两篇文章的关系十分紧密,因此,我把前一篇文章改名为了《漫话中文自动分词和语义识别(上)》,这篇文章自然就是它的下篇。我已经在很多不同的地方做过与这个话题有关的演讲了,在这里我想把它们写下来,和更多的人一同分享。
    什么叫做句法结构呢?让我们来看一些例子。“白天鹅在水中游”,这句话是有歧义的,它可能指的是“白天有一只鹅在水中游”,也可能指的是“有一只白天鹅在水中游”。不同的分词方案,产生了不同的意义。有没有什么句子,它的分词方案是唯一的,但也会产生不同的意思呢?有。比如“门没有锁”,它可能是指的“门没有被锁上”,也有可能是指的“门上根本就没有挂锁”。这个句子虽然只能切分成“门/没有/锁”,但由于“锁”这个词既有可能是动词,也有可能是名词,因而让整句话产生了不同的意思。有没有什么句子,它的分词方案是唯一的,并且每个词的词义也都不再变化,但整个句子仍然有歧义呢?有可能。看看这句话:“咬死了猎人的狗”。这句话有可能指的是“把猎人的狗咬死了”,也有可能指的是“一只咬死了猎人的狗”。这个歧义是怎么产生的呢?仔细体会两种不同的意思后,你会发现,句子中最底层的成分可以以不同的顺序组合起来,歧义由此产生。

    在前一篇文章中,我们看到了,利用概率转移的方法,我们可以有效地给一句话分词。事实上,利用相同的模型,我们也能给每一个词标注词性。更好的做法则是,我们直接把同一个词不同词性的用法当作是不同的词,从而把分词和词性标注的工作统一起来。但是,所有这样的工作都是对句子进行从左至右线性的分析,而句子结构实际上比这要复杂多了,它是这些词有顺序有层次地组合在一起的。计算机要想正确地解析一个句子,在分词和标注词性后,接下来该做的就是分析句法结构的层次。
    在计算机中,怎样描述一个句子的句法结构呢? 1957 年, Noam Chomsky 出版了《句法结构》一书,把这种语言的层次化结构用形式化的方式清晰地描述了出来,这也就是所谓的“生成语法”模型。这本书是 20 世纪为数不多的几本真正的著作之一,文字非常简练,思路非常明晰,震撼了包括语言学、计算机理论在内的多个领域。记得 Quora 上曾经有人问 Who are the best minds of the world today ,投出来的答案就是 Noam Chomsky 。
    随便取一句很长很复杂的话,比如“汽车被开车的师傅修好了”,我们总能至顶向下地一层层分析出它的结构。这个句子最顶层的结构就是“汽车修好了”。汽车怎么修好了呢?汽车被师傅修好了。汽车被什么样的师傅修好了呢?哦,汽车被开车的师傅修好了。当然,我们还可以无限地扩展下去,继续把句子中的每一个最底层的成分替换成更详细更复杂的描述,就好像小学语文中的扩句练习那样。这就是生成语法的核心思想。
    熟悉编译原理的朋友们可能知道“上下文无关文法”。其实,上面提到的扩展规则本质上就是一种上下文无关文法。例如,一个句子可以是“什么怎么样”的形式,我们就把这条规则记作
      句子 → 名词性短语+动词性短语
    其中,“名词性短语”指的是一个具有名词功能的成分,它有可能就是一个名词,也有可能还有它自己的内部结构。例如,它有可能是一个形容词性短语加上“的”再加上另一个名词性短语构成的,比如“便宜的汽车”;它还有可能是由“动词性短语+的+名词性短语”构成的,比如“抛锚了的汽车”;它甚至可能是由“名词性短语+的+名词性短语”构成的,比如“老师的汽车”。我们把名词性短语的生成规则也都记下来:
      名词性短语 → 名词
      名词性短语 → 形容词性短语+的+名词性短语
      名词性短语 → 动词性短语+的+名词性短语
      名词性短语 → 名词性短语+的+名词性短语
      ⋯⋯
    类似地,动词性短语也有诸多具体的形式:
      动词性短语 → 动词
      动词性短语 → 动词性短语+了
      动词性短语 → 介词短语+动词性短语
      ⋯⋯
    上面我们涉及到了介词短语,它也有自己的生成规则:
      介词短语 → 介词+名词性短语
      ⋯⋯
    我们构造句子的任务,也就是从“句子”这个初始结点出发,不断调用规则,产生越来越复杂的句型框架,然后从词库中选择相应词性的单词,填进这个框架里:
      
    而分析句法结构的任务,则是已知一个句子从左到右各词的词性,要反过来求出一棵满足要求的“句法结构树”。这可以用 Earley parser 来实现。
    这样看来,句法结构的问题似乎就已经完美的解决了。其实,我们还差得很远。生成语法有两个大问题。首先,句法结构正确的句子不见得都是好句子。 Chomsky 本人给出了一个经典的例子: Colorless green ideas sleep furiously 。形容词加形容词加名词加动词加副词,这是一个完全符合句法要求的序列,但随便拼凑会闹出很多笑话——什么叫做“无色的绿色的想法在狂暴地睡觉”?顺便插播个广告,如果你还挺喜欢这句话的意境的,欢迎去我以前做的 IdeaGenerator 玩玩。不过,如果我们不涉及句子的生成,只关心句子的结构分析,这个缺陷对我们来说影响似乎并不大。生成语法的第二个问题就比较麻烦了:从同一个词性序列出发,可能会构建出不同的句法结构树。比较下面两个例子:
      老师 被 迟到 的 学生 逗乐 了
      电话 被 窃听 的 房间 找到 了
    它们都是“名词+介词+动词+的+名词+动词+了”,但它们的结构并不一样,前者是老师被逗乐了,“迟到”是修饰“学生”的,后者是房间找到了,“电话被窃听”是一起来修饰房间的。但是,纯粹运用前面的模型,我们无法区分出哪句话应该是哪个句法结构树。如何强化句法分析的模型和算法,让计算机构建出一棵正确的句法树,这成了一个大问题。
    让我们来看一个更简单的例子吧。同样是“动词+形容词+名词”,我们有两种构建句法结构树的方案:
      
    未经过汉语语法训练的朋友可能会问,“点亮蜡烛”和“踢新皮球”的句法结构真的不同吗?我们能证明,这里面真的存在不同。我们造一个句子“踢破皮球”,你会发现对于这个句子来说,两种句法结构都是成立的,于是出现了歧义:把皮球踢破了(结构和“点亮蜡烛”一致),或者是,踢一个破的皮球(结构和“踢新皮球”一致)。
    但为什么“点亮蜡烛”只有一种理解方式呢?这是因为我们通常不会把“亮”字直接放在名词前做定语,我们一般不说“一根亮蜡烛”、“一颗亮星星”等等。为什么“踢新皮球”也只有一种理解方式呢?这是因为我们通常不会把“新”直接放在动词后面作补语,不会说“皮球踢新了”,“衣服洗新了”等等。但是“破”既能作定语又能作补语,于是“踢破皮球”就产生了两种不同的意思。如果我们把每个形容词能否作定语,能否作补语都记下来,然后在生成规则中添加限制条件,不就能完美解决这个问题了吗?
    基于规则的句法分析器就是这么做的。汉语语言学家们已经列出了所有词的各种特征:
      亮:词性 = 形容词,能作补语 = True ,能作定语 = False ⋯⋯
      新:词性 = 形容词,能作补语 = False ,能作定语 = True ⋯⋯
      ⋯⋯
    当然,每个动词也有一大堆属性:
      点:词性 = 动词,能带宾语 = True ,能带补语 = True ⋯⋯
      踢:词性 = 动词,能带宾语 = True ,能带补语 = True ⋯⋯
      污染:词性 = 动词,能带宾语 = True ,能带补语 = False ⋯⋯
      排队:词性 = 动词,能带宾语 = False ,能带补语 = False ⋯⋯
      ⋯⋯
    名词也不例外:
      蜡烛:词性 = 名词,能作主语 = True ,能作宾语 = True ,能受数量词修饰 = True ⋯⋯
      皮球:词性 = 名词,能作主语 = True ,能作宾语 = True ,能受数量词修饰 = True ⋯⋯
      ⋯⋯
    有人估计会觉得奇怪了:“能作主语”也是一个属性,莫非有些名词不能做主语?哈哈,这样的名词不但有,而且还真不少:剧毒、看头、厉害、正轨、存亡⋯⋯这些词都不放在动词前面。难道有些名词不能做宾语吗?这样的词也有不少:享年、芳龄、心术、浑身、家丑⋯⋯这些词都不放在动词后面。这样说来,存在不受数量词修饰的词也就不奇怪了,事实上上面这些怪异的名词前面基本上都不能加数量词。
    另外一个至关重要的就是,这些性质可以“向上传递”。比方说,我们规定,套用规则
      名词性短语 → 形容词性短语+名词性短语
    后,整个名词性短语能否作主语、能否作宾语、能否受数量词修饰,这将取决于它的第二个构成成分。通俗地讲就是,如果“皮球”能够作主语,那么“新皮球”也能够作主语。有了“词语知识库”,又确保了这些知识能够在更高层次得到保留,我们就能给语法生成规则添加限制条件了。例如,我们可以规定,套用规则
      动词性短语 → 动词性短语+名词性短语
    的前提条件就是,那个动词性短语的“能带宾语”属性为 True ,并且那个名词性短语“能作宾语”的属性为 True 。另外,我们规定
      动词性短语 → 动词性短语+形容词性短语
    必须满足动词性短语的“能带补语”属性为 True ,并且形容词性短语“能作补语”属性为 True 。这样便阻止了“踢新皮球”中的“踢”和“新”先结合起来,因为“新”不能作补语。
    最后我们规定,套用规则
      名词性短语 → 形容词性短语+名词性短语
    时,形容词性短语必须要能作定语。这就避免了“点亮蜡烛”中的“亮”和“蜡烛”先组合起来,因为“亮”通常不作定语。这样,我们便解决了“动词+形容词+名词”的结构分析问题。
    当然,这只是一个很简单的例子。在这里的问题 6 、 7 、 8 中你可以看到,一条语法生成规则往往有很多限制条件,这些限制条件不光是简单的“功能相符”和“前后一致”,有些复杂的限制条件甚至需要用 IF … THEN … 的方式来描述。你可以在这里看到,汉语中词与词之间还有各种怪异的区别特征,并且哪个词拥有哪些性质纯粹是知识库的问题,完全没有规律可循。一个实用的句法结构分析系统,往往拥有上百种属性标签。北京大学计算语言所编写了《现代汉语语法信息词典》,它里面包含了 579 种属性。我们的理想目标就是,找到汉语中每一种可能会影响句法结构的因素,并据此为词库里的每一个词打上标签;再列出汉语语法中的每一条生成规则,找到每一条生成规则的应用条件,以及应用这条规则之后,整个成分将会以怎样的方式继承哪些子成分的哪些属性,又会在什么样的情况下产生哪些新的属性。按照生成语言学的观点,计算机就应该能正确解析所有的汉语句子了。


    那么,这样一来,计算机是否就已经能从句子中获取到理解语义需要的所有信息了呢?答案是否定的。还有这么一些句子,它从分词到词义到结构都没有两可的情况,但整个句子仍然有歧义。考虑这句话“鸡不吃了”,它有两种意思:鸡不吃东西了,或者我们不吃鸡了。但是,这种歧义并不是由分词或者词义或者结构导致的,两种意思所对应的语法结构完全相同,都是“鸡”加上“不吃了”。但为什么歧义仍然产生了呢?这是因为,在句法结构内部,还有更深层次的语义结构,两者并不相同。
    汉语就是这么奇怪,位于主语位置上的事物既有可能是动作的发出者,也有可能是动作的承受者。“我吃完了”可以说,“苹果吃完了”也能讲。然而,“鸡”这个东西既能吃,也能被吃,歧义由此产生。
    位于宾语位置上的事物也不一定就是动作的承受者,“来客人了”、“住了一个人”都是属于宾语反而是动作发出者的情况。记得某次数理逻辑课上老师感叹,汉语的谓词非常不规范,明明是太阳在晒我,为什么要说成是“我晒太阳”呢?事实上,汉语的动宾搭配范围极其广泛,还有很多更怪异的例子:“写字”是我们真正在写的东西,“写书”是写的结果,“写毛笔”是写的工具,“写楷体”是写的方式,“写地上”是写的场所,“写一只狗”,等等,什么叫做“写一只狗”啊?我们能说“写一只狗”吗?当然可以,这是写的内容嘛,“同学们这周作文写什么啊”,“我写一只狗”。大家可以想像,学中文的老外看了这个会是什么表情。虽然通过句法分析,我们能够判断出句子中的每样东西都和哪个动词相关联,但从语义层面上看这个关联是什么,我们还需要新的模型。
    汉语语言学家把事物与动词的语义关系分为了 17 种,叫做 17 种“语义角色”,它们是施事、感事、当事、动力、受事、结果、系事、工具、材料、方式、内容、与事、对象、场所、目标、起点、时间。你可以看到,语义角色的划分非常详细。同样是动作的发出者,施事指的是真正意义上的发出动作,比如“他吃饭”中的“他”;感事则是指某种感知活动的经验者,比如“他知道这件事了”中的“他”;当事则是指性质状态的主体,比如“他病了”中的“他”;动力则是自然力量的发出者,比如“洪水淹没了村庄”中的“洪水”。语义角色的具体划分以及 17 这个数目是有争议的,不过不管怎样,这个模型本身能够非常贴切地回答“什么是语义”这个问题。
    汉语有一种“投射理论”,即一个句子的结构是由这个句子中的谓语投射出来的。给定一个动词后,这个动词能够带多少个语义角色,这几个语义角色都是什么,基本上都已经确定了。因而,完整的句子所应有的结构实际上也就已经确定了。比如,说到“休息”这个动词,你就会觉得它缺少一个施事,而且也不缺别的了。我们只会说“老王休息”,不会说“老王休息手”或者“老王休息沙发”。因而我们认为,“休息”只有一个“论元”。它的“论元结构”是:
      休息 <施事>
    因此,一旦在句子中看到“休息”这个词,我们就需要在句内或者句外寻找“休息”所需要的施事。这个过程有一个很帅的名字,叫做“配价”。“休息”就是一个典型的“一价动词”。我们平时接触的比较多的则是二价动词。不过,它们具体的论元有可能不一样:
      吃 <施事,受事>
      去 <施事,目标>
      淹没 <动力,受事>
    三价动词也是有的,例如
      送 <施事,受事,与事>
    甚至还有零价动词,例如
      下雨 <Ф>
    下面我们要教计算机做的,就是怎样给动词配价。之前,我们已经给出了解析句法结构的方法,这样计算机便能判断出每个动词究竟在和哪些词发生关系。语义分析的实质,就是确定出它们具体是什么关系。因此,语义识别的问题,也就转化为了“语义角色标注”的问题。然而,语义角色出现的位置并不固定,施事也能出现在动词后面,受事也能出现在动词前面,怎样让计算机识别语义角色呢?在回答这个问题之前,我们不妨问问自己:我们是怎么知道,“我吃完了”中的“我”是“吃”的施事,“苹果吃完了”中的“苹果”是“吃”的受事的呢?大家肯定会说,废话,“我”当然只能是“吃”的施事,因为我显然不会“被吃”;“苹果”当然只能是“吃”的受事,因为苹果显然不能发出“吃”动作。也就是说,“吃”的两个论元都有语义类的要求。我们把“吃”的论元结构写得更详细一些:
      吃 <施事[语义类:人|动物],受事[语义类:食物|药物]>
而“淹没”一词的论元结构则可以补充为:
      淹没 <动力[语义类:自然事物],受事[语义类:建筑物|空间]>
    所以,为了完成计算机自动标注语义角色的任务,我们需要人肉建立两个庞大的数据库:语义类词典和论元结构词典。这样的人肉工程早就已经做过了。北京语言大学 1990 年 5 月启动的“九〇五语义工程”就是人工构建的一棵规模相当大的语义树。它把词语分成了事物、运动、时空、属性四大类,其中事物类分为事类和物类,物类又分为具体物和抽象物,具体物则再分为生物和非生物,生物之下则分了人类、动物、植物、微生物、生物构件五类,非生物之下则分了天然物、人工物、遗弃物、几何图形和非生物构件五类,其中人工物之下又包括设施物、运载物、器具物、原材料、耗散物、信息物、钱财七类。整棵语义树有 414 个结点,其中叶子结点 309 个,深度最大的地方达到了 9 层。论元结构方面则有清华大学和人民大学共同完成的《现代汉语述语动词机器词典》,词典中包括了各种动词的拼音、释义、分类、论元数、论元的语义角色、论元的语义限制等语法和语义信息。
    说到语义工程,不得不提到董振东先生的知网。这是一个综合了语义分类和语义关系的知识库,不但通过语义树反映了词与词的共性,还通过语义关系反映了每个词的个性。它不但能告诉你“医生”和“病人”都是人,还告诉了你“医生”可以对“病人”发出一个“医治”的动作。知网的理念和 WordNet 工程很相似,后者是 Princeton 在 1985 年就已经开始构建的英文单词语义关系词典,背后也是一个语义关系网的概念,词与词的关系涉及同义词、反义词、上下位词、整体与部分、子集与超集、材料与成品等等。如果你装了 Mathematica,你可以通过 WordData 函数获取到 WordNet 的数据。至于前面说的那几个中文知识库嘛,别问我,我也不知道上哪儿取去。

    看到这里,想必大家会欢呼,啊,这下子,在中文信息处理领域,从语法到语义都已经漂亮的解决了吧。其实并没有。上面的论元语义角色的模型有很多问题。其中一个很容易想到的就是隐喻的问题,比如“信息淹没了我”、“悲伤淹没了我”。一旦出现动词的新用法,我们只能更新论元结构:
      淹没 <动力[语义类:自然事物|抽象事物],受事[语义类:建筑物|空间|人类]>
    但更麻烦的则是下面这些违背语义规则的情况。一个是否定句,比如“张三不可能吃思想”。一个是疑问句,比如“张三怎么可能吃思想”。更麻烦的就是超常现象。随便在新闻网站上一搜,你就会发现各种不符合语义规则的情形。我搜了一个“吃金属”,立即看到某新闻标题《法国一位老人以吃金属为生》。要想解决这些问题,需要给配价模型打上不少补丁。

    然而,配价模型也仅仅解决了动词的语义问题。其他词呢?好在,我们也可以为名词发展一套类似的配价理论。我们通常认为“教师”是一个零价名词,而“老师”则是一个一价名词,因为说到“老师”时,我们通常会说“谁的老师”。“态度”则是一个二价的名词,因为我们通常要说“谁对谁的态度”才算完整。事实上,形容词也有配价,“优秀”就是一个一价形容词,“友好”则是一个二价形容词,原因也是类似的。配价理论还有很多更复杂的内容,这里我们就不再详说了。
    但还有很多配价理论完全无法解决的问题。比如,语义有指向的问题。“砍光了”、“砍累了”、“砍钝了”、“砍快了”,都是动词后面跟形容词作补语,但实际意义各不相同。“砍光了”指的是“树砍光了”,“砍累了”指的是“人砍累了”,“砍钝了”指的是“斧子砍钝了”,“砍快了”指的是“砍砍快了”。看来,一个动词的每个论元不但有语义类的限制,还有“评价方式”的限制。
    两个动词连用,也有语义关系的问题。“抓住不放”中,“抓住”和“不放”这两个动作构成一种反复的关系,抓住就等于不放。“说起来气人”中,“说起来”和“气人”这两个动作构成了一种条件关系,即每次发生了“说起来”这个事件后,都会产生“气人”这个结果。大家或许又会说,这两种情况真的有区别吗?是的,而且我能证明这一点。让我们造一个句子“留着没用”,你会发现它出现了歧义:既可以像“抓住不放”一样理解为反复关系,一直把它留着一直没有使用;又可以像“说起来气人”一样理解为条件关系,留着的话是不会有用的。因此,动词与动词连用确实会产生不同的语义关系,这需要另一套模型来处理。
    虚词的语义更麻烦。别以为“了”就是表示完成,“这本书看了三天”表示这本书看完了,“这本书看了三天了”反而表示这本书没看完。“了”到底有多少个义项,现在也没有一个定论。副词也算虚词,副词的语义同样捉摸不定。比较“张三和李四结婚了”与“张三和李四都结婚了”,你会发现描述“都”字的语义没那么简单。

    不过,在实际的产品应用中,前面所说的这些问题都不大。这篇文章中讲到的基本上都是基于规则的语言学处理方法。目前更实用的,则是对大规模真实语料的概率统计分析与机器学习算法,这条路子可以无视很多具体的语言学问题,并且效果也相当理想。最大熵模型和条件随机场都是目前非常常用的自然语言处理手段,感兴趣的朋友可以深入研究一下。但是,这些方法也有它们自己的缺点,就是它们的不可预测性。不管哪条路,似乎都离目标还有很远的一段距离。期待在未来的某一日,自然语言处理领域会迎来一套全新的语言模型,一举解决前面提到的所有难题。

漫话中文自动分词和语义识别(上):中文分词算法


漫话中文自动分词和语义识别(上):中文分词算法
icon2 Brain Storm | icon4 2011-03-10 11:04| icon374 Comments | 本文内容遵从CC版权协议 转载请注明出自matrix67.com
    记得第一次了解中文分词算法是在 Google 黑板报 上看到的,当初看到那个算法时我彻底被震撼住了,想不到一个看似不可能完成的任务竟然有如此神奇巧妙的算法。最近在詹卫东老师的《中文信息处理导论》课上再次学到中文分词算法,才知道这并不是中文分词算法研究的全部,前前后后还有很多故事可讲。在没有建立统计语言模型时,人们还在语言学的角度对自动分词进行研究,期间诞生了很多有意思的理论。
    中文分词的主要困难在于分词歧义。“结婚的和尚未结婚的”,应该分成“结婚/的/和/尚未/结婚/的”,还是“结婚/的/和尚/未/结婚/的”?人来判断很容易,要交给计算机来处理就麻烦了。问题的关键就是,“和尚未”里的“和尚”也是一个词,“尚未”也是一个词,从计算机的角度看上去,两者似乎都有可能。对于计算机来说,这样的分词困境就叫做“交集型歧义”。
    有时候,交集型歧义的“歧义链”有可能会更长。“中外科学名著”里,“中外”、“外科”、“科学”、“学名”、“名著”全是词,光从词库的角度来看,随便切几刀下去,得出的切分都是合理的。类似的例子数不胜数,“提高产品质量”、“鞭炮声响彻夜空”、“努力学习语法规则”等句子都有这样的现象。在这些极端例子下,分词算法谁优谁劣可谓是一试便知。

    最简单的,也是最容易想到的自动分词算法,便是“最大匹配法”了。也就是说,从句子左端开始,不断匹配最长的词(组不了词的单字则单独划开),直到把句子划分完。算法的理由很简单:人在阅读时也是从左往右逐字读入的,最大匹配法是与人的习惯相符的。而在大多数情况下,这种算法也的确能侥幸成功。不过,这种算法并不可靠,构造反例可以不费吹灰之力。例如,“北京大学生前来应聘”本应是“北京/大学生/前来/应聘”,却会被误分成“北京大学/生前/来/应聘”。
    维护一个特殊规则表,可以修正一些很机械的问题,效果相当不错。例如,“不可能”要划分成“不/可能”,“会诊”后面接“断”、“疗”、“脉”、“治”时要把“会”单独切出,“的确切”后面是抽象名词时要把“的确切”分成“的/确切”,等等。
    还有一个适用范围相当广的特殊规则,这个强大的规则能修正很多交集型歧义的划分错误。首先我们要维护一个一般不单独成词的字表,比如“民”、“尘”、“伟”、“习”等等;这些字通常不会单独划出来,都要跟旁边的字一块儿组成一个词。在分词过程中时,一旦发现这些字被孤立出来,都重新考虑它与前面的字组词的可能。例如,在用最大匹配法切分“为人民服务”时,算法会先划出“为人”一词,而后发现“民”字只能单独成词了。查表却发现,“民”并不能单独划出,于是考虑进行修正——把“为人”的“人”字分配给“民”字。巧在这下“为”和“人民”正好都能成词,据此便可得出正确的划分“为/人民/服务”。

    不过,上述算法归根结底,都是在像人一样从左到右地扫描文字。为了把问题变得更加形式化,充分利用计算机的优势,我们还有一种与人的阅读习惯完全不同的算法思路:把句子作为一个整体来考虑,从全局的角度评价一个句子划分方案的好坏。设计自动分词算法的问题,也就变成了如何评估分词方案优劣的问题。最初所用的办法就是,寻找词数最少的划分。注意,每次都匹配最长的词,得出的划分不见得是词数最少的,错误的贪心很可能会不慎错过一些更优的路。因而,在有的情况下,最少词数法比最大匹配法效果更好。若用最大匹配法来划分,“独立自主和平等互利的原则”将被分成“独立自主/和平/等/互利/的/原则”,一共有 6 个词;但词数更少的方案则是“独立自主/和/平等互利/的/原则”,一共只有 5 个词。
    当然,最少词数法也会有踩大便的时候。“为人民办公益”的最大匹配划分和最少词数划分都是“为人/民办/公益”,而正确的划分则是“为/人民/办/公益”。同时,很多句子也有不止一个词数最少的分词方案,最少词数法并不能从中选出一个最佳答案。不过,把之前提到的“不成词字表”装备到最少词数法上,我们就有了一种简明而强大的算法:
    对于一种分词方案,里面有多少词,就罚多少分;每出现一个不成词的单字,就加罚一分。最好的分词方案,也就是罚分最少的方案。
    这种算法的效果出人意料的好。“他说的确实在理”是一个很困难的测试用例,“的确”和“实在”碰巧也成词,这给自动分词带来了很大的障碍。但是“确”、“实”、“理”通常都不单独成词的,因此很多切分方案都会被扣掉不少分:
      他/说/的/确实/在理 (罚分:1+1+1+1+1 = 5 )
      他/说/的确/实/在理 (罚分:1+1+1+2+1 = 6 )
      他/说/的确/实在/理 (罚分:1+1+1+1+2 = 6 )
    正确答案胜出。
    需要指出的是,这个算法并不需要枚举所有的划分可能。整个问题可以转化为图论中的最短路径问题,利用动态规划效率则会更高。
    算法还有进一步加强的余地。大家或许已经想到了,“字不成词”有一个程度的问题。“民”是一个不成词的语素,它是绝对不会单独成词的。“鸭”一般不单独成词,但在儿歌童谣和科技语体中除外。“见”则是一个可以单独成词的语素,只是平时我们不常说罢了。换句话说,每个字成词都有一定的概率,每个词出现的频率也是不同的。
    何不用每个词出现的概率,来衡量分词的优劣?于是我们有了一个更标准、更连续、更自动的改进算法:先统计大量真实语料中各个词出现的频率,然后把每种分词方案中各词的出现概率乘起来作为这种方案的得分。利用动态规划,不难求出得分最高的方案。
    以“有意见分歧”为例,让我们看看最大概率法是如何工作的。查表可知,在大量真实语料中,“有”、“有意”、“意见”、“见”、“分歧”的出现概率分别是 0.0181 、 0.0005 、 0.0010 、 0.0002 、 0.0001 ,因此“有/意见/分歧”的得分为 1.8×10-9 ,但“有意/见/分歧”的得分只有 1.0×10-11 ,正确方案完胜。
    这里的假设是,用词造句无非是随机选词连在一块儿,是一个简单的一元过程。显然,这个假设理想得有点不合理,必然会有很多问题。考虑下面这句话:
      这/事/的确/定/不/下来
    但是概率算法却会把这个句子分成:
      这/事/的/确定/不/下来
    原因是,“的”字的出现概率太高了,它几乎总会从“的确”中挣脱出来。
    其实,以上所有的分词算法都还有一个共同的大缺陷:它们虽然已经能很好地处理交集型歧义的问题,却完全无法解决另外一种被称为“组合型歧义”的问题。所谓组合型歧义,就是指同一个字串既可合又可分。比如说,“个人恩怨”中的“个人”就是一个词,“这个人”里的“个人”就必须拆开;“这扇门的把手”中的“把手”就是一个词,“把手抬起来”的“把手”就必须拆开;“学生会宣传部”中的“学生会”就是一个词,“学生会主动完成作业”里的“学生会”就必须拆开。这样的例子非常多,“难过”、“马上”、“将来”、“才能”、“过人”、“研究所”、“原子能”都有此问题。究竟是合还是分,还得取决于它两侧的词语。到目前为止,所有算法对划分方案的评价标准都是基于每个词固有性质的,完全不考虑相邻词语之间的影响;因而一旦涉及到组合型歧义的问题,最大匹配、最少词数、概率最大等所有策略都不能实现具体情况具体分析。
    于是,我们不得不跳出一元假设。此时,便有了那个 Google 黑板报上提到的统计语言模型算法。对于任意两个词语 w1 、 w2 ,统计在语料库中词语 w1 后面恰好是 w2 的概率 P(w1, w2) 。这样便会生成一个很大的二维表。再定义一个句子的划分方案的得分为 P(∅, w1) · P(w1, w2) · … · P(wn-1, wn) ,其中 w1, w2, …, wn 依次表示分出的词。我们同样可以利用动态规划求出得分最高的分词方案。这真是一个天才的模型,这个模型一并解决了词类标注、语音识别等各类自然语言处理问题。
    至此,中文自动分词算是有了一个漂亮而实用的算法。


    但是,随便拿份报纸读读,你就会发现我们之前给出的测试用例都太理想了,简直就是用来喂给计算机的。在中文分词中,还有一个比分词歧义更令人头疼的东西——未登录词。中文没有首字母大写,专名号也被取消了,这叫计算机如何辨认人名地名之类的东西?最近十年来,中文分词领域都在集中攻克这一难关。
    在汉语的未定义词中,中国人名的规律是最强的了。根据统计,汉语姓氏大约有 1000 多个,其中“王”、“陈”、“李”、“张”、“刘”五大姓氏的覆盖率高达 32% ,前 400 个姓氏覆盖率高达 99% 。人名的用字也比较集中,“英”、“华”、“玉”、“秀”、“明”、“珍”六个字的覆盖率就有 10.35% ,最常用的 400 字则有 90% 的覆盖率。虽然这些字分布在包括文言虚词在内的各种词类里,但就用字的感情色彩来看,人名多用褒义字和中性字,少有不雅用字,因此规律性还是非常强的。根据这些信息,我们足以计算一个字符串能成为名字的概率,结合预先设置的阈值便能很好地识别出可能的人名。
    可是,如何把人名从句子中切出来呢?换句话说,如果句中几个连续字都是姓名常用字,人名究竟应该从哪儿取到哪儿呢?人名以姓氏为左边界,相对容易判定一些。人名的右边界则可以从下文的提示确定出来:人名后面通常会接“先生”、“同志”、“校长”、“主任”、“医生”等身份词,以及“是”、“说”、“报道”、“参加”、“访问”、“表示”等动作词。
    但麻烦的情况也是有的。一些高频姓氏本身也是经常单独成词的常用字,例如“于”、“马”、“黄”、“常”、“高”等等。很多反映时代性的名字也是本身就成词的,例如“建国”、“建设”、“国庆”、“跃进”等等。更讨厌的就是那些整个名字本身就是常用词的人了,他们会彻底打乱之前的各种模型。如果分词程序也有智能的话,他一定会把所有叫“高峰”、“汪洋”的人拖出去斩了;要是听说了有人居然敢叫“令计划”,估计直接就崩溃了。
    还有那些恰好与上下文组合成词的人名,例如:
     费孝通向人大常委会提交书面报告
     邓颖超生前使用过的物品
    这就是最考验分词算法的句子了。
    相比之下,中国地名的用字就分散得多了。北京有一个地方叫“臭泥坑”,网上搜索“臭泥坑”,第一页全是“臭泥坑地图”、“臭泥坑附近酒店”之类的信息。某年《重庆晨报》刊登停电通知,上面赫然印着“停电范围包括沙坪坝区的犀牛屙屎和犀牛屙屎抽水”,读者纷纷去电投诉印刷错误。记者仔细一查,你猜怎么着,印刷并无错误,重庆真的就有叫“犀牛屙屎”和“犀牛屙屎抽水”的地方。
    好在,中国地名数量有限,这是可以枚举的。中国地名委员会编写了《中华人民共和国地名录》,收录了从高原盆地到桥梁电站共 10 万多个地名,这让中国地名的识别便利了很多。
    真正有些困难的就是识别机构名了,虽然机构名的后缀比较集中,但左边界的判断就有些难了。更难的就是品牌名了。如今各行各业大打创意战,品牌名可以说是无奇不有,而且经常本身就包含常用词,更是给自动分词添加了不少障碍。
    最难识别的未登录词就是缩略语了。“高数”、“抵京”、“女单”、“发改委”、“北医三院”都是比较好认的缩略语了,有些缩略语搞得连人也是丈二和尚摸不着头脑。你能猜到“人影办”是什么机构的简称吗?打死你都想不到,是“人工影响天气办公室”。
    汉语中构造缩略语的规律很诡异,目前也没有一个定论。初次听到这个问题,几乎每个人都会做出这样的猜想:缩略语都是选用各个成分中最核心的字,比如“安全检查”缩成“安检”,“人民警察”缩成“民警”等等。不过,反例也是有的,“邮政编码”就被缩成了“邮编”,但“码”无疑是更能概括“编码”一词的。当然,这几个缩略语已经逐渐成词,可以加进词库了;不过新近出现的或者临时构造的缩略语该怎么办,还真是个大问题。
    说到新词,网络新词的大量出现才是分词系统真正的敌人。这些新词汇的来源千奇百怪,几乎没有固定的产生机制。要想实现对网络文章的自动分词,目前来看可以说是相当困难的。革命尚未成功,分词算法还有很多进步的余地。

语义搜索:Google的人类知识图谱


语义搜索:Google的人类知识图谱

第二章, 微格式:语义标注和常义冲突

第二章, 微格式:语义标注和常义冲突

分类: data mining 

随着“网络”一词的不断革新,微格式(microformat)是前进中重要的一步,因为它提供了一种机制能嵌入“聪明的数据”到网页中,并且易于内容提供者来实现。简单的说,微格式是规定了如何增加结构化数据到网页中,且不用修改原网页。这一节将主要介绍微格式,并且深入一些实例将用到XFN(XHTML Friends Network),geo, hRecipe 以及 hReview等微格式。特别的,我们将从博客链接中挖掘人的关系,从网页中抽取坐标,从foodnetwork.com中解析菜单,并且分析对这些菜单的评论。本章中示例代码的实现没有处理全部的解析细节,但足够能将你领上道了。以微格式如geo或hRecipe来标记数据被称作社会化数据,它是令人感兴趣的,且社会化数据将不断增加。在写这本书的时候,几乎有一半的网页开发页报告有用到微格式,microformats.org社区刚刚庆祝了它的5岁生日。google报告有94%概率,富摘要信息(Google在搜索结果里引入的一种新的网站信息显示方式)中包含了微格式,如果google宣传了这点,我们将看到微格式重要的增长;事实上,通过ReadWriteWeb,google想要看到50%的网页包含了某种形式的语义标注,并且鼓励公司通过奖励的形式来支持这一动机。不管怎么说,你将看到更多的微格式,如果你关心网络的话。让我们进入正题吧。


XFN和朋友关系

语义网的狂热者预言像FOAF(friend of a friend --一种实体论描述人与人之间的关系,活动和活动之间的关系)这样的技术可能有一天会成为催化剂,促使很多社交网络联合起来对抗如Facebook这样的平台。虽然这些所谓的语义网技术如FOAF目前还达不到这点,但也不用太惊讶。如果你知道一些关于网络的短暂历史,那么你就会认识到这个革新是不容易的,因为网络极其分散的性质让它很难一蹴而就(参见第10章),然而,变化正在持续的,稳固的,向前进化着。微格式的出现就是为填补网页上“智能数据”的空白,它是一个很好的示范带给已有的技术以规范的标准。在这种特定情况下,它拉近了传统网络(基于易于人类阅读的HTML4.01)和语议网络(更加友好,易于机器解释)的距离。

微格式的好处在于,它提供了一种方法去嵌入这样的数据:社交网络,日程,摘要,书签;并且是反向兼容的。微格式的生态系统是多种多样的,如geo就发展得很快,并随着搜索引擎,社交媒体网站,博客平台而大受欢迎,而其它微格式则发展缓慢。当正写这本书的时候,重要的微格式开发正在进行中,包括google宣称他们在宣摘要信息中支持hRecipe.表2-1提供了一个总结对一些受欢迎的微格式。更多的示例请看http://microformats.org/wiki/examples-in-the-wild

表2-1, 一些受欢迎的技术云去嵌入结构化数据到网页中



还有其他很多微格式你可能会碰到,但是一个好方法是,认准池塘中最大的那条鱼,如Google, Yahoo!, 以及Facebook.越多的人用到微格式,它就越可能成功,越对数据挖掘有用。


通过XFN导出社交联系

随着一点梗概关于微格式是如何适应整个网络空间,下面让我们转向一个操作性的XFN(可能是目前你所遇到的最受欢迎的微格式)程序。如你所知,XFN是一种方式,来标识与他人之间的朋友关系,以在其他标签中加入rel属性。XFN常用在博客中,特别是博客链接插件中,像WordPress提供的那样。考虑如下的HTML内容,如示例2-1, 这可能会出现在博客的友链中。

示例2-1,XFN标注示例

[html] view plaincopy
  1. <div>  
  2. <a href="http://example.org/matthew" rel="me">Matthew</a>  
  3. <a href="http://example.com/users/jc" rel="friend met">J.C.</a>  
  4. <a href="http://example.com/users/abe" rel="friend met co-worker">Abe</a>  
  5. <a href="http://example.net/~baseeret" rel="spouse met">Baseeret</a>  
  6. <a href="http://example.net/~lindsaybelle" rel="child met">Lindsay Belle</a>  
  7. </div>  

从以上内容的rel标签,可以很明显的看出这些人之间的关系。名叫做Matthew的家伙,有一帮朋友,一位妻子,一个小孩,他和这些朋友中的一个是同事,他在日常生活中和大家见面(这情况在网上也许不会发生)。除去规范的语法外,这就是XFN的全部内容。好消息是,虽然它非常简单,但在大规模情形下,它非常有用,由于它是结构化的数据。除非你碰到一些数据严重的过时--如两个最好的朋友变成了敌人,而忘记了更新他们的博客链接--XFN给出了非常准备的信息关于两个人之间的联系。已知大部分博客平台支持XFN,有很多的信息可以去发现。坏消息是,XFN只能告诉你这些信息,如果要得到更多的信息,需要借助其它的微格式。

让我们来看一个简单的获取XFN数据的例子,它类似于rubhub(http://rubhub.com/,一个社会化的搜索引擎,它爬取和索引大量的网站信息通过XFN)提供的服务,你可能想看一下在线的XFN工具在进入下一节之前。


一个宽度优先的XFN数据爬虫

让我们通过XFN获取社交数据, 并以此建立一个社交图谱。已知XFN可以嵌入任何可信的网站,坏消息是我们要做一些网站爬取工作。好消息是,虽然很繁琐,但BeautifulSoup包帮你最小化了这些麻烦。示例2-2的代码涉及到Ajaxian( 一个很受欢迎的博客关于现代化的网站开发),作为图的基础。在运行它之前请用easy_install安装BeautifulSoup.

示例2-2,从网页中爬取XFN内容(microformats__xfn_scrape.py

[python] view plaincopy
  1. # -*- coding: utf-8 -*-  
  2.   
  3. import sys  
  4. import urllib2  
  5. import HTMLParser  
  6. from BeautifulSoup import BeautifulSoup  
  7.   
  8. # Try http://ajaxian.com/  
  9. URL = sys.argv[1]  
  10.   
  11. XFN_TAGS = set([  
  12.     'colleague',  
  13.     'sweetheart',  
  14.     'parent',  
  15.     'co-resident',  
  16.     'co-worker',  
  17.     'muse',  
  18.     'neighbor',  
  19.     'sibling',  
  20.     'kin',  
  21.     'child',  
  22.     'date',  
  23.     'spouse',  
  24.     'me',  
  25.     'acquaintance',  
  26.     'met',  
  27.     'crush',  
  28.     'contact',  
  29.     'friend',  
  30.     ])  
  31.   
  32. try:  
  33.     page = urllib2.urlopen(URL)  
  34. except urllib2.URLError:  
  35.     print 'Failed to fetch ' + item  
  36.   
  37. try:  
  38.     soup = BeautifulSoup(page)  
  39. except HTMLParser.HTMLParseError:  
  40.     print 'Failed to parse ' + item  
  41.   
  42. anchorTags = soup.findAll('a')  
  43.   
  44. for a in anchorTags:  
  45.     if a.has_key('rel'):  
  46.         if len(set(a['rel'].split()) & XFN_TAGS) > 0:  
  47.             tags = a['rel'].split()  
  48.             print a.contents[0], a['href'], tags  


传入一个URL(包含XFN)给这个脚本,它会返回名称,关系类型,以及指向其朋友的url,如下所示输出:

[python] view plaincopy
  1. Dion Almaer http://www.almaer.com/blog/ [u'me']  
  2. Ben Galbraith http://weblogs.java.net/blog/javaben/ [u'co-worker']  
  3. Rey Bango http://reybango.com/ [u'friend']  
  4. Michael Mahemoff http://softwareas.com/ [u'friend']  
  5. Chris Cornutt http://blog.phpdeveloper.org/ [u'friend']  
  6. Rob Sanheim http://www.robsanheim.com/ [u'friend']  
  7. Dietrich Kappe http://blogs.pathf.com/agileajax/ [u'friend']  
  8. Chris Heilmann http://wait-till-i.com/ [u'friend']  
  9. Brad Neuberg http://codinginparadise.org/about/ [u'friend']  

假如这些URL中包含XFN或其它有用的信息,我们可以直接跟踪这些链接,系统的建立更全的社交信息图谱。这种方法就是下一个示例要用到的:以宽度优先的方式的建立图谱,如示例2-3的伪代码所示。
示例2-3,深度优先的搜索的伪代码
[python] view plaincopy
  1. Create an empty graph  
  2. Create an empty queue to keep track of nodes that need to be processed  
  3.   
  4. Add the starting point to the graph as the root node  
  5. Add the root node to a queue for processing  
  6. Repeat until some maximum depth is reached or the queue is empty:  
  7.   Remove a node from the queue  
  8.   For each of the node's neighbors:  
  9.     If the neighbor hasn't already been processed:  
  10.       Add it to the queue  
  11.       Add it to the graph  
  12.       Create an edge in the graph that connects the node and its neighbor  

注意用这种方法创建的图会自动建立双向的边(如果这样的边存在的话),而不用任何的额外操作,以此来发现相互的朋友很有用。示例2-4是示例2-2的改进版本,它通过跟踪XFN中的超链接来建立NetworkX图。运行示例代码,即使仅为2的深度也能得到一张相当大的图,这取决于朋友网络中XFN的受欢迎程度。同时建立一张图片,观察它,并在它上面运行各种图的度量(见图2-1)。
示例2-4,用宽度优先搜索来抓取XFN链接(microformats_xfn_crawl.py)
[python] view plaincopy
  1. # -*- coding: utf-8 -*-  
  2.   
  3. import sys  
  4. import os  
  5. import urllib2  
  6. from BeautifulSoup import BeautifulSoup  
  7. import HTMLParser  
  8. import networkx as nx  
  9.   
  10. ROOT_URL = sys.argv[1]  
  11.   
  12. if len(sys.argv) > 2:  
  13.     MAX_DEPTH = int(sys.argv[2])  
  14. else:  
  15.     MAX_DEPTH = 1  
  16.   
  17. XFN_TAGS = set([  
  18.     'colleague',  
  19.     'sweetheart',  
  20.     'parent',  
  21.     'co-resident',  
  22.     'co-worker',  
  23.     'muse',  
  24.     'neighbor',  
  25.     'sibling',  
  26.     'kin',  
  27.     'child',  
  28.     'date',  
  29.     'spouse',  
  30.     'me',  
  31.     'acquaintance',  
  32.     'met',  
  33.     'crush',  
  34.     'contact',  
  35.     'friend',  
  36.     ])  
  37.   
  38. OUT = "graph.dot"  
  39.   
  40. depth = 0  
  41.   
  42. g = nx.DiGraph()  
  43.   
  44. next_queue = [ROOT_URL]  
  45.   
  46. while depth < MAX_DEPTH:  
  47.   
  48.     depth += 1  
  49.     (queue, next_queue) = (next_queue, [])  
  50.   
  51.     for item in queue:  
  52.         try:  
  53.             page = urllib2.urlopen(item)  
  54.         except urllib2.URLError:  
  55.             print 'Failed to fetch ' + item  
  56.             continue  
  57.   
  58.         try:  
  59.             soup = BeautifulSoup(page)  
  60.         except HTMLParser.HTMLParseError:  
  61.             print 'Failed to parse ' + item  
  62.             continue  
  63.   
  64.         anchorTags = soup.findAll('a')  
  65.   
  66.         if not g.has_node(item):  
  67.             g.add_node(item)  
  68.   
  69.         for a in anchorTags:  
  70.             if a.has_key('rel'):  
  71.                 if len(set(a['rel'].split()) & XFN_TAGS) > 0:  
  72.                     friend_url = a['href']  
  73.                     g.add_edge(item, friend_url)  
  74.                     g[item][friend_url]['label'] = a['rel'].encode('utf-8')  
  75.                     g.node[friend_url]['label'] = a.contents[0].encode('utf-8')  
  76.   
  77.                     next_queue.append(friend_url)  
  78.   
  79.         # Further analysis of the graph could be accomplished here  
  80.   
  81. if not os.path.isdir('out'):  
  82.     os.mkdir('out')  
  83.   
  84. try:  
  85.     nx.drawing.write_dot(g, os.path.join('out', OUT))  
  86. except ImportError, e:  
  87.   
  88.     # Help for Windows users:  
  89.     # Not a general purpose method, but representative of  
  90.     # the same output write_dot would provide for this graph  
  91.     # if installed and easy to implement  
  92.   
  93.     dot = []  
  94.     for (n1, n2) in g.edges():  
  95.         dot.append('"%s" [label="%s"]' % (n2, g.node[n2]['label']))  
  96.         dot.append('"%s" -> "%s" [label="%s"]' % (n1, n2, g[n1][n2]['label']))  
  97.   
  98.     f = open(os.path.join('out', OUT), 'w')  
  99.     f.write('''''strict digraph { 
  100.     %s 
  101.     }''' % (';\n'.join(dot), ))  
  102.     f.close()  
  103.   
  104. # *nix users could produce an image file with a good layout   
  105. # as follows from a terminal:  
  106. # $ circo -Tpng -Ograph graph.dot  
  107. # Windows users could use the same options with circo.exe   
  108. # or use the GVedit desktop application  





图2-1,Ajaxian网站XFN数据的双向图,注意在点“http://ajaxian.com/"和点"Dion Almaer"的边“Me"暗示Dion Almaer拥有这个博客。

尽管很简单,但这个图很有趣。它连接了八个点,以叫做“Dion Almaer"的人为中心点。如果再爬深一层或更多层,将在图中引入更多的结点来连接更多的人。单从这个图中,是不清楚Dion 和 Ben Galbraith 是否有更亲密的关系比起其他人来,因为"同事(Co-worker)"和"朋友(Friend)"关系的不同,但我们可以去爬取Ben的XFN数据,从中取得“同事”关系的数据,再爬取其同事的“同事”关系数据,从而建立一个谁和谁一起工作的社交网络。见第6章,挖掘同学和同事关系。


宽度优先技术的简要分析

我不想中断主题来花很长时间分析这项技术,但由于这个示例是本书的第一个严格意义上的算法,不是最后一个,因此有必要仔细去测验一下它。一般来说有两个标准去测验一个算法:效率和有效性,或者说,性能和质量。

一般的算法性能分析牵涉到它的最坏情况下时间和空间复杂度--换句话说就是,执行程序要发的时间,执行时占用的内存空间。我们采用的宽度优先方法在本质上是宽度优先搜索,虽然我们没有特别的去搜索什么,因为没有必要除了去扩展图到最大的深度或达到我们需要的结点。如果我们搜索一些特定的东西而不是只爬取链接,这就被认为是真正的宽度优先搜索。事实上,所有的搜索都有一些既定的标准,由于有限的资源的限制。因此宽度优先搜索的一种变异称作有边的宽度优先搜索,它引入了一个深度的限制,如我们所做的那样。

对于宽度优先搜索(或宽度优先爬取),时间和空间的复杂度在最坏情况是b^d,b是图中的分支因子,d是深度。如果你在纸上草拟一个示例,考虑一下它,这会很有意义。如果图中每个结点有5个邻居,你只想要1的深度,最终你将得到6个结点, 即根结点和它的五个邻居。如果所有的这五个邻居也有五个邻居,当你扩展到下一级时,就得到了总共31个结点,即根结点,根结点的五个邻居,以及根结点的每个邻居的五个邻居。这样的分析看起来很迂腐,但是在大数据的工程领域,能够利用已有的数据集做粗略的分析是更加重要了。表2-2提供了一概览关于b^d的增长

表2-2,图的结点数随着分支因子和深度增加而增加


前面的讨论主要是关于算法理论上的复杂度,而最终要参考的度量是算法在实践中给定数据集上的性能。对代码大概的分析发现它的主要是I/O影响了其性能,因为大部分时间发在了等待urlopen返回数据来处理。在后面的一个示例, “多线程会话” 介绍和示范了用一个线程池来改善性能,以增加少量的复杂度为代价。

在这个分析中最后一项要考虑的是结果的质量。从质量分析的观点来看,由虚拟的视图可以看出这实际上是一个连接人的图谱。任务完成了吗?是的,但总是有改善的空间的。有一点要考虑的就是,结果中URL的细小差别会在图中多个结点中出现,虽然它们指向相同的内容。例如,如果涉及到Matthew的链接有http://example.com/~Matthewhttp://www.example.com/~Matthew, 图谱中将出现两个不同的结点, 虽然它们可能指向相同的内容。幸运的是,XFN定义了一个rel="me"的特别值,来辨别可合并项。Google的社交图谱API就是用这种方法来连接用户的各种属性的,这里有许多的示例用rel="me"来允许用户在属性中添加外链。另外一问题(要小得多)就是URL的末尾是否有‘/’,大部分设计良好的网站会将一个转化为另一个,因此这就不成为问题了。

幸运的是,别人已经注意到了这个问题,并做了一些努力。SocialGraph Node Mapper(社交图谱结点映射)是一个有趣的开源项目,它可以标准化URL, 包括结尾的'/','www'是否出现等。它也可以辨别各种社交网站的不同URL指向同一个人, 如http://blog.example.com/Matthewhttp://status.example.com?user=Matthew指向同一个人在某个社交网站上。


地标:A Common Thread for Just About Anything(不知这句什么意思。。。)

认为像geo, hRecipe这样的微格式对社交数据挖掘没有用而忽略他们是一个大错误。虽然单独的geo数据是没有用的,但它是很得要的将完成不同的数据集以相同的地理坐标联系在一起。地标数据是无所不在的,它们在社交数据结合上发挥了很多作用,因为将空间中的位置作为一个线索可以来聚类人们到一起。真实生活和网上生活的距离就被进一步接近,并且任何的社交化数据都与现实中的个体相连。例如,它可能是相当可怕的,你可能知道一个人她在哪里住,她在家做什么食物,甚至这些菜谱是由什么组成的。这一节来过一些示例,查找,分析,可视化地理和菜单数据,很快你将想到要怎么用它们。


维基百科的文章 + 谷歌地图 = 路线图 ?

一个最简单的微格式去嵌入地理数据到网页中的是geo, 具体的表现是通过vCard(提供了一种方式来描述位置)的属性geo。有两种方式可以嵌入geo微格式, 示例2-5中的HTML小片段说明了以这两种技术来描述富兰克林--田纳西州最好的一个小镇。

示例2-5,简单的geo标注

[html] view plaincopy
  1. <!-- The multiple class approach -->  
  2. <span style="display: none" class="geo">  
  3. <span class="latitude">36.166</span>  
  4. <span class="longitude">-86.784</span>  
  5. </span>  
  6. <!-- When used as one class, the separator must be a semicolon -->  
  7. <span style="display: none" class="geo">36.166; -86.784</span>  
正如你所看到的,微格式简单的包装纬度和经度的值在标签中以相应的类名,把它们包在一个带有类名为geo的标签中。大量的著名网站--包括维基百科,Yahoo!Local, MapQuest Local, 以及许多其它的--用geo和其它的微格式在他们的网页上暴露结构化的数据。

示例2-6用一个简单的程序分析geo微格式从MapQuest Local页面,来展示如何从geo格式的内容中抽取坐标。

示例2-6从MapQuest Local中抽取geo数据(microformats__mapquest_geo.py)

[python] view plaincopy
  1. # -*- coding: utf-8 -*-  
  2.   
  3. import sys  
  4. import urllib2  
  5. from BeautifulSoup import BeautifulSoup  
  6. import HTMLParser  
  7.   
  8. # Pass in a URL such as http://local.mapquest.com/franklin-tn  
  9.   
  10. url = sys.argv[1]  
  11.   
  12. try:  
  13.     page = urllib2.urlopen(url)  
  14. except urllib2.URLError, e:  
  15.     print 'Failed to fetch ' + url  
  16.     raise e  
  17.     exit()  
  18.   
  19. try:  
  20.     soup = BeautifulSoup(page)  
  21. except HTMLParser.HTMLParseError:  
  22.     print 'Failed to parse ' + url  
  23.     exit()  
  24.   
  25. geoTag = soup.find(True'geo')  
  26.   
  27. if geoTag and len(geoTag) > 1:  
  28.     lat = geoTag.find(True'latitude').string  
  29.     lon = geoTag.find(True'longitude').string  
  30.     print 'Location is at', lat, lon  
  31. elif geoTag and len(geoTag) == 1:  
  32.     (lat, lon) = geoTag.string.split(';')  
  33.     (lat, lon) = (lat.strip(), lon.strip())  
  34.     print 'Location is at', lat, lon  
  35. else:  
  36.     print 'No location found'  


用微格式的实现是巧妙然而在某各程度上意义深远:当一个正在读一篇文章关于一个地方如富兰克林,直觉的知道在地图上的一点指示这个镇的位置,一个机器就不能如此容易的得出这样的判断了,除非有特殊逻辑来针对各种样式匹配。但这样的页面抽取是非常脏的建议,且当你想要将所有的可能性都搞定的时候,你会发现你还是漏了一个。嵌入语义到网页中来标注非结构化数据,能够使机器人也能很轻易的明白,它消除了歧义,并降低了爬虫开发者的门槛。它是一个双赢的局面对消费者和生产者来说都是,希望能在这方面有更多创新。


绘制geo数据通过microform.at 和 google地图

在你从网页中发现有趣的geo数据的那一刻,每一件想要做的事也许就是可视化它。例如,考虑“美国国家公园列表”的维基百科文章,它显示了一个漂亮的国家公园的表格视图,并以geo格式来标了它们,但是它是不是更漂亮,去快速的将它们装载到一个交互工具中作可视化的观察?很好,microform.at就是一个极好的小的网络服务,它从给定的URL中抽取各种类型的微格式,并返回各种有用的格式的数据。它提供了各种选项去判断和交互同网页上的微格式数据,如图2-2

图2-2, http://microform.at的结果对于维基百科的文章“美国国家公园列表“


如果有得选, KML(Keyhole Markup Language)输出是最易于可视化geo数据的。你可以下载Google Earth然后在本地加载KML文件,或者输入一个URL指向KML数据的到google地图搜索框中,无需其它操作即可建立它。在microform.at显示的结果中,点击"KML"触发一个文件下载,此文件可以在Google Earth 中使用, 你也可以右键复制这个链接给Google Maps。图2-3显示了Google Maps的虚拟视图对于http://microform.at/?type=geo&url=http%3A%2F%2Fen.wikipedia.org%2Fwiki%2FList_of_U.S._na
tional_parks--前面提到的维基百科文章的KML结果,也就是基本的url:http://microform.at和类型以及查询的url参数。

图2-3, Google Maps的结果显示所有美国的国家公园当传给它microform.at的KML数据

从包含语义标注(如geo数据)的维基百科文章中提取有用的数据,并可视化它, 这是一个很强大的分析能力,因为它可让我们很快洞悉重要的东西而只是做很少的工作。浏览器插件如Firefox Operator add-on 目标就是进一步降低这种劳动。在本节中只能讲这么多了,一个简洁的方法是发上一个小时左右的时间将本节中美国国家公园的数据同你的LinkedIn网络中联系人数据混合,从中你可能会发现怎么让下一次的出差更加有趣些。(见“从地理上了聚类你的网络“在第193页的例子,怎样通过使用k-means技术来查找类别并计算这些类别的中心点来获取和分析geo数据)


切分菜谱(为了健康)

由于google的富摘要信息的启动,将会有越来越多的微格式数据,许多的著名的美食网站做了很大的努力来暴露他们的菜单和评价通以hRecipe和hReview的形式。考虑这个潜在的可能性,一个虚拟的网上约会服务,它爬取博客和其它的社交网站,企图将配对人们去约会吃饭,某个人可能想要有权限查看特定的另一个的地理位置信息和菜单信息,这可能对增加第一次约会的成功机率有重大意义。人们能够被配对通过两个标准:一个人同另一个住的有多远;他们吃哪种类型的食物。例如,你可能会喜欢同肉食者约会吃饭而不是一个素食主义者。食物的偏好能够被用来增强商业创意。然而我们不会去创建一个新的网上数据服务,但我们想要激发你去创建它。

Food Network网站正完全的拥护以微格式来使整个网络更好,他暴露菜单信息以hRecipe并hReview格式来展现对菜单的评价。 这一节示范搜索引擎怎么从Food Network的菜单和评价中解析结构化数据以用来索引或分析。虽然我们不对菜单和评价中的纯文本数据作分析,或是持久的存储抽取的信息,后面的章节将会示范这些的如果你感兴趣的话。特别是,第3章介绍了CouchDB,一个很好的方法去存储和分享数据(和分析数据)--从包含微格式的网页中抽取的数据,第7章介绍一些基本的自然语言处理,你可以用来深入的分析评价数据。

示例2-6的一个改编版本来解析hRecipe格式的数据,如示例2-7.

示例2-7,从泰国菜中解析hRecipe数据(microformats__foodnetwork_hrecipe.py

[python] view plaincopy
  1. # -*- coding: utf-8 -*-  
  2.   
  3. import sys  
  4. import urllib2  
  5. import json  
  6. import HTMLParser  
  7. import BeautifulSoup  
  8.   
  9. # Pass in a URL such as  
  10. http://www.foodnetwork.com/recipes/alton-brown/pad-thai-recipe/index.html  
  11.   
  12. url = sys.argv[1]  
  13.   
  14. # Parse out some of the pertinent information for a recipe  
  15. # See http://microformats.org/wiki/hrecipe  
  16.   
  17.   
  18. def parse_hrecipe(url):  
  19.     try:  
  20.         page = urllib2.urlopen(url)  
  21.     except urllib2.URLError, e:  
  22.         print 'Failed to fetch ' + url  
  23.         raise e  
  24.   
  25.     try:  
  26.         soup = BeautifulSoup.BeautifulSoup(page)  
  27.     except HTMLParser.HTMLParseError, e:  
  28.         print 'Failed to parse ' + url  
  29.         raise e  
  30.   
  31.     hrecipe = soup.find(True'hrecipe')  
  32.   
  33.     if hrecipe and len(hrecipe) > 1:  
  34.         fn = hrecipe.find(True'fn').string  
  35.         author = hrecipe.find(True'author').find(text=True)  
  36.         ingredients = [i.string   
  37.                             for i in hrecipe.findAll(True'ingredient')   
  38.                                 if i.string is not None]  
  39.   
  40.         instructions = []  
  41.         for i in hrecipe.find(True'instructions'):  
  42.             if type(i) == BeautifulSoup.Tag:  
  43.                 s = ''.join(i.findAll(text=True)).strip()  
  44.             elif type(i) == BeautifulSoup.NavigableString:  
  45.                 s = i.string.strip()  
  46.             else:  
  47.                 continue  
  48.   
  49.             if s != '':   
  50.                 instructions += [s]  
  51.   
  52.         return {  
  53.             'name': fn,  
  54.             'author': author,  
  55.             'ingredients': ingredients,  
  56.             'instructions': instructions,  
  57.             }  
  58.     else:  
  59.         return {}  
  60.   
  61.   
  62. recipe = parse_hrecipe(url)  
  63. print json.dumps(recipe, indent=4)  



用一个示例URL,如Alton Brown’s acclaimed Pad Thai recipe(奥尔顿受欢迎的泰国菜),你应该会得到如示例2-8所示的结果。

示例2-8, 示例2-7中泰国菜的解析结果

[python] view plaincopy
  1. {  
  2. "instructions": [  
  3. "Place the tamarind paste in the boiling water and set aside ...",  
  4. "Combine the fish sauce, palm sugar, and rice wine vinegar in ...",  
  5. "Place the rice stick noodles in a mixing bowl and cover with ...",  
  6. "Press the tamarind paste through a fine mesh strainer and add ...",  
  7. "Place a wok over high heat. Once hot, add 1 tablespoon of the ...",  
  8. "If necessary, add some more peanut oil to the pan and heat until ..."  
  9. ],  
  10. "ingredients": [  
  11. "1-ounce tamarind paste",  
  12. "3/4 cup boiling water",  
  13. "2 tablespoons fish sauce",  
  14. "2 tablespoons palm sugar",  
  15. "1 tablespoon rice wine vinegar",  
  16. "4 ounces rice stick noodles",  
  17. "6 ounces Marinated Tofu, recipe follows",  
  18. "1 to 2 tablespoons peanut oil",  
  19. "1 cup chopped scallions, divided",  
  20. "2 teaspoons minced garlic",  
  21. "2 whole eggs, beaten",  
  22. "2 teaspoons salted cabbage",  
  23. "1 tablespoon dried shrimp",  
  24. "3 ounces bean sprouts, divided",  
  25. "1/2 cup roasted salted peanuts, chopped, divided",  
  26. "Freshly ground dried red chile peppers, to taste",  
  27. "1 lime, cut into wedges"  
  28. ],  
  29. "name""Pad Thai",  
  30. "author""Recipe courtesy Alton Brown, 2005"  
  31. }  
虽然它不是一种真实的社交数据分析形式,它是很有趣的去分析同一菜单的各种的参数来得到是否有联系在原料,评价,评分之间。例如,你可能想去攫取一个泰国菜谱来判断哪种原料是常用的哪种是不常用的。


收集餐馆的评价

这一节结束我们对微格式的研究。Yelp的一个很受欢迎的服务,它用到了hReview,因此顾客留下的关于餐馆的评价是被暴露的。示例2-9示范了怎么抽取hReview信息从Yelp网页中。一个示例URL在代码中,它代表了一个泰国餐馆如果你有机会去的话一定不想错过的。

示例2-9,从泰国菜单中解析hReview数据(microformats__yelp_hreview.py)

[python] view plaincopy
  1. # -*- coding: utf-8 -*-  
  2.   
  3. import sys  
  4. import re  
  5. import urllib2  
  6. import json  
  7. import HTMLParser  
  8. from BeautifulSoup import BeautifulSoup  
  9.   
  10. # Pass in a URL that contains hReview info such as  
  11. http://www.yelp.com/biz/bangkok-golden-fort-washington-2  
  12.   
  13. url = sys.argv[1]  
  14.   
  15. # Parse out some of the pertinent information for a Yelp review  
  16. # Unfortunately, the quality of hReview implementations varies  
  17. # widely so your mileage may vary. This code is *not* a spec  
  18. # parser by any stretch. See http://microformats.org/wiki/hreview  
  19.   
  20. def parse_hreviews(url):  
  21.     try:  
  22.         page = urllib2.urlopen(url)  
  23.     except urllib2.URLError, e:  
  24.         print 'Failed to fetch ' + url  
  25.         raise e  
  26.   
  27.     try:  
  28.         soup = BeautifulSoup(page)  
  29.     except HTMLParser.HTMLParseError, e:  
  30.         print 'Failed to parse ' + url  
  31.         raise e  
  32.   
  33.     hreviews = soup.findAll(True'hreview')  
  34.   
  35.     all_hreviews = []  
  36.     for hreview in hreviews:  
  37.         if hreview and len(hreview) > 1:  
  38.   
  39.             # As of 1 Jan 2010, Yelp does not implement reviewer as an hCard,   
  40.             # per the spec  
  41.   
  42.             reviewer = hreview.find(True'reviewer').text    
  43.   
  44.             dtreviewed = hreview.find(True'dtreviewed').text  
  45.             rating = hreview.find(True'rating').find(True'value-title')['title']  
  46.             description = hreview.find(True'description').text  
  47.             item = hreview.find(True'item').text  
  48.   
  49.             all_hreviews.append({  
  50.                 'reviewer': reviewer,  
  51.                 'dtreviewed': dtreviewed,  
  52.                 'rating': rating,  
  53.                 'description': description,  
  54.                 })  
  55.     return all_hreviews  
  56.   
  57. reviews = parse_hreviews(url)  
  58.   
  59. # Do something interesting like plot out reviews over time  
  60. # or mine the text in the descriptions...  
  61.   
  62. print json.dumps(reviews, indent=4)  



截取的结果数据如示例2-10,它包括点评者,从hCard微格式结点中解析出来的。

示例2-10, 示例2-9的部分结果

[python] view plaincopy
  1. [  
  2. {  
  3. },  
  4. "reviewer""Nick L.",  
  5. "description""Probably the best Thai food in the metro area...",  
  6. "dtreviewed""4/27/2009",  
  7. "rating""5"  
  8. ...truncated...  
  9. ]  
不幸的是,Yelp, Food Network和其它的网站都没有提供详细的信息将点评者归到一起,但是,很有希望很快会改变,打开社交网站的额外可能性。你可能做的最多的是算餐馆的平均得分随时间的变化,从而看其是上升了还是下降了。另外一个主意就是挖掘在文本中的描述,见第7章和第8章,看是怎么做的。

有无限的创新会发生,当你将极客和食物组合在一起,Cooking for Geeks这本书受欢迎就是个明证,也是O’Reilly出版的。随着美食网站改进并增加他们的API, 我们将在该领域有更多的创新。


总结

如果你无法记住本章中其它的东西,请记住微格式是一种方法来包装标注以暴露各种结构化数据,如菜单,联系人信息,人与人之间的关系。微格式有巨大的潜力因为它允许我们用已有的内容使得数据显式的且合适的达到预定的目标。期待到微格式在未来几个月中重大的增长。你也会吃惊于基于HTML5 microdata的创新随着HTML5市场份额的增加。如果你发现自己还有空余的时间,请看一下Google's social graph API, 它不同于Facebook的RDFa-based Open Graph protocol ,或是第9章中的Graph API,它包含XFN, FOAF和其它公开声明的联系的索引。