網(wǎng)絡環(huán)境下的大規(guī)模內(nèi)容計算-PowerPointPre

網(wǎng)絡環(huán)境下的大規(guī)模內(nèi)容計算------

WebSearchandWebMining程學旗，cxq@中國科學院計算技術研究所06.8.17SWCL2006沈陽OutlineBackgroundandMotivationSomeofexistingworksinICTSomeofexistingresearchworksSomeofsharingsystemsConclusionABigProblem!NaturalLanguageSemanticWebInformationWebComputingMachineLearningNetworkSocial拋開爭論看Web搜索的發(fā)展UnifiedBrowsingUnifiedSearchPersonalizedSearchPersonalizedSpaceWebMining：海量信息空間內(nèi)的知識發(fā)現(xiàn)對象：大規(guī)模復雜網(wǎng)絡信息網(wǎng)頁達到100億；每天PB規(guī)模的郵件流量；10多億以上的即時通信用戶，同時在線數(shù)億用戶；每年近3000億條的手機短信，每天平均近10億條目的：準確、及時有效地知識發(fā)現(xiàn)商業(yè)情報智能：非完整信息下的確定性判定垃圾信息的過濾：貓與老鼠的游戲金融證券信息的監(jiān)管：反恐、網(wǎng)絡犯罪的發(fā)現(xiàn)挑戰(zhàn)：發(fā)現(xiàn)難！如何找到最想要的信息，而不是一堆垃圾如何發(fā)現(xiàn)和跟蹤最有價值的線索？如何實時響應數(shù)據(jù)流？如何發(fā)現(xiàn)異常？“Web2.0”：熱鬧背后有什么？行為模式的變化Architecture:Fromserver-centeredtoPeer-distributed互動參與：P2P,Blog狀態(tài)特征的變化Streaming:FromINFORMATIONtoMESSAGESocialization:內(nèi)容表征的變化：RichContent多源頭、大規(guī)模RichDimensionsMotivation:

“問題還是那個問題，目標不再是那個目標”模型表示與特征獲取：“單一的特征空間既不是完備的，又不是正交的”AssumptionsofVSM,PM,LMetcHowtorepresenttheRichdimensionalfeaturespaces?可計算性：“統(tǒng)一性排名不是大多數(shù)需求，個性化才是大多數(shù)”UnifiedRANKINGhassomanybiases！Identityvs.Otherness(Active-computing)SpecialalgorithmsforRich-dimensionalfeaturespaceStreamingMessagevs.Text/Sentence；Dynamic“context”sensitiveTradeoffbetweendeepunderstandingandperformanceShadowandefficientlanguageprocessingOutlineBackgroundandMotivationSomeofexistingworksinICTSomeofexistingresearchworksSomeofsharingsystemsConclusionOrganizationsofICTDoIS前瞻中心網(wǎng)絡與普適計算系統(tǒng)結構智能軟件BioinformaticsIntelligentInformationProcessingGridandServiceComputingInformation

Intelligence&infosecurityIR、WebMining、ShadowLanguageProcessing、DataStringmanagement、P2PcomputingNetworkSecurity、DRMandTrustComputingICTI3SAbout80personsinI3SAbout25researchfacultyMorethan40studentsOver20Ph.dcandidates，over15mastercandidatesRelatedworksinI3S@ICTResearchtopics大規(guī)模文本分析與網(wǎng)絡挖掘：Dr.許洪波等確定性（淺層）自然語言處理：Dr.張華平等網(wǎng)絡搜索：Dr.王斌、張剛etc大規(guī)模特征匹配、數(shù)據(jù)流挖掘：Dr.譚建龍等網(wǎng)絡結構挖掘與社會計算：Dr.陳海強等P2P計算：Dr.呂建明等SharableSystems中文分詞與詞法分析軟件：ICTCLAS高性能全文索引與檢索平臺：FirteXDataStreamManagementConditions:Highspeedstreaming(Over10GBps)LargeScalequeries (Over100,000)EmergenceoftemporalunknownpatternsRequirementOnlinerespondingEmergencepredictionChallenges數(shù)據(jù)流QueryProcessingMultiplefilteringqueriesprocessingonsinglestreamJoinalgorithmsonmultiplestreamsDataStreamminingFrequentpatternsdiscoveryClusteringEmergenceprediction…Whatwearepursuing數(shù)據(jù)流MultipleStringsMatchingClassicAlgorithms:Prefix-basedapproach:KMP,AC,Shift-And,Shift-OrSuffix-basedapproach:Boyer-Moore,Wu-ManberFactor-basedapproach:SBDM,SBOMChallengeThenumberoffeaturestringsincreasewiththerapidgrowofinformationscale.(ClamAntiViruslibrary:26653)TraditionalStringmatchingalgorithmcannotsolvetheproblemwhilethefeaturenumberisover5000.國家主干網(wǎng)的網(wǎng)絡流量增長圖串匹配算法速度隨特征串數(shù)量的變化圖改進算法時間復雜度優(yōu)化算法的數(shù)據(jù)結構問題的核心：時間優(yōu)化與空間優(yōu)化數(shù)據(jù)流Partition:CombinatorialOptimizationMatching(ICT-COM)FindtheoptimalpartitionFindtheshortestpathinaweightedgraphEdge:asetofblockswithlengthgreaterthanorequalwithi,butlessthanjWeight:theminimaltimeoftheclassicalalgorithmstosearchinatrainingtextforthekeywordsinthecorrespondingsubsetObjective:findtheshortestpathfromsourcetosinkinGsourcesinkConstructaweightedgraphGaccordingtothegivenkeywordssetPasfollowsNode:eachablockwithlengthiinP數(shù)據(jù)流OptimizationAnalysis4subsetsweregivenbyCOMandassignedwithdifferentalgorithms. 3-9(AC)，10-13(SBOM)，14-35(SBOM)，36-210(SBOM)ThespeedofCOMisabout3timesfasterthanthequickestclassicalone.ICT-COMisanefficientlarge-scalestringmatchingalgorithm.

ResultsofICT-COMLIUPing,etc,APartition-BasedEfficientAlgorithmforLargeScaleMultiple-StringsMatching,IEEESPIRE2005數(shù)據(jù)流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文本分析現(xiàn)象一套集中式的計算方法為所有類型的用戶提供服務往往是眾口難調。Google等檢索的前提同樣的輸入總有一個最符合“大多數(shù)”人群需求的結果集。遺憾的是，網(wǎng)絡中，“少數(shù)人的需求”才是真正的大多數(shù)網(wǎng)絡信息的實時性、動態(tài)性、多樣性和巨大規(guī)模只能使得集中式檢索放棄傳統(tǒng)查全率概念，與此同時仍然避免不了大量的垃圾。原因分析一方面是知識不完全、計算不完備情況下的集中、近似計算另一方面是存在大規(guī)模個性差異的信息需求二者的本身是“不匹配”的直觀求解人人平等：每個人都是需求方也都是提供方，沒有傳統(tǒng)意義上的獨立服務器各人自掃門前雪：我只關注我想要的東西和我能提供的東西人人為我，我為人人：遵循最基本的原則，包括內(nèi)容路由規(guī)則、SWEffect,PL等P2PIRWhyP2P?P2P計算與構造個性化信息空間的初步設想內(nèi)容表示的個性化：每一個節(jié)點有權選擇自身的內(nèi)容呈現(xiàn)方式，提供“最準確”的自身需求計算的個性化：內(nèi)容的發(fā)現(xiàn)與提供方式由節(jié)點之間自行協(xié)商。可以在多個計算引擎之間選擇最優(yōu)的策略。遵循一定的框架與屬性規(guī)范信息定位綜合為對拓撲結構、屬性、內(nèi)容特征、行為特征的判定問題數(shù)據(jù)驅動、動態(tài)計算引擎、對等協(xié)同是否可以解決數(shù)據(jù)稀疏和個性化內(nèi)容關聯(lián)等問題？是否能夠構造動態(tài)自適應的網(wǎng)絡內(nèi)容社區(qū)，同時保證Scalability?P2PIRWonGoo:基于P2P的內(nèi)容關聯(lián)平臺基于ＣＡＮ的M維笛卡爾空間編碼采用增量化的特征空間壓縮與轉化策略（質心表示）對等節(jié)點之間鄰接距離與語義距離之間保序（任意兩點之間的連接度與兩點之間的語義距離相對相關）節(jié)點規(guī)模對召回率的影響文檔規(guī)模對召回率的影響P2PIRJianmingLvetc,WonGoo:APurePeer-to-PeerFullTextInformationRetrievalSystemBasedOnSemanticOverlayNetworks,IEEENCA2004WonGoo@WAX：ResearcherNetworkWAXWAXWAXWAXWAXWAXWAXWAXWAXWAXWAXWAXWAXWAXP2PIRCommunityIdentification

CurrentcommunityidentificationLinkdensitycommunityKleinbergetc,Science294(2001)EdgedensitycommunityPallaetc,natural(2005)WebMiningOutlineBackgroundandMotivationSomeofexistingworksinICTSomeofexistingresearchworksSomeofsharingsystemsConclusion共享系統(tǒng)與算法工具包提供開源系統(tǒng)的目的：共同促進大規(guī)模內(nèi)容計算領域科研水平整體發(fā)展為廣大科研人員，尤其是學生，提供免費的研究學習環(huán)境和良好的科研工具，減少大家的重復勞動與同行交流切磋，優(yōu)化系統(tǒng)計劃提供的共享系統(tǒng)、工具分詞與詞法分析系統(tǒng)：ICTCLAS（已經(jīng)全部實現(xiàn)源碼共享）全文索引與檢索平臺：FirteX（部分實現(xiàn)源碼共享）分類／聚類算法庫：ICTDRAP（即將實現(xiàn)部分源碼共享）數(shù)據(jù)流處理平臺：IceStream（執(zhí)行碼共享）定位１：小規(guī)模的直接用戶（無須編程，快速搭建全文檢索系統(tǒng)）直接提供了多種文件格式解析器(HTML,PDF,WORD等)；采用類似于XML格式的配置文件，可以根據(jù)數(shù)據(jù)集和機器配置情況，靈活配置整個系統(tǒng)。

定位２：科研人員（提供信息檢索與文本分析算法研究環(huán)境）提供了TREC文檔集解析器；檢索模型易于擴展；提供了3種前向索引方式，可以直接用來做文本分類、聚類，摘要等實驗；定位３：二次開發(fā)者（提供可擴展的檢索系統(tǒng)架構和高性能實現(xiàn)算法）系統(tǒng)各組成部分耦合性低，從應用層模塊到系統(tǒng)核心層模塊，均可單獨修改、升級或替換；擴展既可以在源代碼上直接進行，也可以使用非C/C++語言通過COM組件擴展FirteX------

開源的高性能全文索引與檢索平臺ApplicationIndexAccessComponentIndexReaderAnalyzerIndexSearcherIndexComponentWordIndexerURLIndexerOtherUserIndexerStorageComponentDiskStorageRAMStorageClusterStorageIndexWriterParserCollectioninterfaceimplementationPluggableExtensibleBuild-inFirteX架構InvertedIndexFilesbarrelbarrelbarrelbarrelbarrelbarrelbarrelbarrelbarrelbarrelbarrelbarrelStorageLayerIndexer/Searcher…IndexerEmailIndexerTermIndexerMemCache…SearcherEmailSearcherTermSearcherAnalyzerLayer….EnglishAnalyzerChineseAnalyzerJapaneseAnalyzerKoreanAnalyzerParserLayerMP3ParserEmailParserAVIParser…….HTMLParserPDFParserWORDParserPPTParserXMLParserApplicationLayerForumSearchEngine….DigitalLibraryExperimentFirteX的功能對比NOTE:表中有關Lucene和Lemur的所有數(shù)據(jù)都是從相應系統(tǒng)的官方網(wǎng)站獲取的.

Lucene2.00Lemur4.32FirteX1.02InvFPIndexIndriKeyfile索引增量索引是+是是+多字段支持是否是是是前向索引(詞向量)是+是-是+多種文檔集支持否是是+處理Tb級數(shù)據(jù)否是是索引速度1x3x9x多文檔格式解析支持是是是多文檔內(nèi)容分析支持是是是中文支持是是是+檢索檢索語言豐富+豐富豐富+豐富豐富檢索模型可擴展是是是索引全裝入內(nèi)存檢索是否是索引的同時檢索是否是其他COM插件支持否否是XML配置系統(tǒng)否是是+程序運行記錄否否是FirteX性能測試－索引corpus1Corpus2corpus4corpus8Corpus11索引內(nèi)存(M)1024索引合并因子10停用詞(中/英文)(個)961CPU平均占用率49%原始數(shù)據(jù)大小(G)1.02.04.08.011.5物理文件數(shù)(個)12485文檔總數(shù)(個)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測試環(huán)境:Windows2000AdvanceServer,P42.8G(2CPU),2GRAM,共5個純文本數(shù)據(jù)集,從北大天網(wǎng)CWT100G中文網(wǎng)頁語料中提取，文件大小5k~30kFirteX性能測試－檢索Corpus1Corpus2corpus4corpus8corpus11檢索使用內(nèi)存峰值(M)16.6116.0714.8517.017.4索引大小(G)0.490.981.973.975.80測試查詢總數(shù)109641查詢詞平均長度(字)2.5命中結果數(shù)(個)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注:檢索是在索引優(yōu)化合并后進行，僅檢索詞典收錄詞FirteX的特點及進一步工作ICTCLAS:ChineseLexicalAnalysisArchitectureofICTCLASCorpusCharacterStringW