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

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

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

“問題還是那個(gè)問題，目標(biāo)不再是那個(gè)目標(biāo)”模型表示與特征獲?。骸皢我坏奶卣骺臻g既不是完備的，又不是正交的”AssumptionsofVSM,PM,LMetcHowtorepresenttheRichdimensionalfeaturespaces?可計(jì)算性：“統(tǒng)一性排名不是大多數(shù)需求，個(gè)性化才是大多數(shù)”UnifiedRANKINGhassomanybiases！Identityvs.Otherness(Active-computing)SpecialalgorithmsforRich-dimensionalfeaturespaceStreamingMessagevs.Text/Sentence；Dynamic“context”sensitiveTradeoffbetweendeepunderstandingandperformanceShadowandefficientlanguageprocessingOutlineBackgroundandMotivationSomeofexistingworksinICTSomeofexistingresearchworksSomeofsharingsystemsConclusionOrganizationsofICTDoIS前瞻中心網(wǎng)絡(luò)與普適計(jì)算系統(tǒng)結(jié)構(gòu)智能軟件BioinformaticsIntelligentInformationProcessingGridandServiceComputingInformation

Intelligence&infosecurityIR、WebMining、ShadowLanguageProcessing、DataStringmanagement、P2PcomputingNetworkSecurity、DRMandTrustComputingICTI3SAbout80personsinI3SAbout25researchfacultyMorethan40studentsOver20Ph.dcandidates，over15mastercandidatesRelatedworksinI3S@ICTResearchtopics大規(guī)模文本分析與網(wǎng)絡(luò)挖掘：Dr.許洪波等確定性（淺層）自然語(yǔ)言處理：Dr.張華平等網(wǎng)絡(luò)搜索：Dr.王斌、張剛etc大規(guī)模特征匹配、數(shù)據(jù)流挖掘：Dr.譚建龍等網(wǎng)絡(luò)結(jié)構(gòu)挖掘與社會(huì)計(jì)算：Dr.陳海強(qiáng)等P2P計(jì)算：Dr.呂建明等SharableSystems中文分詞與詞法分析軟件：ICTCLAS高性能全文索引與檢索平臺(tái)：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.國(guó)家主干網(wǎng)的網(wǎng)絡(luò)流量增長(zhǎng)圖串匹配算法速度隨特征串?dāng)?shù)量的變化圖改進(jìn)算法時(shí)間復(fù)雜度優(yōu)化算法的數(shù)據(jù)結(jié)構(gòu)問題的核心：時(shí)間優(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語(yǔ)言處理HHMMArchitectureinICTCLASIIIHHMMArchitecture:

TraceStringAtomSegmentationNSP-basedroughsegmentation5thHMMAtomsequenceTopnsequence

WordssequenceLexicalresults

POSsequenceSimpleunknownwordsrecognitionPERLOCWordgraph4thHMMComplexunknownwordsrecognition3rdHMMClass-basedfinalsegmentation2thHMMRevisedNresultsLOCORG1thHMMPOSTaggingHHMM-basedChineselexicalanalysis語(yǔ)言處理Class-basedsegmentationci=wiiffwiislistedinthesegmentationlexicon;PER,LOC,ORG,TIMEorNUMiffwiisanunknownnamedentity;STRiffwiisanunknownsymbolstring;BEGiffbeginningofasentenceENDiffendingofasentenceOTHERotherwise.WordclassdefinitionClass-basedsegmentationmodel語(yǔ)言處理Role-basedUnknownwordrecognitionUnknownwordsrecognition:role-basedHMM毛/Surname澤/Mid_name東/last_name1893年/context誕生/remote_contextProbabilityP(Wi|Ci)ofrecognizedunknownwordscouldbeestimatedinrole-basedHMMHuapingZhangetc,ChineseNamedEntityRecognitionUsingRoleModel,InternationalJournalofComputationalLinguisticsandChineseLanguageProcessing,2003,Vol.8(2)語(yǔ)言處理ChineseNewWordIdentificationUnknownwordsornewwordsblastwiththedevelopmentofWebsize.非典、超女、售奶亭、法杰港、荷賽獎(jiǎng)、豎冰、招聘季…Weexploredcharactercoupling,single-characterwordprobability,Positioninformationwithidentifyingnewwords.語(yǔ)言處理ChineseNewWordIdentificationCharacterCoupling字對(duì)N1N2Coup（cicj）好看52500.9615德昂881否具1000才基3010.0323化氣31180.5806所思188

0.4444語(yǔ)言處理RecognitionSample未切分句子初切分結(jié)果碎片未登錄詞小洋房以西百十來(lái)米，豐鎬房和玉泰鹽鋪相鄰而立小/洋房/以西/百十/來(lái)/米/，豐/鎬/房/和/玉/泰/鹽/鋪/相鄰./而/立來(lái)米豐鎬房和玉泰鹽鋪而立豐鎬房玉泰鹽鋪盡管她已過而立之年盡管/她/已/過/而/立/之/年她已過而立之年而立之年阿維蘭熱走上前阿/維/蘭/熱/走/上/前阿維蘭熱走上前阿維蘭熱主任龐廷清聽完解救小組的情況反映主任/龐/廷/清/聽/完/解救/小組/的/情況/反映龐廷清聽完龐廷清語(yǔ)言處理UnpublishedTextMiningSupervisedLearning:ClassificationUnsupervisedLearning:ClusteringNewFeatureDetection文本分析Fromtheviewofgranularity,clusteringisaprocedureinauniformgranularity,whileclassificationindifferentgranularities.illustration:B12345AabcABacb

12345TextClassification(1)

InformationGranularitybasedclassification文本分析圖（4-11c）開放測(cè)試的準(zhǔn)確率——粒度原理法-.-.-.-類中心法——粒度原理法-.-.-.-類中心法Average↑5%文本分析DragPushingasarefinementstrategytoenhancetheperformanceofthelatterhigh-speedtextclassifiers,suchasCBorRocchio.Themainmotivationbehindthisstrategyisthehypothesisthattherestillexistsroomforperformanceimprovementbecausethelearningalgorithmitselfmayhaveinductivebias,orthetextcollectionmaymisfitthelearningmodeltosomedegree.TextClassification(2)

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

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

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

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

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