挖掘技术教程

第十三章半第十三章半结构化文本挖杨建北京大学计算机科学技术研究1Text-centricXMLText-centricXMLDocumentsmarkedupasE.g.,assemblymanuals,journalQueriesareuserinformationE.g.,givemetheSection(element)ofdocumentthattellsmehowtochangeabrakelight2VectorspacesandVectorspacesandVectorspaces–tried+testedframeworkforkeywordretrievalOther“bagofwords”applicationsinclassification,clustering…Fortext-centricXMLretrieval,canwemakeuseofvectorspaceideas?Challenge:capturethestructureofanXMLdocumentinthevectorspace.3VectorspacesandForinstance,distinguishbetweenVectorspacesandForinstance,distinguishbetweenfollowingtwoBillBill4Content-richXML:Content-richXML:Lexicon5EncodingtheGatesEncodingtheGatesWhataretheaxesofthevectorIntextretrieval,therewouldbeasingleaxisforGatesHerewemustseparateoutthetwooccurrences,underAuthorandTitleThus,axesmustrepresentnotonlyterms,butsomethingabouttheirpositioninanXMLtree6Beforeaddressingthis,letustheBeforeaddressingthis,letusthekindsofquerieswewantto7SubtreesandConsiderallsubtreesofthethatincludeatleastonelexiconSubtreesandConsiderallsubtreesofthethatincludeatleastonelexicon…8Structuralterms:Calleachoftheresulting(8+,inthepreviousslide)subtreesastructuralStructuralterms:Calleachoftheresulting(8+,inthepreviousslide)subtreesastructuraltermCreateoneaxisinthevectorspaceforeachdistinctstructuraltermEachdocumentbecomesavectorinthespaceofstructuraltermsAquerytreecanlikewisebefactoredintostructuraltermsAndrepresentedasaAllowsweightingportionsofthe9StructuraltermsStructuraltermsWeightsbasedonfrequenciesfornumberofoccurrences(justaswehadtf)Alltheusualissueswithterms(stemming?Casefolding?)remainExampleoftfTobeExampleoftfTobeornottoExercise:HowmanyaxesarethereinthisHerethestructuraltermscontainingtoorbewouldhavemoreweightthanthosethatForthedocontheleft:inastructuraltermrootedatthenodePlay,shouldn’tForthedocontheleft:inastructuraltermrootedatthenodePlay,shouldn’tHamlethaveahighertfweightthanIdea:multiplytfcontributionofatermtoanodeklevelsupbyk,forsomeg<Alaspoor=0.8Forthedoconthepreviousslide,theHamletismultipliedbyYorickismultipliedbyinanystructuraltermrootedatThenumberofThenumberofstructuralCanbeAlright,howhuge,ImpracticaltobuildavectorindexwithsomanyWillexaminepragmaticsolutionstothisshortly;fornow,continuetobelieve…RestrictstructuralRestrictstructuralDependingontheapplication,wemayrestrictthestructuraltermsE.g.,mayneverwanttoreturnaTitlenode,onlyBookorPlaynodesSodon’tenumerate/index/retrieve/scorestructuraltermsrootedatsomenodesTwoQuery-timematerializationofRestrictthekindsofsubtreestoamanageableQuery-timeInsteadofenumeratingallstructuraltermsofalldocsQuery-timeInsteadofenumeratingallstructuraltermsofalldocs(andthequery),enumerateonlyforthequeryThelatterishopefullyasmallNow,we’rereducedtocheckingwhichstructuralterm(s)fromthequerymatchasubtreeofanyThisistreepatternmatching:givenatexttreeandapatterntree,findmatchesExceptwehavemanytextOurtreesarelabeledandTextHereweseekadocwithHamletintheTextHereweseekadocwithHamletintheOnfindingthematchwecomputethecosinesimilarityscoreAfterallmatchesarefound,rankbysortingAlaspoorQuery(StillAdoc(StillAdocwithYoricksomewhereinQueryWillgettoitRestrictingtheRestrictingtheEnumeratingallstructuralterms(subtrees)isprohibitive,forindexingMostsubtreesmayneverbeusedinprocessinganyqueryCanwegetawaywithindexingarestrictedclassofsubtreesIdeally–focusonsubtreeslikelytoariseinJuruXML(IBMOnlypathsincludingalexicontermInJuruXML(IBMOnlypathsincludingalexicontermInthisexamplethereareonly14(why?)suchpathsThuswehave14structuraltermsintheTobeornottoWhyisthisfarmoreHowbigcantheindexbeasafunctionoftheExampleofaretrievalST=StructuralExampleofaretrievalST=StructuralNowranktheDoc’sbycosinesimilarity;e.g.,Doc9scores0.578.SQLforSQLforUsageHuman-readableData-orientedMixeddocuments(e.g.,patientReliesXMLSchemaTheprincipalformsTheprincipalformsofXQueryexpressionsare:pathelementFLWR("flower")listconditionalquantifieddatatypeEvaluatedwithrespecttoaFOR$pINdocument("bib.xml")//publisherLETFOR$pINdocument("bib.xml")//publisherLET$b:=document("bib.xml”)//book[publisher=$p]WHEREcount($b)>100RETURN$pFORgeneratesanorderedlistofbindingsofpublishernamesto$pLETassociatestoeachbindingafurtherbindingofthelistofbookelementswiththatpublisherto$batthisstage,wehaveanorderedlistoftuplesofbindings:WHEREfiltersthatlisttoretainonlythedesiredRETURNconstructsforeachtuplearesultingQueriesSupportedbyQueriesSupportedbyLocation/position(“chapterSimple/play/titlecontainsPathtitlecontains/play//titlecontainsComplexEmployeeswithtwoSubsumes:WhataboutrelevanceXQuery:OrderXQuery:OrderByOrderbyclauseonlyallowsorderingbySaybyanattributeRelevanceIsoftenCan’tbeexpressedeasilyasfunctionofsettobeIsbetterabstractedoutofqueryformulation(cf.XQuery:OrderByXQuery:OrderByfor$dinlet$e:=document("emps.xml")//emp[deptno=$d]wherecount($e)>=10orderbyavg($e/salary)descendingreturn<big-dept>{$d,XMLXMLNativeXMLNativeXMLUsesXMLdocumentaslogicalShouldPCDATA(parsedcharacterDocumentContrastDBmodifiedforGenericIRsystemmodifiedforXMLIndexingandMostnativeXMLIndexingandMostnativeXMLdatabasestakenaDBNoIRtyperelevanceOnlyafewthatfocusonrelevanceDatavs.Text-centricDatavs.Text-centricmainlyarecastingofrelationalusedformessagingbetweenenterpriseusedforannotatingRichinDemandsgoodintegrationoftextretrievalE.g.,findmetheISBN#sofBookswithatleastthreeChaptersdiscussingcocoaproduction,rankedbyPriceDatastructuresDatastructuresforXMLDatastructuresforDatastructuresforXMLWhataretheprimitivesweInvertedindex:givemeallelementsmatchingtextqueryQWeknowhowtodothis–treateachelementasadocumentGivemeallelements(immediately)belowanyinstanceoftheBookelementCombinationoftheParent/childNumbereachParent/childNumbereachMaintainalistofparent-childE.g.,Chapter:21EnablesimmediateButwhatabout“thewordHamletunderSceneelementunderaPlayGeneralpositionalViewtheXMLdocumentasGeneralpositionalViewtheXMLdocumentasatextBuildapositionalindexforeachMarkthebeginningandendforeachelement,PositionaldroppethunderVersePositionaldroppethunderVerseunderPl3y.SummaryofdataSummaryofdataPathcontainmentetc.canessentiallybesolvedbypositionalinvertedindexesRetrievalconsistsof“merging”Allthecompressiontricksetc.from276AarestillComplicationsarisefrominsertion/deletionofelements,textwithinelementsBeyondthescopeofthisINEX:aINEX:abenchmarkfortext-XMLINitiativefortheINitiativefortheEvaluationofXMLrmatik.uni-SponsoredDELOSNetworkofExcellenceforDigitalIEEEComputerBenchmarkfortheevaluationofXMLConsistsSetofXMLCollectionofretrievalDocumentcollectioninterlinkingtheWiki)INEX--adhocINEX--adhocEachengineindexesEngineteamconvertsretrievaltasksintoInXMLquerylanguageunderstoodbyInresponse,theengineretrievesnotdocs,butelementswithindocsEngineranksretrievedINEXINEX2006INEXINEX2006(IEEEComputerSociety12,107494Averagearticle:1,532XMLAveragenodedepth=INEX2007(WikipediatheXMLfull-textsof659,388morethan60GB(4.6GBwithout30millionarticle:161.35depth:INEXEachINEXEachtopicisaninformationneed,oneoftwokinds:ContentOnly(CO)–freetextContentandStructure(CAS)–explicitstructuralconstraints,e.g.,containmentSampleINEXCOSampleINEXCO<Title>computationalbiology<Keywords>computationalbiology,bioinformatics,genome,genomics,proteomics,sequencing,proteinfolding<Description>Challengesthatarise,andapproachesbeingexplored,intheinterdisciplinaryfieldofcomputational<Narrative>Toberelevant,adocument/componentmusteithertalkingeneraltermsabouttheopportunitiesattheintersectionofcomputerscienceandbiology,ordescribeaparticularproblemandthewaysitisbeingattacked.</Narrative>INEXEachINEXEachengineformulatesthetopicasaE.g.,usethekeywordslistedintheEngineretrievesoneormoreelementsandranksthem.Humanevaluatorsassigntoeachretrievedelementrelevanceandcoveragescores.INEXhowINEXhowrelevantistheretrievedistheretrievedelementtoospecific,toogeneral,orjustrightE.g.,ifthequeryseeksadefinitionoftheFastFourierTransform,doIgettheequation(toospecific),thec