数据库系统概念全套配套课件PPT ch21.ppt 25页

'Chapter21:InformationRetrieval Chapter21:InformationRetrievalRelevanceRankingUsingTermsRelevanceUsingHyperlinksSynonyms.,Homonyms,andOntologiesIndexingofDocumentsMeasuringRetrievalEffectivenessWebSearchEnginesInformationRetrievalandStructuredDataDirectories InformationRetrievalSystemsInformationretrieval(IR)systemsuseasimplerdatamodelthandatabasesystemsInformationorganizedasacollectionofdocumentsDocumentsareunstructured,noschemaInformationretrievallocatesrelevantdocuments,onthebasisofuserinputsuchaskeywordsorexampledocumentse.g.,finddocumentscontainingthewords“databasesystems”Canbeusedevenontextualdescriptionsprovidedwithnon-textualdatasuchasimagesWebsearchenginesarethemostfamiliarexampleofIRsystems InformationRetrievalSystems(Cont.)DifferencesfromdatabasesystemsIRsystemsdon’tdealwithtransactionalupdates(includingconcurrencycontrolandrecovery)Databasesystemsdealwithstructureddata,withschemasthatdefinethedataorganizationIRsystemsdealwithsomequeryingissuesnotgenerallyaddressedbydatabasesystemsApproximatesearchingbykeywordsRankingofretrievedanswersbyestimateddegreeofrelevance KeywordSearchInfulltextretrieval,allthewordsineachdocumentareconsideredtobekeywords.WeusethewordtermtorefertothewordsinadocumentInformation-retrievalsystemstypicallyallowqueryexpressionsformedusingkeywordsandthelogicalconnectivesand,or,andnotAndsareimplicit,evenifnotexplicitlyspecifiedRankingofdocumentsonthebasisofestimatedrelevancetoaqueryiscriticalRelevancerankingisbasedonfactorssuchasTermfrequencyFrequencyofoccurrenceofquerykeywordindocumentInversedocumentfrequencyHowmanydocumentsthequerykeywordoccursinFewergivemoreimportancetokeywordHyperlinkstodocumentsMorelinkstoadocumentdocumentismoreimportant RelevanceRankingUsingTermsTF-IDF(Termfrequency/InverseDocumentfrequency)ranking:Letn(d)=numberoftermsinthedocumentdn(d,t)=numberofoccurrencesoftermtinthedocumentd.RelevanceofadocumentdtoatermtThelogfactoristoavoidexcessiveweighttofrequenttermsRelevanceofdocumenttoqueryQn(d)n(d,t)1+TF(d,t)=logr(d,Q)=TF(d,t)n(t)tQ RelevanceRankingUsingTerms(Cont.)MostsystemsaddtotheabovemodelWordsthatoccurintitle,authorlist,sectionheadings,etc.aregivengreaterimportanceWordswhosefirstoccurrenceislateinthedocumentaregivenlowerimportanceVerycommonwordssuchas“a”,“an”,“the”,“it”etc.areeliminatedCalledstopwordsProximity:ifkeywordsinqueryoccurclosetogetherinthedocument,thedocumenthashigherimportancethaniftheyoccurfarapartDocumentsarereturnedindecreasingorderofrelevancescoreUsuallyonlytopfewdocumentsarereturned,notall SimilarityBasedRetrievalSimilaritybasedretrieval-retrievedocumentssimilartoagivendocumentSimilaritymaybedefinedonthebasisofcommonwordsE.g.,findktermsinAwithhighestTF(d,t)/n(t)andusethesetermstofindrelevanceofotherdocuments.Relevancefeedback:SimilaritycanbeusedtorefineanswersettokeywordqueryUserselectsafewrelevantdocumentsfromthoseretrievedbykeywordquery,andsystemfindsotherdocumentssimilartotheseVectorspacemodel:defineann-dimensionalspace,wherenisthenumberofwordsinthedocumentset.VectorfordocumentdgoesfromorigintoapointwhoseithcoordinateisTF(d,t)/n(t)Thecosineoftheanglebetweenthevectorsoftwodocumentsisusedasameasureoftheirsimilarity. RelevanceUsingHyperlinksNumberofdocumentsrelevanttoaquerycanbeenormousifonlytermfrequenciesaretakenintoaccountUsingtermfrequenciesmakes“spamming”easyE.g.,atravelagencycanaddmanyoccurrencesofthewords“travel”toitspagetomakeitsrankveryhighMostofthetimepeoplearelookingforpagesfrompopularsitesIdea:usepopularityofWebsite(e.g.,howmanypeoplevisitit)toranksitepagesthatmatchgivenkeywordsProblem:hardtofindactualpopularityofsiteSolution:nextslide RelevanceUsingHyperlinks(Cont.)Solution:usenumberofhyperlinkstoasiteasameasureofthepopularityorprestigeofthesiteCountonlyonehyperlinkfromeachsite(why?-seepreviousslide)Popularitymeasureisforsite,notforindividualpageBut,mosthyperlinksaretorootofsiteAlso,conceptof“site”difficulttodefinesinceaURLprefixlikecs.yale.educontainsmanyunrelatedpagesofvaryingpopularityRefinementsWhencomputingprestigebasedonlinkstoasite,givemoreweighttolinksfromsitesthatthemselveshavehigherprestigeDefinitioniscircularSetupandsolvesystemofsimultaneouslinearequationsAboveideaisbasisoftheGooglePageRankrankingmechanism RelevanceUsingHyperlinks(Cont.)ConnectionstosocialnetworkingtheoriesthatrankedprestigeofpeopleE.g.,thepresidentoftheU.S.AhasahighprestigesincemanypeopleknowhimSomeoneknownbymultipleprestigiouspeoplehashighprestigeHubandauthoritybasedrankingAhubisapagethatstoreslinkstomanypages(onatopic)AnauthorityisapagethatcontainsactualinformationonatopicEachpagegetsahubprestigebasedonprestigeofauthoritiesthatitpointstoEachpagegetsanauthorityprestigebasedonprestigeofhubsthatpointtoitAgain,prestigedefinitionsarecyclic,andcanbegotbysolvinglinearequationsUseauthorityprestigewhenrankinganswerstoaquery SynonymsandHomonymsSynonymsE.g.,document:“motorcyclerepair”,query:“motorcyclemaintenance”Needtorealizethat“maintenance”and“repair”aresynonymsSystemcanextendqueryas“motorcycleand(repairormaintenance)”HomonymsE.g.,“object”hasdifferentmeaningsasnoun/verbCandisambiguatemeanings(tosomeextent)fromthecontextExtendingqueriesautomaticallyusingsynonymscanbeproblematicNeedtounderstandintendedmeaninginordertoinfersynonymsOrverifysynonymswithuserSynonymsmayhaveothermeaningsaswell Concept-BasedQueryingApproachForeachword,determinetheconceptitrepresentsfromcontextUseoneormoreontologies:HierarchicalstructureshowingrelationshipbetweenconceptsE.g.,theISArelationshipthatwesawintheE-RmodelThisapproachcanbeusedtostandardizeterminologyinaspecificfieldOntologiescanlinkmultiplelanguagesFoundationoftheSemanticWeb(notcoveredhere) IndexingofDocumentsAninvertedindexmapseachkeywordKitoasetofdocumentsSithatcontainthekeywordDocumentsidentifiedbyidentifiersInvertedindexmayrecordKeywordlocationswithindocumenttoallowproximitybasedrankingCountsofnumberofoccurrencesofkeywordtocomputeTFandoperation:FindsdocumentsthatcontainallofK1,K2,...,Kn.IntersectionS1S2.....Snoroperation:documentsthatcontainatleastoneofK1,K2,…,Knunion,S1S2.....Sn,.EachSiiskeptsortedtoallowefficientintersection/unionbymerging“not”canalsobeefficientlyimplementedbymergingofsortedlists MeasuringRetrievalEffectivenessInformation-retrievalsystemssavespacebyusingindexstructuresthatsupportonlyapproximateretrieval.Mayresultin:falsenegative(falsedrop)-somerelevantdocumentsmaynotberetrieved.falsepositive-someirrelevantdocumentsmayberetrieved.Formanyapplicationsagoodindexshouldnotpermitanyfalsedrops,butmaypermitafewfalsepositives.Relevantperformancemetrics:precision-whatpercentageoftheretrieveddocumentsarerelevanttothequery.recall-whatpercentageofthedocumentsrelevanttothequerywereretrieved. MeasuringRetrievalEffectiveness(Cont.)Recallvs.precisiontradeoff:Canincreaserecallbyretrievingmanydocuments(downtoalowlevelofrelevanceranking),butmanyirrelevantdocumentswouldbefetched,reducingprecisionMeasuresofretrievaleffectiveness:Recallasafunctionofnumberofdocumentsfetched,orPrecisionasafunctionofrecallEquivalently,asafunctionofnumberofdocumentsfetchedE.g.,“precisionof75%atrecallof50%,and60%atarecallof75%”Problem:whichdocumentsareactuallyrelevant,andwhicharenot WebSearchEnginesWebcrawlersareprogramsthatlocateandgatherinformationontheWebRecursivelyfollowhyperlinkspresentinknowndocuments,tofindotherdocumentsStartingfromaseedsetofdocumentsFetcheddocumentsHandedovertoanindexingsystemCanbediscardedafterindexing,orstoreasacachedcopyCrawlingtheentireWebwouldtakeaverylargeamountoftimeSearchenginestypicallycoveronlyapartoftheWeb,notallofitTakemonthstoperformasinglecrawl WebCrawling(Cont.)Crawlingisdonebymultipleprocessesonmultiplemachines,runninginparallelSetoflinkstobecrawledstoredinadatabaseNewlinksfoundincrawledpagesaddedtothisset,tobecrawledlaterIndexingprocessalsorunsonmultiplemachinesCreatesanewcopyofindexinsteadofmodifyingoldindexOldindexisusedtoanswerqueriesAfteracrawlis“completed”newindexbecomes“old”indexMultiplemachinesusedtoanswerqueriesIndicesmaybekeptinmemoryQueriesmayberoutedtodifferentmachinesforloadbalancing InformationRetrievalandStructuredDataInformationretrievalsystemsoriginallytreateddocumentsasacollectionofwordsInformationextractionsystemsinferstructurefromdocuments,e.g.:Extractionofhouseattributes(size,address,numberofbedrooms,etc.)fromatextadvertisementExtractionoftopicandpeoplenamedfromanewarticleRelationsorXMLstructuresusedtostoreextracteddataSystemseeksconnectionsamongdatatoanswerqueriesQuestionansweringsystems DirectoriesStoringrelateddocumentstogetherinalibraryfacilitatesbrowsingUserscanseenotonlyrequesteddocumentbutalsorelatedones.Browsingisfacilitatedbyclassificationsystemthatorganizeslogicallyrelateddocumentstogether.Organizationishierarchical:classificationhierarchy AClassificationHierarchyForALibrarySystem ClassificationDAGDocumentscanresideinmultipleplacesinahierarchyinaninformationretrievalsystem,sincephysicallocationisnotimportant.ClassificationhierarchyisthusDirectedAcyclicGraph(DAG) AClassificationDAGForALibraryInformationRetrievalSystem WebDirectoriesAWebdirectoryisjustaclassificationdirectoryonWebpagesE.g.,Yahoo!Directory,OpenDirectoryprojectIssues:Whatshouldthedirectoryhierarchybe?Givenadocument,whichnodesofthedirectoryarecategoriesrelevanttothedocumentOftendonemanuallyClassificationofdocumentsintoahierarchymaybedonebasedontermsimilarity EndofChapter'