數(shù)據(jù)挖掘研究前沿韓家煒

1

DataMining:UnlimitedNewResearchFrontiersJiaweiHanDataMiningResearchGroupDepartmentofComputerScienceUniversityofIllinoisatUrbana-ChampaignAcknowledgements:NSF,ARL,NASA,AFOSR(MURI),DHS,Microsoft,IBM,Yahoo!,HPLab&Boeing04May20232

OutlineAnIntroductiontoDataMiningResearchGroupMiningandOLAPingInformationNetworksMiningHeterogeneousInformationNetworksMiningText-RichInformationNetworksOLAPing(Multi-dimensionalanalysis)ofinformationnetworks:TextCube,OLAPheterogeneousnetworksTamingtheWeb:WINACS(IntegratedminingofWebstructuresandcontents)MiningCyber-PhysicalSystemsandNetworksConclusionsDataMiningandDataWarehousing

JiaweiHan’sGroupatCS,UIUC

MiningpatternsandknowledgediscoveryfrommassivedataDatamininginheterogeneousinformationnetworksExploringbroadapplicationsofdataminingDevelopedmanyeffectivedataminingalgorithms,e.g.,FPgrowth,PrefixSpan,gSpan,StarCubing,CrossMine,RankingCube,CrossClus,RankClus,andNetClus600+researchpapersinconferencesandjournalsFellowofACM,FellowofIEEE,ACMSIGKDDInnovationAward,W.McDowellAward,DanielDruckerEminentFacultyAwardTextbook,“Datamining:ConceptsandTechniques,”adoptedworldwideProjectleadforNASAEventCubeforAviationSafety[2023-2023]DirectorofInformationNetworkAcademicResearchCenterfundedfromArmyResearchLab(ARL)[2023-2023]3

DataMiningResearchGroupatCS,UIUC4

NewBooksonDataMining&LinkMining5

Han,KamberandPei,DataMining,3rded.2023Yu,HanandFaloutsos(eds.),LinkMining,2023SunandHan,MiningHeterogeneousInformationNetworks,20236

OutlineAnIntroductiontoDataMiningResearchGroupMiningandOLAPingInformationNetworksMiningHeterogeneousInformationNetworksMiningText-RichInformationNetworksOLAPing(Multi-dimensionalanalysis)ofinformationnetworks:TextCube,OLAPheterogeneousnetworksTamingtheWeb:WINACS(IntegratedminingofWebstructuresandcontents)MiningCyber-PhysicalSystemsandNetworksConclusionsMiningHeterogeneousInformationNetworksRankClus/NetClusVS.RankCompete:ACompetingRandomWalkModelforRank-BasedClusteringDatabaseDataMiningAIIRTop-5rankedconferencesVLDBKDDIJCAISIGIRSIGMODSDMAAAIECIRICDEICDMICMLCIKMPODSPKDDCVPRWWWEDBTPAKDDECMLWSDMTop-5rankedtermsdatamininglearningretrievaldatabasedataknowledgeinformationqueryclusteringreasoningwebsystemclassificationlogicsearchxmlfrequentcognitiontextRankClass[KDD11]KnowledgePropagationinHeterogeneousNetwork8SimilaritySearchandRoleDiscoveryinInformationNetworksPath:ITIPath:ITIGITIWhichimagesaremostsimilartomeinFlickr?PathSim[VLDB11]MetaPath-GuidedSimilaritySearchinNetworksA“dirty”InformationNetwork(imaginary)Cleaned/InferredAdversarialNetworkChiefInsurgentCellLeadAutomaticallyinferRoleDiscoveryinInformationNetworks[KDD’10]AdviseeTopRankedAdvisorTimeNoteDavidM.Blei1.MichaelI.Jordan01-03PhDadvisor,20232.JohnD.Lafferty05-06Postdoc,2023HongCheng1.QiangYang02-03MSadvisor,20232.JiaweiHan04-08PhDadvisor,2023SergeyBrin1.RajeevMotawani97-98UnofficialadvisorInterestingResultsfromOtherDomainsRankCompete:Organizeyourphotoalbumautomatically!RanktreatmentsforAIDSfromMEDLINE9

Meta-PathBasedCo-authorshipPredictioninDBLPCo-authorshippredictionproblemWhethertwoauthorsaregoingtocollaborateforthefirsttimeCo-authorshipencodedinmeta-pathAuthor-Paper-AuthorTopologicalfeaturesencodedinmeta-pathsMeta-pathsbetweenauthorsunderlength4Meta-PathSemanticMeaning10

ThePowerofPathPredictExplainthepredictionpowerofeachmeta-pathWaldTestforlogisticregressionHigherpredictionaccuracythanusingprojectedhomogeneousnetwork7%higherinpredictionaccuracySocialrelationsplaymoreimportantrole?11

CaseStudy:PredictingConcreteCo-AuthorsHighqualitypredictivepowerforsuchadifficulttask12UsingdatainT0=[1989;1995]andT1=[1996;2023]PredictnewcoauthorrelationshipinT2=[2023;2023]13

OutlineAnIntroductiontoDataMiningResearchGroupMiningandOLAPingInformationNetworksMiningHeterogeneousInformationNetworksMiningText-RichInformationNetworksOLAPing(Multi-dimensionalanalysis)ofinformationnetworks:TextCube,OLAPheterogeneousnetworksTamingtheWeb:WINACS(IntegratedminingofWebstructuresandcontents)MiningCyber-PhysicalSystemsandNetworksConclusionsIntuitions:Friendstendtoholdsimilaropinions,whilefoestendtoholdconflictingopinionsBasedonusers’sentimentscoresondifferentobjects,wecaninferthesimilarityanddissimilarity(i.e.,pseudo-friendandpseudo-foerelationship)betweenusersBasedontheinferredfriendship,wecanimprovesentimentanalysisanduserclusteringbyconsideringglobalconsistencyonheterogeneousnetworksState-of-the-ArtExploresimilaropinionsinsteadofoppositeopinionsTypicallyconsidertextcontentwhileignoreInfoNetRelyonobservedfriendship(butmanyarehidden)IndustryNeed/BenefitsUsesentimentanalysistounderstandandminepublicopinionsonproduct/market-relatedissuesQoI-awareminingoftext-richmulti-genrenetworksIntelligentmethodsforpublicopinionassessment14Insight:Exploringoppositeopinionsmayhelptodiscoverhiddenfriendship,whichcanproducebettersentimentscoresanduserclustering.(mutuallyenhanceeachother)1.Considerinformationandsocialnetworks2.Exploreoppositeandsimilaropinions3.Bothobserved&hiddenfriendshiparevaluableObservedfriendshipObserved+InferredfriendshipRefiningsentimentscoresInferhiddenfriendshipPseudo-foeWhatpeoplearethinkingaboutcertaintarget/issue?ExploringOppositeOpinionsandDissimilaritiesforSentimentAnalysisLong-TermGoalsStructurallymodelatext-richmulti-genrenetworkandinvestigatemethodsforminingknowledgefromsuchnetworksEnhancesearchandknowledgediscoverycapabilityintext-richmulti-genrenetworkmodelSimilarstudiesoftext-richmulti-genrenetworkscanleadtonovelmodelsforminingandsearchrichtextualdatainsocialmediaforbusinessapplicationsApproaches15

Developanewmetapath-basedmeasureforinferringsimilarityanddissimilaritybetweenobjectsandusers,basedonsentimentscoresDevelopagraph-basedsemi-supervisedrefiningmodeltopropagatethesentimentscoresfromlabeleddatatounlabeleddataResult:Forsentimentclassification,ourmodelwith40labeleddataachievesbetterperformancethanSVM-basedmodelwith600trainingdata;foruserclustering,theresultsoninferredfriendshipcarrymoresemanticmeaningthantheresultsonobservedfriendship.ObservedfriendshipClusteringresultsofNormalizedCutsondifferentgraphsIdealresults(ground-truth)Observed+InferredEachclusterisagroupofuserswithsimilaropinionswrt3candidatesSVM-basedsupervisedmodelwith600trainingdataBetterthanExploringOppositeOpinionsandDissimilaritiesforSentimentAnalysis(2)TruthDiscovery:FromTruth-FindertoLatentTruthModel(1)State-of-the-ArtHITS-likeRandomWalkmethods(e.g.,TruthFinder(KDD’07),3-Estimate(WSDM’10),Investment(COLING’10),etc.)Limitations:(1)Qualityasasinglevalue,cannotwellsupportmultipletrueattributesforeachentity;and(2)basedonheuristics,notprincipledprobabilisticmodels.IndustryNeed/BenefitsIntegrateentity-attributedatabasesfrommultiplesources,e.g.salescampaign/productopinions,etc.Automaticallylearnthequalityofeachdatasourceandthemostaccurateintegratedrecords16Insight:Somesourcestendtomisstrueattributes(FalseNegatives),whilesomeotherstendtoproducefalseattributes(FalsePositives).Modelingtwo-sidedqualityiskeytosupportingmultipletruevaluesperentityfortruthfinding.ContributionsofLatentTruthModelAPrincipledProbabilisticModelModelnegativeclaimsandtwo-sidedsourcequalitywithBayesianregularizationNaturallysupportmultipletrueattributevaluesLTMcannaturallyincorporatepriordomainknowledgethroughBayesianpriorsLTMcanrunineitherbatchoronlinestreamingmodesforincrementaltruthfindingIMDBNegativeClaimPositiveClaimGenerateImplicitNegativeClaims:HarryPotterQualityofSourcesObservationofClaimsTruthofFactsGenerativeProcessinLTM:1)Foreachsource,generatefalsepositiverate(withstrongprior)andsensitivity(withuniformprior).2)Foreachfactf,generatepriortruthprobabilityandtruthlabel.3)Foreachclaim,generateobservationbasedontruthlabelandcorrespondingsourcequality.NetflixBadSourceCorrectClaimIncorrectClaimHighPrecision,HighRecallHighPrecision,LowRecallLowPrecision,LowRecallLong-TermGoalsTruth-findingmodelsformoregeneraldatatypes(numericalattributes,etc.)Modelsourcequalityinotherdataintegrationtasks,e.g.entityresolution.Trustworthinessinmulti-genrenetworks(text-richnetworks,socialnetworks,etc.)TruthDiscovery:FromTruth-FindertoLatentTruthModel(2)17Result:

Outperformstate-of-the-artmethodsontworealworlddatasets:booksandmoviesLTMisalsoveryscalable:seeLTM_incExperimentaldatasets:LargeandrealBookAuthorsfrom(1263books,879sources,48153claims,2420book-author,100labeled)MovieDirectorsfromBing(15073movies,12sources,108873claims,33526movie-director,100labeled)Varyingcutoffthreshold(consistentlybetter)RunningTime18

OutlineAnIntroductiontoDataMiningResearchGroupMiningandOLAPingInformationNetworksMiningHeterogeneousInformationNetworksMiningText-RichInformationNetworksOLAPing(Multi-dimensionalanalysis)ofinformationnetworks:TextCube,OLAPheterogeneousnetworksTamingtheWeb:WINACS(IntegratedminingofWebstructuresandcontents)MiningCyber-PhysicalSystemsandNetworksConclusionsEventCube:AnOverviewMultidimensionalTextDatabase98.0199.0299.0198.02LAXSJCMIAAUSovershootundershootbirdsturbulenceTimeLocationTopicCAFLTXLocation19981999TimeDeviationEncounterTopicdrill-downroll-upEventCubeRepresentationAnalyst…MultidimensionalOLAP,Ranking,CauseAnalysis,TopicSummarization/Comparison……

AnalysisSupport19

EventCube:AnOrganizedApproachforMiningandUnderstandingAnomalousAviationEventsFundedbyNASA$1.2M(2023-now)Text/TopicCube:GeneralIdeaHeterogeneous:categoricalattributes+unstructuredtextHowtocombine?Oursolution:TimeLocationPlaceEnvironment……Event

ReportACNTextdataCube:CategoricalAttributesTerm/TopicWeightT1W1T2W2T3W3……Text/TopicModel:UnstructuredTextMeasure20

EffectiveKeywordSearchTopCells(ICDE’10):Rankingaggregatedcells(objects)inTextCube.HealthcareReformTopCellsSystemPerson:Obama,Year:2023Org:Congress,Year:2023Person:Hillary,Year:2023…21

EffectiveOLAPExplorationTEXplorer(CIKM’11):Integratingkeyword-basedrankingandOLAPexplorationHealthcareReformTEXplorerSystemTop-1Dimension:PersonTop-2Dimension:OrgTop-3Dimension:Time20232023202322

EffectiveEventTrackingPET(KDD’10):trackingpopularityandtextualrepresentationofeventsinsocialcommunities(twitter)debate,cost,senate,…pass,success,law,…HealthcareReformPopularEventTrackingSystemTimePopularityContentFeb2023Mar2023Apr2023benefit,profit,effective,…23

24

OutlineAnIntroductiontoDataMiningResearchGroupMiningandOLAPingInformationNetworksMiningHeterogeneousInformationNetworksMiningText-RichInformationNetworksOLAPing(Multi-dimensionalanalysis)ofinformationnetworks:TextCube,OLAPheterogeneousnetworksTamingtheWeb:WINACS(IntegratedminingofWebstructuresandcontents)MiningCyber-PhysicalSystemsandNetworksConclusionsGrowingParallelPaths(WWW2023)

Result:25

MappingPagestoRecords(CIKM’10)Databaserecordscanbefoundonlinkpaths!26

WinaCS:WebInformationNetworkAnalysisforComputerScienceIntegrationofWebstructureminingandinformationnetworkanalysisTimWeninger,MarinaDanilevsky,etal.,“WinaCS:ConstructionandAnalysisofWeb-BasedComputerScienceInformationNetworks",ACMSIGMOD'11(systemdemo),Athens,Greece,June2023.27

28

OutlineAnIntroductiontoDataMiningResearchGroupMiningandOLAPingInformationNetworksMiningHeterogeneousInformationNetworksMiningText-RichInformationNetworksOLAPing(Multi-dimensionalanalysis)ofinformationnetworks:TextCube,OLAPheterogeneousnetworksTamingtheWeb:WINACS(IntegratedminingofWebstructuresandcontents)MiningCyber-PhysicalSystemsandNetworksConclusions29DiscoveryofSwarmsandPeriodicPatternsinMovingObjectDataAsystemthatminesmovingobjectpatterns:Z.Li,etal.,“MoveMine:MiningMovingObjectDatabases",SIGMOD’10(systemdemo)Z.Li,B.Ding,J.Han,andR.Kays,“MiningHiddenPeriodicBehaviorsforMovingObjects”,KDD’10(sub)Z.Li,B.Ding,J.Han,andR.Kays,“Swarm:MiningRelaxedTemporalMovingObjectClusters”,VLDB’10(sub)←BirdflyingpathsshownonGoogleEarthMinedperiodicpatternsbyournewmethod→←ConvoydiscoversonlyrestrictedpatternsSwarm

discoversmorepatterns→GeoTopicDiscovery:MiningSpatialTextLDMTDMGeoFolkLGTAGeo-taggedphotosw.landscape(coastvs.desertvs.mountain)30

Z.Yin,eta.,GeoTopicDiscoveryandComparison,WWW'1131

OutlineAnIntroductiontoDataMiningResearchGroupMiningandOLAPingInformationNetworksMiningHeterogeneousInformationNetworksMiningText-RichInformationNetworksOLAPing(Multi-dimensionalanalysis)ofinformationnetworks:TextCube,OLAPheterogeneousnetworksTamingtheWeb:WINACS(IntegratedminingofWebstructuresandcontents)MiningCyber-PhysicalSystemsandNetworksConclusions32

Conclusions:MiningBigandComplexDataMiningbigdata:AcriticalpartofbigdatainitiativesMostdataobjectsareinterconnected,formingheterogeneousinformationnetworksMostdatasetscanbe“organized”or“transformed”into“structured”multi-typed,heterogeneous