数据挖掘概念与技术 第二版 韩家炜 第九章03.ppt

29.05.2020,DataMining:PrinciplesandAlgorithms,1,DataMining:ConceptsandTechniquesChapter99.3.MultirelationalDataMining,JiaweiHanandMichelineKamberDepartmentofComputerScienceUniversityofIllinoisatUrbana-C/hanj2006JiaweiHanandMichelineKamber.Allrightsreserved.Acknowledgements:XiaoxinYin,29.05.2020,DataMining:PrinciplesandAlgorithms,2,Multi-RelationalandMulti-DBMining,Classificationovermultiple-relationsindatabasesClusteringovermulti-relationsbyUser-GuidanceMiningacrossmulti-relationaldatabasesMiningacrossmultipleheterogeneousdataandinformationrepositoriesSummary,29.05.2020,DataMining:PrinciplesandAlgorithms,3,MultirelationalDataMining,Classificationovermultiple-relationsindatabasesClusteringovermulti-relationsbyuser-guidanceLinkClus:EfficientclusteringbyexploringthepowerlawdistributionDistinct:DistinguishingobjectswithidenticalnamesbylinkanalysisMiningacrossmultipleheterogeneousdataandinformationrepositoriesSummary,29.05.2020,DataMining:PrinciplesandAlgorithms,4,Outline,Theme:“Knowledgeispower,butknowledgeishiddeninmassivelinks”,StartingwithPageRankandHITSCrossMine:Classificationofmulti-relationsbylinkanalysisCrossClus:Clusteringovermulti-relationsbyuser-guidanceMorerecentworkandconclusions,29.05.2020,DataMining:PrinciplesandAlgorithms,5,TraditionalDataMining,Workonsingle“flat”relations,flatten,Contact,LoseinformationoflinkagesandrelationshipsCannotutilizeinformationofdatabasestructuresorschemas,29.05.2020,DataMining:PrinciplesandAlgorithms,6,Multi-RelationalDataMining(MRDM),MotivationMoststructureddataarestoredinrelationaldatabasesMRDMcanutilizelinkageandstructuralinformationKnowledgediscoveryinmulti-relationalenvironmentsMulti-relationalrulesMulti-relationalclusteringMulti-relationalclassificationMulti-relationallinkageanalysis,29.05.2020,DataMining:PrinciplesandAlgorithms,7,ApplicationsofMRDM,e-Commerce:discoveringpatternsinvolvingcustomers,products,manufacturers,Bioinformatics/Medicaldatabases:discoveringpatternsinvolvinggenes,patients,diseases,Networkingsecurity:discoveringpatternsinvolvinghosts,connections,services,ManyotherrelationaldatasourcesExample:EvidenceExtractionandLinkDiscovery(EELD):ADARPA-fundingprojectthatemphasizesmulti-relationalandmulti-databaselinkageanalysis,29.05.2020,DataMining:PrinciplesandAlgorithms,8,ImportanceofMulti-relationalClassification(fromEELDProgramDescription),TheobjectiveoftheEELDProgramistoresearch,develop,demonstrate,andtransitioncriticaltechnologythatwillenablesignificantimprovementinourabilitytodetectasymmetricthreats,e.g.,alooselyorganizedterroristgroup.Patternsofactivitythat,inisolation,areoflimitedsignificancebut,whencombined,areindicativeofpotentialthreats,willneedtobelearned.Addressingthesethreatscanonlybeaccomplishedbydevelopinganewlevelofautonomicinformationsurveillanceandanalysistoextract,discover,andlinktogethersparseevidencefromvastamountsofdatasources,indifferentformatsandwithdifferingtypesanddegreesofstructure,torepresentandevaluatethesignificanceoftherelatedevidence,andtolearnpatternstoguidetheextraction,discovery,linkageandevaluationprocesses.,29.05.2020,DataMining:PrinciplesandAlgorithms,9,MRDMApproaches,InductiveLogicProgramming(ILP)FindmodelsthatarecoherentwithbackgroundknowledgeMulti-relationalClusteringAnalysisClusteringobjectswithmulti-relationalinformationProbabilisticRelationalModelsModelcross-relationalprobabilisticdistributionsEfficientMulti-RelationalClassificationTheCrossMineApproachYinetal,2004,29.05.2020,DataMining:PrinciplesandAlgorithms,10,InductiveLogicProgramming(ILP),Findahypothesisthatisconsistentwithbackgroundknowledge(trainingdata)FOIL,Golem,Progol,TILDE,BackgroundknowledgeRelations(predicates),Tuples(groundfacts),Trainingexamples,Backgroundknowledge,29.05.2020,DataMining:PrinciplesandAlgorithms,11,InductiveLogicProgramming(ILP),HypothesisThehypothesisisusuallyasetofrules,whichcanpredictcertainattributesincertainrelationsDaughter(X,Y)female(X),parent(Y,X),29.05.2020,DataMining:PrinciplesandAlgorithms,12,FOIL:First-OrderInductiveLearner,FindasetofrulesconsistentwithtrainingdataE.g.female(X),parent(Y,X)daughter(X,Y)Atop-down,sequentialcoveringlearnerBuildeachrulebyheuristicsFoilgainaspecialtypeofinformationgain,ExamplescoveredbyRule1,Allexamples,ExamplescoveredbyRule2,ExamplescoveredbyRule3,29.05.2020,DataMining:PrinciplesandAlgorithms,13,ILPApproaches,Top-downApproaches(e.g.FOIL)while(enoughexamplesleft)generatearuleremoveexamplessatisfyingthisruleBottom-upApproaches(e.g.Golem)UseeachexampleasaruleGeneralizerulesbymergingrulesDecisionTreeApproaches(e.g.TILDE),29.05.2020,DataMining:PrinciplesandAlgorithms,14,ILPProsandCons,AdvantagesExpressiveandpowerfulRulesareunderstandableDisadvantagesInefficientfordatabaseswithcomplexschemasNotappropriateforcontinuousattributes,29.05.2020,DataMining:PrinciplesandAlgorithms,15,AutomaticallyClassifyingObjectsUsingMultipleRelations,Whynotconvertmultiplerelationaldataintoasingletablebyjoins?Relationaldatabasesaredesignedbydomainexpertsviasemanticmodeling(e.g.,E-Rmodeling)IndiscriminativejoinsmayloosesomeessentialinformationOneuniversalrelationmaynotbeappealingtoefficiency,scalabilityandsemanticspreservationOurapproachtomulti-relationalclassification:Automaticallyclassifyingobjectsusingmultiplerelations,29.05.2020,DataMining:PrinciplesandAlgorithms,16,AnExample:LoanApplications,Applyforloan,Approveornot?,Askthebackenddatabase,29.05.2020,DataMining:PrinciplesandAlgorithms,17,TheBackendDatabase,Howtomakedecisionstoloanapplications?,29.05.2020,DataMining:PrinciplesandAlgorithms,18,Roadmap,MotivationRule-basedClassificationTupleIDPropagationRuleGenerationNegativeTupleSamplingPerformanceStudy,29.05.2020,DataMining:PrinciplesandAlgorithms,19,Rule-basedClassification,Everboughtahouse,LiveinChicago,Approve!,Justapplyforacreditcard,Reject,Applicant,Applicant,29.05.2020,DataMining:PrinciplesandAlgorithms,20,RuleGeneration,Applicant#1,Applicant#2,Applicant#3,Applicant#4,LoanApplications,Accounts,Orders,Districts,Otherrelations,Searchforgoodpredicatesacrossmultiplerelations,29.05.2020,DataMining:PrinciplesandAlgorithms,21,PreviousApproaches,InductiveLogicProgramming(ILP)TobuildaruleRepeatedlyfindthebestpredicateToevaluateapredicateonrelationR,firstjointargetrelationwithRNotscalablebecauseHugesearchspace(numerouscandidatepredicates)NotefficienttoevaluateeachpredicateToevaluateapredicateLoan(L,+):-Loan(L,A,?,?,?,?),Account(A,?,monthly,?)firstjoinloanrelationwithaccountrelationCrossMineismorescalableandmorethanonehundredtimesfasterondatasetswithreasonablesizes,29.05.2020,DataMining:PrinciplesandAlgorithms,22,CrossMine:AnEfficientandAccurateMulti-relationalClassifier,Tuple-IDpropagation:anefficientandflexiblemethodforvirtuallyjoiningrelationsConfinetherulesearchprocessinpromisingdirectionsLook-one-ahead:amorepowerfulsearchstrategyNegativetuplesampling:improveefficiencywhilemaintainingaccuracy,29.05.2020,DataMining:PrinciplesandAlgorithms,23,Roadmap,MotivationRule-basedClassificationTupleIDPropagationRuleGenerationNegativeTupleSamplingPerformanceStudy,29.05.2020,DataMining:PrinciplesandAlgorithms,24,TupleIDPropagation,0+,0,0+,1,0+,1,2+,0,Labels,1,2,02/27/93,monthly,124,Null,01/01/97,weekly,67,4,12/09/96,monthly,45,3,09/23/97,weekly,108,PropagatedID,Opendate,Frequency,AccountID,Applicant#1,Applicant#2,Applicant#3,Applicant#4,PropagatetupleIDsoftargetrelationtonon-targetrelationsVirtuallyjoinrelationstoavoidthehighcostofphysicaljoins,Possiblepredicates:Frequency=monthly:2+,1Opendatethresholdthenaddptocurrentruleelsebreak,Positiveexamples,Negativeexamples,A3=1,A3=1&A1=2,A3=1&A1=2&A8=5,29.05.2020,DataMining:PrinciplesandAlgorithms,29,EvaluatingPredicates,AllpredicatesinarelationcanbeevaluatedbasedonpropagatedIDsUsefoil-gaintoevaluatepredicatesSupposecurrentruleisr.Forapredicatep,foil-gain(p)=CategoricalAttributesComputefoil-gaindirectlyNumericalAttributesDiscretizewitheverypossiblevalue,29.05.2020,DataMining:PrinciplesandAlgorithms,30,RuleGeneration,StartfromthetargetrelationOnlythetargetrelationisactiveRepeatSearchinallactiverelationsSearchinallrelationsjoinabletoactiverelationsAddthebestpredicatetothecurrentruleSettheinvolvedrelationtoactiveUntilThebestpredicatedoesnothaveenoughgainCurrentruleistoolong,29.05.2020,DataMining:PrinciplesandAlgorithms,31,RuleGeneration:Example,Targetrelation,Firstpredicate,Secondpredicate,RangeofSearch,Addbestpredicatetorule,29.05.2020,DataMining:PrinciplesandAlgorithms,32,Look-one-aheadinRuleGeneration,Twotypesofrelations:EntityandRelationshipOftencannotfindusefulpredicatesonrelationsofrelationship,TargetRelation,SolutionofCrossMine:WhenpropagatingIDstoarelationofrelationship,propagateonemoresteptonextrelationofentity.,Nogoodpredicate,29.05.2020,DataMining:PrinciplesandAlgorithms,33,Roadmap,MotivationRule-basedClassificationTupleIDPropagationRuleGenerationNegativeTupleSamplingPerformanceStudy,29.05.2020,DataMining:PrinciplesandAlgorithms,34,NegativeTupleSampling,ArulecoverssomepositiveexamplesPositiveexamplesareremovedaftercoveredAftergeneratingmanyrules,therearemuchlesspositiveexamplesthannegativeones,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,29.05.2020,DataMining:PrinciplesandAlgorithms,35,NegativeTupleSampling(cont.),WhentherearemuchmorenegativeexamplesthanpositiveonesCannotbuildgoodrules(lowsupport)Stilltimeconsuming(largenumberofnegativeexamples)MakesamplingonnegativeexamplesImproveefficiencywithoutaffectingrulequality,+,+,+,+,+,29.05.2020,DataMining:PrinciplesandAlgorithms,36,Roadmap,MotivationRule-basedClassificationTupleIDPropagationRuleGenerationNegativeTupleSamplingPerformanceStudy,29.05.2020,DataMining:PrinciplesandAlgorithms,37,Syntheticdatasets:,Scalabilityw.r.t.numberofrelations,Scalabilityw.r.t.numberoftuples,29.05.2020,DataMining:PrinciplesandAlgorithms,38,RealDataset,PKDDCup99datasetLoanApplication,Mutagenesisdataset(4relations),29.05.2020,DataMining:PrinciplesandAlgorithms,39,Multi-RelationalClassification:Summary,ClassificationacrossmultiplerelationsInterestingpiecesofinformationoftenlieacrossmultiplerelationsItisdesirabletomineacrossmultipleinterconnectedrelationsNewmethodologyinCrossMine(forclassificationmodelbuilding)ID(andclasslabel)propagationleadstoefficiencyandeffectiveness(bypreservingsemantics)inCrossMineRulegenerationandnegativetuplesamplingleadtofurtherimprovedperformanceOurperformancestudyshowsordersofmagnitudefasterandhighaccuracycomparingwiththeRelationalMiningapproachFuturework:classificationinheterogeneousrelationaldatabases,29.05.2020,DataMining:PrinciplesandAlgorithms,40,MultirelationalDataMining,Classificationovermultiple-relationsindatabasesClusteringovermulti-relationsbyuser-guidanceLinkClus:EfficientclusteringbyexploringthepowerlawdistributionDistinct:DistinguishingobjectswithidenticalnamesbylinkanalysisMiningacrossmultipleheterogeneousdataandinformationrepositoriesSummary,29.05.2020,DataMining:PrinciplesandAlgorithms,41,Multi-RelationalandMulti-DBMining,Classificationovermultiple-relationsindatabasesClusteringovermulti-relationsbyUser-GuidanceMiningacrossmulti-relationaldatabasesMiningacrossmultipleheterogeneousdataandinformationrepositoriesSummary,29.05.2020,DataMining:PrinciplesandAlgorithms,42,Motivation1:Multi-RelationalClustering,office,position,Student,name,Targetofclustering,TraditionalclusteringworksonasingletableMostdataissemanticallylinkedwithmultiplerelationsThusweneedinformationinmultiplerelations,29.05.2020,DataMining:PrinciplesandAlgorithms,43,Motivation2:User-GuidedClustering,Course,Userusuallyhasagoalofclustering,e.g.,clusteringstudentsbyresearchareaUserspecifieshisclusteringgoaltoCrossClus,29.05.2020,DataMining:PrinciplesandAlgorithms,44,ComparingwithClassification,User-specifiedfeature(intheformofattribute)isusedasahint,notclasslabelsTheattributemaycontaintoomanyortoofewdistinctvaluesE.g.,ausermaywanttoclusterstudentsinto20clustersinsteadof3Additionalfeaturesneedtobeincludedinclusteranalysis,Alltuplesforclustering,Userhint,29.05.2020,DataMining:PrinciplesandAlgorithms,45,ComparingwithSemi-supervisedClustering,Semi-supervisedclusteringWagstaff,etal01,Xing,etal.02Userprovidesatrainingsetconsistingof“similar”and“dissimilar”pairsofobjectsUser-guidedclusteringUserspecifiesanattributeasahint,andmorerelevantfeaturesarefoundforclustering,Alltuplesforclustering,Semi-supervisedclustering,Alltuplesforclustering,User-guidedclustering,x,29.05.2020,DataMining:PrinciplesandAlgorithms,46,Semi-supervisedClustering,Muchinformation(inmultiplerelations)isneededtojudgewhethertwotuplesaresimilarAusermaynotbeabletoprovideagoodtrainingsetItismucheasierforausertospecifyanattributeasahint,suchasastudentsresearcharea,Tuplestobecompared,29.05.2020,DataMining:PrinciplesandAlgorithms,47,CrossClus:AnOverview,Useanewtypeofmulti-relationalfeaturesofclusteringMeasuresimilaritybetweenfeaturesbyhowtheyclusterobjectsintogroupsUseaheuristicmethodtosearchforpertinentfeaturesUseak-medoids-basedalgorithmforclustering,29.05.2020,DataMining:PrinciplesandAlgorithms,48,Roadmap,OverviewFeaturePertinenceSearchingforFeaturesClusteringExperimentalResults,29.05.2020,DataMining:PrinciplesandAlgorithms,49,Multi-relationalFeatures,Amulti-relationalfeatureisdefinedby:Ajoinpath.E.g.,StudentRegisterOpenCourseCourseAnattribute.E.g.,Course.area(Fornumericalfeature)anaggregationoperator.E.g.,sumoraverageCategoricalFeaturef=StudentRegisterOpenCourseCourse,Course.area,null,areasofcoursesofeachstudent,Valuesoffeaturef,NumericalFeature,e.g.,averagegradesofstudentsh=StudentRegister,Register.grade,averageE.g.h(t1)=3.5,29.05.2020,DataMining:PrinciplesandAlgorithms,50,RepresentingFeatures,Mostimportantinformationofafeaturefishowfclustersobjectsintogroupsfisrepresentedbysimilaritiesbetweeneverypairofobjectsindicatedbyf,Similaritybetweeneachpairoftuplesindicatedbyf.Thehorizontalaxesarethetupleindices,andtheverticalaxisisthesimilarity.ThiscanbeconsideredasavectorofNxNdimensions.,SimilarityvectorVf,29.05.2020,DataMining:PrinciplesandAlgorithms,51,SimilaritybetweenTuples,CategoricalfeaturefDefinedastheprobabilityt1andt2havingthesamevaluee.g.wheneachofthemselectsanothercourse,whatistheprobabilitytheyselectcoursesofthesameareaNumericalfeatureh,simf(t1,t2)=0.5*0.3+0.5*0.3=0.3,29.05.2020,DataMining:PrinciplesandAlgorithms,52,SimilarityBetweenFeatures,ValuesofFeaturefandg,Similaritybetweentwofeaturescosinesimilarityoftwovectors,Vf,Vg,29.05.2020,DataMining:PrinciplesandAlgorithms,53,ComputingFeatureSimilarity,Objects,Featuref,Featureg,DB,AI,TH,Infosys,Cogsci,Theory,Similaritybetweenfeaturevaluesw.r.t.theobjects,sim(fk,gq)=i=1toNf(ti).pkg(ti).pq,Objectsimilarities,hardtocompute,Featurevaluesimilarities,easytocompute,Computesimilaritybetweeneachpairoffeaturevaluesbyonescanondata,29.05.2020,DataMining:PrinciplesandAlgorithms,54,SimilaritybetweenCategoricalandNumericalFeatures,Partsdependingonti,Partsdependingonalltiwithji,29.05.2020,DataMining:PrinciplesandAlgorithms,55,SimilaritybetweenNumericalFeatures,SimilaritybetweennumericalfeatureshandgSupposeobjectsareorderedaccordingtohComputingVhVgScanobjectsinorderofhWhenscanningeachobjectt*,maintainthesetofobjectstwith0h(t*)-h(t)h,inabinarytreesortedwithgUpdateVhVgbyalltwith0h(t*)-h(t*)h,|g(t)-g(t*)|g,Objectstsatisfying0h(t*)-h(t)h,|g(t)-g(t*)|g,t*,Featureh,Objects,t*,29.05.2020,DataMining:PrinciplesandAlgorithms,56,Roadmap,OverviewFeaturePertinenceSearchingforFeaturesClusteringExperimentalResults,29.05.2020,DataMining:PrinciplesandAlgorithms,57,SearchingforPertinentFeatures,DifferentfeaturesconveydifferentaspectsofinformationFeaturesconveyingsameaspectofinformationusuallyclusterobjectsinmoresimilarwaysresearchgroupareasvs.conferencesofpublicationsGivenuserspecifiedfeatureFindpertinentfeaturesbycomputingfeaturesimilarity,29.05.2020,DataMining:PrinciplesandAlgorithms,58,HeuristicSearchforPertinentFeatures,Overallprocedure1.Startfromtheuser-specifiedfeature2.Searchinneighborhoodofexistingpertinentfeatures3.Expandsearchrangegradually,TupleIDpropagationYin,etal.04isusedtocreatemulti-relationalfeaturesIDsoftargettuplescanbepropagatedalonganyjoinpath,fromwhichwecanfindtuplesjoinablewitheachtargettuple,29.05.2020,DataMining:PrinciplesandAlgorithms,59,Roadmap,OverviewFeaturePertinenceSearchingforFeaturesClusteringExperimentalResults,29.05.2020,DataMining:PrinciplesandAlgorithms,60,ClusteringwithMulti-RelationalFeature,GivenasetofLpertinentfeaturesf1,fL,similaritybetweentwoobjectsWeightofafeatureisdeterminedinfeaturesearchbyitssimilaritywithotherpertinentfeaturesForclustering,weuseCLARANS,ascalablek-medoidsNg&Han94algorithm,29.05.2020,DataMining:PrinciplesandAlgorithms,61,Roadmap,OverviewFeaturePertinenceSearchingforFeaturesClusteringExperimentalResults,29.05.2020,DataMining:PrinciplesandAlgorithms,62,Experiments:CompareCrossCluswith,Baseline:OnlyusetheuserspecifiedfeaturePROCLUSAggarwal,etal.99:astate-of-the-artsubspaceclusteringalgorithmUseasubsetoffeaturesforeachclusterWeconvertrelationaldatabasetoatablebypropositionalizationUser-specifiedfeatureisforcedtobeusedineveryclusterRDBCKirstenandWrobel00ArepresentativeILPclusteringalgorithmUseneighborinformationofobjectsforclusteringUser-specifiedfeatureisforcedtobeused,29.05.2020,DataMining:PrinciplesandAlgorithms,63,ClusteringAccuracy,ToverifythatCrossCluscapturesusersclusteringgoal,wedefine“accuracy”ofclusteringGivenaclusteringtaskManuallyfindallfeaturesthatcontaininformationdirectlyrelatedtotheclusteringtaskstandardfeaturesetE.g.,ClusteringstudentsbyresearchareasStandardfeatureset:researchgroup,groupareas,advisors,conferencesofpublications,courseareasAccuracyofclusteringresult:howsimilaritistotheclusteringgeneratedbystandardfeatureset,29.05.2020,DataMining:PrinciplesandAlgorithms,64,MeasureofClusteringAccuracy,AccuracyMeasuredbymanuallylabeleddataWemanuallyassigntuplesintoclustersaccordingtotheirproperties(e.g.,professorsindifferentresearchareas)Accuracyofclustering:Percentageofpairsoftuplesinthesameclu