网络环境下的大规模内容计算-PowerPointPre

网络环境下的大规模内容计算------

WebSearchandWebMining程学旗，cxq@中国科学院计算技术研究所06.8.17SWCL2006沈阳OutlineBackgroundandMotivationSomeofexistingworksinICTSomeofexistingresearchworksSomeofsharingsystemsConclusionABigProblem!NaturalLanguageSemanticWebInformationWebComputingMachineLearningNetworkSocial抛开争论看Web搜索的发展UnifiedBrowsingUnifiedSearchPersonalizedSearchPersonalizedSpaceWebMining：海量信息空间内的知识发现对象：大规模复杂网络信息网页达到100亿；每天PB规模的邮件流量；10多亿以上的即时通信用户，同时在线数亿用户；每年近3000亿条的手机短信，每天平均近10亿条目的：准确、及时有效地知识发现商业情报智能：非完整信息下的确定性判定垃圾信息的过滤：猫与老鼠的游戏金融证券信息的监管：反恐、网络犯罪的发现挑战：发现难！如何找到最想要的信息，而不是一堆垃圾如何发现和跟踪最有价值的线索？如何实时响应数据流？如何发现异常？“Web2.0”：热闹背后有什么？行为模式的变化Architecture:Fromserver-centeredtoPeer-distributed互动参与：P2P,Blog状态特征的变化Streaming:FromINFORMATIONtoMESSAGESocialization:内容表征的变化：RichContent多源头、大规模RichDimensionsMotivation:

“问题还是那个问题，目标不再是那个目标”模型表示与特征获取：“单一的特征空间既不是完备的，又不是正交的”AssumptionsofVSM,PM,LMetcHowtorepresenttheRichdimensionalfeaturespaces?可计算性：“统一性排名不是大多数需求，个性化才是大多数”UnifiedRANKINGhassomanybiases！Identityvs.Otherness(Active-computing)SpecialalgorithmsforRich-dimensionalfeaturespaceStreamingMessagevs.Text/Sentence；Dynamic“context”sensitiveTradeoffbetweendeepunderstandingandperformanceShadowandefficientlanguageprocessingOutlineBackgroundandMotivationSomeofexistingworksinICTSomeofexistingresearchworksSomeofsharingsystemsConclusionOrganizationsofICTDoIS前瞻中心网络与普适计算系统结构智能软件BioinformaticsIntelligentInformationProcessingGridandServiceComputingInformation

Intelligence&infosecurityIR、WebMining、ShadowLanguageProcessing、DataStringmanagement、P2PcomputingNetworkSecurity、DRMandTrustComputingICTI3SAbout80personsinI3SAbout25researchfacultyMorethan40studentsOver20Ph.dcandidates，over15mastercandidatesRelatedworksinI3S@ICTResearchtopics大规模文本分析与网络挖掘：Dr.许洪波等确定性（浅层）自然语言处理：Dr.张华平等网络搜索：Dr.王斌、张刚etc大规模特征匹配、数据流挖掘：Dr.谭建龙等网络结构挖掘与社会计算：Dr.陈海强等P2P计算：Dr.吕建明等SharableSystems中文分词与词法分析软件：ICTCLAS高性能全文索引与检索平台：FirteXDataStreamManagementConditions:Highspeedstreaming(Over10GBps)LargeScalequeries (Over100,000)EmergenceoftemporalunknownpatternsRequirementOnlinerespondingEmergencepredictionChallenges数据流QueryProcessingMultiplefilteringqueriesprocessingonsinglestreamJoinalgorithmsonmultiplestreamsDataStreamminingFrequentpatternsdiscoveryClusteringEmergenceprediction…Whatwearepursuing数据流MultipleStringsMatchingClassicAlgorithms:Prefix-basedapproach:KMP,AC,Shift-And,Shift-OrSuffix-basedapproach:Boyer-Moore,Wu-ManberFactor-basedapproach:SBDM,SBOMChallengeThenumberoffeaturestringsincreasewiththerapidgrowofinformationscale.(ClamAntiViruslibrary:26653)TraditionalStringmatchingalgorithmcannotsolvetheproblemwhilethefeaturenumberisover5000.国家主干网的网络流量增长图串匹配算法速度随特征串数量的变化图改进算法时间复杂度优化算法的数据结构问题的核心：时间优化与空间优化数据流Partition:CombinatorialOptimizationMatching(ICT-COM)FindtheoptimalpartitionFindtheshortestpathinaweightedgraphEdge:asetofblockswithlengthgreaterthanorequalwithi,butlessthanjWeight:theminimaltimeoftheclassicalalgorithmstosearchinatrainingtextforthekeywordsinthecorrespondingsubsetObjective:findtheshortestpathfromsourcetosinkinGsourcesinkConstructaweightedgraphGaccordingtothegivenkeywordssetPasfollowsNode:eachablockwithlengthiinP数据流OptimizationAnalysis4subsetsweregivenbyCOMandassignedwithdifferentalgorithms. 3-9(AC)，10-13(SBOM)，14-35(SBOM)，36-210(SBOM)ThespeedofCOMisabout3timesfasterthanthequickestclassicalone.ICT-COMisanefficientlarge-scalestringmatchingalgorithm.

ResultsofICT-COMLIUPing,etc,APartition-BasedEfficientAlgorithmforLargeScaleMultiple-StringsMatching,IEEESPIRE2005数据流LexicalProcessingDifficultiesinChineselexicalanalysisSegmentationOverlappedambiguitiesCombinationambiguitiesUnknownwordsrecognitionNamedentities:PER,LOC,ORG,etc.NewwordsPOStagging语言处理HHMMArchitectureinICTCLASIIIHHMMArchitecture:

TraceStringAtomSegmentationNSP-basedroughsegmentation5thHMMAtomsequenceTopnsequence

WordssequenceLexicalresults

POSsequenceSimpleunknownwordsrecognitionPERLOCWordgraph4thHMMComplexunknownwordsrecognition3rdHMMClass-basedfinalsegmentation2thHMMRevisedNresultsLOCORG1thHMMPOSTaggingHHMM-basedChineselexicalanalysis语言处理Class-basedsegmentationci=wiiffwiislistedinthesegmentationlexicon;PER,LOC,ORG,TIMEorNUMiffwiisanunknownnamedentity;STRiffwiisanunknownsymbolstring;BEGiffbeginningofasentenceENDiffendingofasentenceOTHERotherwise.WordclassdefinitionClass-basedsegmentationmodel语言处理Role-basedUnknownwordrecognitionUnknownwordsrecognition:role-basedHMM毛/Surname泽/Mid_name东/last_name1893年/context诞生/remote_contextProbabilityP(Wi|Ci)ofrecognizedunknownwordscouldbeestimatedinrole-basedHMMHuapingZhangetc,ChineseNamedEntityRecognitionUsingRoleModel,InternationalJournalofComputationalLinguisticsandChineseLanguageProcessing,2003,Vol.8(2)语言处理ChineseNewWordIdentificationUnknownwordsornewwordsblastwiththedevelopmentofWebsize.非典、超女、售奶亭、法杰港、荷赛奖、竖冰、招聘季…Weexploredcharactercoupling,single-characterwordprobability,Positioninformationwithidentifyingnewwords.语言处理ChineseNewWordIdentificationCharacterCoupling字对N1N2Coup（cicj）好看52500.9615德昂881否具1000才基3010.0323化气31180.5806所思188

0.4444语言处理RecognitionSample未切分句子初切分结果碎片未登录词小洋房以西百十来米，丰镐房和玉泰盐铺相邻而立小/洋房/以西/百十/来/米/，丰/镐/房/和/玉/泰/盐/铺/相邻./而/立来米丰镐房和玉泰盐铺而立丰镐房玉泰盐铺尽管她已过而立之年尽管/她/已/过/而/立/之/年她已过而立之年而立之年阿维兰热走上前阿/维/兰/热/走/上/前阿维兰热走上前阿维兰热主任庞廷清听完解救小组的情况反映主任/庞/廷/清/听/完/解救/小组/的/情况/反映庞廷清听完庞廷清语言处理UnpublishedTextMiningSupervisedLearning:ClassificationUnsupervisedLearning:ClusteringNewFeatureDetection文本分析Fromtheviewofgranularity,clusteringisaprocedureinauniformgranularity,whileclassificationindifferentgranularities.illustration:B12345AabcABacb

12345TextClassification(1)

InformationGranularitybasedclassification文本分析图（4-11c）开放测试的准确率——粒度原理法-.-.-.-类中心法——粒度原理法-.-.-.-类中心法Average↑5%文本分析DragPushingasarefinementstrategytoenhancetheperformanceofthelatterhigh-speedtextclassifiers,suchasCBorRocchio.Themainmotivationbehindthisstrategyisthehypothesisthattherestillexistsroomforperformanceimprovementbecausethelearningalgorithmitselfmayhaveinductivebias,orthetextcollectionmaymisfitthelearningmodeltosomedegree.TextClassification(2)

DragPushing:ARefinementStrategyforTextClassifier文本分析DragPushing文本分析训练与分类时间：与Centroid相当Dragpushing准确性：与SVM相当SongboTanetc,ANovelRefinementApproachforTextCategorization,ACMSIGIR2005,ACMCIKM2005etc文本分析现象一套集中式的计算方法为所有类型的用户提供服务往往是众口难调。Google等检索的前提同样的输入总有一个最符合“大多数”人群需求的结果集。遗憾的是，网络中，“少数人的需求”才是真正的大多数网络信息的实时性、动态性、多样性和巨大规模只能使得集中式检索放弃传统查全率概念，与此同时仍然避免不了大量的垃圾。原因分析一方面是知识不完全、计算不完备情况下的集中、近似计算另一方面是存在大规模个性差异的信息需求二者的本身是“不匹配”的直观求解人人平等：每个人都是需求方也都是提供方，没有传统意义上的独立服务器各人自扫门前雪：我只关注我想要的东西和我能提供的东西人人为我，我为人人：遵循最基本的原则，包括内容路由规则、SWEffect,PL等P2PIRWhyP2P?P2P计算与构造个性化信息空间的初步设想内容表示的个性化：每一个节点有权选择自身的内容呈现方式，提供“最准确”的自身需求计算的个性化：内容的发现与提供方式由节点之间自行协商。可以在多个计算引擎之间选择最优的策略。遵循一定的框架与属性规范信息定位综合为对拓扑结构、属性、内容特征、行为特征的判定问题数据驱动、动态计算引擎、对等协同是否可以解决数据稀疏和个性化内容关联等问题？是否能够构造动态自适应的网络内容社区，同时保证Scalability?P2PIRWonGoo:基于P2P的内容关联平台基于ＣＡＮ的M维笛卡尔空间编码采用增量化的特征空间压缩与转化策略（质心表示）对等节点之间邻接距离与语义距离之间保序（任意两点之间的连接度与两点之间的语义距离相对相关）节点规模对召回率的影响文档规模对召回率的影响P2PIRJianmingLvetc,WonGoo:APurePeer-to-PeerFullTextInformationRetrievalSystemBasedOnSemanticOverlayNetworks,IEEENCA2004WonGoo@WAX：ResearcherNetworkWAXWAXWAXWAXWAXWAXWAXWAXWAXWAXWAXWAXWAXWAXP2PIRCommunityIdentification

CurrentcommunityidentificationLinkdensitycommunityKleinbergetc,Science294(2001)EdgedensitycommunityPallaetc,natural(2005)WebMiningOutlineBackgroundandMotivationSomeofexistingworksinICTSomeofexistingresearchworksSomeofsharingsystemsConclusion共享系统与算法工具包提供开源系统的目的：共同促进大规模内容计算领域科研水平整体发展为广大科研人员，尤其是学生，提供免费的研究学习环境和良好的科研工具，减少大家的重复劳动与同行交流切磋，优化系统计划提供的共享系统、工具分词与词法分析系统：ICTCLAS（已经全部实现源码共享）全文索引与检索平台：FirteX（部分实现源码共享）分类／聚类算法库：ICTDRAP（即将实现部分源码共享）数据流处理平台：IceStream（执行码共享）定位１：小规模的直接用户（无须编程，快速搭建全文检索系统）直接提供了多种文件格式解析器(HTML,PDF,WORD等)；采用类似于XML格式的配置文件，可以根据数据集和机器配置情况，灵活配置整个系统。

定位２：科研人员（提供信息检索与文本分析算法研究环境）提供了TREC文档集解析器；检索模型易于扩展；提供了3种前向索引方式，可以直接用来做文本分类、聚类，摘要等实验；定位３：二次开发者（提供可扩展的检索系统架构和高性能实现算法）系统各组成部分耦合性低，从应用层模块到系统核心层模块，均可单独修改、升级或替换；扩展既可以在源代码上直接进行，也可以使用非C/C++语言通过COM组件扩展FirteX------

开源的高性能全文索引与检索平台ApplicationIndexAccessComponentIndexReaderAnalyzerIndexSearcherIndexComponentWordIndexerURLIndexerOtherUserIndexerStorageComponentDiskStorageRAMStorageClusterStorageIndexWriterParserCollectioninterfaceimplementationPluggableExtensibleBuild-inFirteX架构InvertedIndexFilesbarrelbarrelbarrelbarrelbarrelbarrelbarrelbarrelbarrelbarrelbarrelbarrelStorageLayerIndexer/Searcher…IndexerEmailIndexerTermIndexerMemCache…SearcherEmailSearcherTermSearcherAnalyzerLayer….EnglishAnalyzerChineseAnalyzerJapaneseAnalyzerKoreanAnalyzerParserLayerMP3ParserEmailParserAVIParser…….HTMLParserPDFParserWORDParserPPTParserXMLParserApplicationLayerForumSearchEngine….DigitalLibraryExperimentFirteX的功能对比NOTE:表中有关Lucene和Lemur的所有数据都是从相应系统的官方网站获取的.

Lucene2.00Lemur4.32FirteX1.02InvFPIndexIndriKeyfile索引增量索引是+是是+多字段支持是否是是是前向索引(词向量)是+是-是+多种文档集支持否是是+处理Tb级数据否是是索引速度1x3x9x多文档格式解析支持是是是多文档内容分析支持是是是中文支持是是是+检索检索语言丰富+丰富丰富+丰富丰富检索模型可扩展是是是索引全装入内存检索是否是索引的同时检索是否是其他COM插件支持否否是XML配置系统否是是+程序运行记录否否是FirteX性能测试－索引corpus1Corpus2corpus4corpus8Corpus11索引内存(M)1024索引合并因子10停用词(中/英文)(个)961CPU平均占用率49%原始数据大小(G)1.02.04.08.011.5物理文件数(个)12485文档总数(个)60183120367240792482319699247索引大小(G)0.49(510M)0.99G1.973.995.82总时间(s)247.11573.151277.342603.333150.74平均时间(M/min)248.4214.2193.2189.0224.4测试环境:Windows2000AdvanceServer,P42.8G(2CPU),2GRAM,共5个纯文本数据集,从北大天网CWT100G中文网页语料中提取，文件大小5k~30kFirteX性能测试－检索Corpus1Corpus2corpus4corpus8corpus11检索使用内存峰值(M)16.6116.0714.8517.017.4索引大小(G)0.490.981.973.975.80测试查询总数109641查询词平均长度(字)2.5命中结果数(个)71,345,331140,474,915280,155,094570,921,066838,464,138总时间(s)75.4280.234109.063171.28264.45平均时间(ms/q)0.690.730.991.562.41注:检索是在索引优化合并后进行，仅检索词典收录词FirteX的特点及进一步工作ICTCLAS:ChineseLexicalAnalysisArchitectureofICTCLASCorpusCharacterStringW