高性能计算导论课件-1大数据挖掘

例子2 Youreceiveanemailfromamedicalresearcherconcerningaprojectthatyouareeagertoworkon.

Hi, I'veattachedthedatafilethatImentionedinmypreviousemail. Eachlinecontainstheinformationforasinglepatientandconsistsoffivefields. Wewanttopredictthelastfieldusingtheotherfields. Idon'thavetimetoprovideanymoreinformationaboutthedatasinceI'mgoingoutoftownforacoupleofdays,buthopefullythatwon'tslowyoudowntoomuch.

Thanksandseeyouinacoupleofdays.例子2 Despitesomemisgivings,youproceedtoanalyzethedata.Thefirstfewrowsofthefileareasfollows:Nothinglooksstrange.Youputyourdoubtsasideandstarttheanalysis.Twodayslateryouyouarriveforthemeeting,andwhilewaitingforotherstoarrive,youstrikeupaconversationwithastatisticianwhoisworkingontheproject.例子2Statistician:So,yougotthedataforallthepatients?DataMiner:Yes.Ihaven'thadmuchtimeforanalysis,butIdohaveafewinterestingresults.Statistician:Amazing.ThereweresomanydataissueswiththissetofpatientsthatIcouldn'tdomuch.DataMiner:Oh?Ididn'thearaboutanypossibleproblems.Statistician:Well,firstthereisfield5,thevariablewewanttopredict.It'scommonknowledgeamongpeoplewhoanalyzethistypeofdatathatresultsarebetterifyouworkwiththelogofthevalues,butIdidn'tdiscoverthisuntillater.Wasitmentionedtoyou?DataMiner:No.Statistician:Butsurelyyouheardaboutwhathappenedtofield4?It'ssupposedtobemeasuredonascalefrom1to10,with0indicatingamissingvalue,butbecauseofadataentryerror,all10'swerechangedinto0's.DataMiner:Interesting.Werethereanyotherproblems?Statistician:Yes,fields2and3arebasicallythesame,butIassumethatyouprobablynoticedthat.DataMiner:Yes,butthesefieldswereonlyweakpredictorsoffield5.例子2Statistician:Anyway,givenallthoseproblems,I'msurprisedyouwereabletoaccomplishanything.DataMiner:True,butmyresultsarereallyquitegood.Field1isaverystrongpredictoroffield5.I'msurprisedthatthiswasn'tnoticedbefore.Statistician:What?Field1isjustanidentificationnumber.DataMiner:Nonetheless,myresultsspeakforthemselves.Statistician:Oh,no!Ijustremembered.WeassignedIDnumbersafterwesortedtherecordsbasedonfield5.Thereisastrongconnection,butit'smeaningless.Sorry.Lesson:Gettoknowyourdata!挖掘山西挖矿前提是有矿，包括煤矿的储藏量，储藏深度，煤的成色之后是挖矿，要把这些埋在地下的矿挖出来，需要挖矿工，挖矿机，运输机之后是加工，洗煤，炼丹，等等最后才是转化为银子数据挖掘前提是有数据，包括数据储藏量，储藏深度，数据的成色之后是数据挖掘，要把这些埋藏的数据挖掘出来之后是把数据可视化输出，指导分析、商业实践直到这一步，才创造了价值大数据：一座正在形成的巨型矿山！越来越多的数据被收集Web数据电子商务购买消费记录银行支付转账信息电脑变得强大和廉价商业竞争压力变大提供更好的，更个性化的服务给用户发现用户的兴趣背景：商业视角背景：科学视角数据收集及存储的速度变大

(GB/hour)卫星上面的传感器天文望远镜基因数据科学仿真：生产大量数据传统技术无法应对这么大的数据量数据挖掘数据的处理和分类形成研究假设挖掘大规模数据集数据中经常存在“隐藏”的信息人工分析需要花费大量的数据，也很难发现其背后的信息现实中，大量的数据都没有被分析过TheDataGapTotalnewdisk(TB)since2019NumberofanalystsFrom:R.Grossman,C.Kamath,V.Kumar,“DataMiningforScientificandEngineeringApplications”数据挖掘定义技术角度的定义数据挖掘（DataMining)是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程近义词：数据融合、数据分析和决策支持等数据源必须是真实的、海量的、含噪声的发现的是用户感兴趣的知识发现的知识要可接受、可理解、可运用并不要求发现放之四海皆准的知识，仅支持特定的发现问题

数据挖掘定义商业角度的定义数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性信息一类深层次的数据分析方法可以描述为:按企业既定业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证己知的规律性，并进一步将其模型化的有效方法

什么是数据挖掘？

什么是数据挖掘？

在美国的特定地点，特定的名字比较流行(O’Brien,O’Rurke,O’Reilly…inBostonarea)

把搜索引擎关于“Amazon”的返回结果按照相似性分为不同的小组

什么不是数据挖掘？

从电话库中查询电话号码

利于搜索引擎查找“Amazon”的信息基本概念信息：事物运动的状态和状态变化的方式数据：指一个有关事实F的集合如学生档案数据库中有关学生基本情况的各条记录用来描述事物有关方面的信息一般而言，这些数据都是准确无误的数据可能存储在数据库、数据仓库和其他信息资料库中基本概念知识

人们实践经验的结晶且为新的实践所证实的；是关于事物运动的状态和状态变化的规律；是对信息加工提炼所获得的抽象化产物。知识的形式可能是模式、关联、变化、异常以及其他有意义的结构。基本概念模式对于集合F中的数据，我们可以用语言L来描述其中数据的特性，得出一个表达式E，E所描述的数据是集合F的一个子集FE。只有当表达式E比列举所有FE中元素的描述方法更为简单时，我们才可称之为模式。如：“如果成绩在81-90之间，则成绩优良”可称为一个模式，而“如果成绩为81、82、83、84、85、86、87、88、89或90，则成绩优良”则不能称之为一个模式。数据挖掘里程碑1763年，ThomasBayes的论文在他死后发表Bayes理论将当前概率与先验概率联系起来Bayes理论能够帮助理解基于概率估计的复杂现况成为数据挖掘和概率论的基础1805年,Adrien-MarieLegendre和CarlFriedrichGauss使用回归确定了天体（彗星和行星）绕行太阳的轨道回归分析的目标是估计变量之间的关系在这个例子中采用的方法是最小二乘法回归成为数据挖掘的重要工具之一数据挖掘里程碑1936年，计算机时代即将到来，海量数据的收集和处理成为可能1936年发表的论文《On

ComputableNumbers》中，AlanTuring介绍了通用图灵机的构想通用机具有像今天的计算机一般的计算能力现代计算机就是在图灵这一开创性概念上建立起来的1943年，WarrenMcCullon和WalterPitts首先构建出神经网络的概念模型《Alogicalcalculusoftheideasimmanentinnervousactivity》的论文阐述了网络中神经元的概念每一个神经元可以做三件事情：接受输入，处理输入和生成输出。数据挖掘里程碑1975年，JohnHenryHolland所著的《自然与人工系统中的适应》问世成为遗传算法领域具有开创意义的著作讲解了遗传算法领域中的基本知识，阐述理论基础，探索其应用1989年，术语“数据库中的知识发现”（KDD）被GregoryPiatetsky-Shapiro提出合作建立起第一个同样名为KDD的研讨会数据挖掘里程碑1992年，BerhardE.Boser,IsabelleM.Guyon和VladimirN.Vanik对原始的支持向量机提出了一种改进办法新的支持向量机充分考虑到非线性分类器的构建1993年，GregoryPiatetsky-Shapiro创立“KnowledgeDiscoveryNuggets(KDnuggets)”通讯本意是联系参加KDD研讨会的研究者KDnuggets的读者群现在似乎广泛得多数据挖掘里程碑2019年，MichealLewis写的《点球成金》出版奥克兰运动家队（美国职业棒球大联盟球队）使用一种统计的，数据驱动的方式针对球员的素质进行筛选，这些球员被低估或者身价更低成功组建了一支打进2019和2019年季后赛的队伍，而他们的薪金总额只有对手的1/3数据挖掘里程碑在2019年二月，DJPatil成为白宫第一位首位数据科学家…数据挖掘：商业、科学、工程和医药、信用卡交易、股票市场、国家安全、基因组测序、临床试验……相关领域人工智能机器学习模式识别统计学数据库…….人工智能20世纪50年代到70年代，“推理期”A.NewellandH.Simon,“逻辑理论家”“通用问题求解”20世纪70年代中期，“知识期”专家系统由人把知识总结出来再教给计算机相当困难20世纪80年代，“机器学习”1980，在CMU举行第一届机器学习研讨会1983,《MachineLearning:AnArtificialIntelligenceApproach》1986，《MachineLearning》创刊机器学习分类从例子中学习监督学习（分类、回归）非监督学习（聚类）在问题求解和规划中学习通过观察和发现学习从指令中学习R.S.Michalski,J.G.Carbonell,T.M.Mitchell,eds,“MachineLearning：AnArtificialIntelligenceApproach,”PaloAlto,CA:TiogaPublishingCo.,1983.从例子中学习20世纪90年代中期之前，归纳逻辑程序设计（InductiveLogicProgramming）知识表达能力，复杂数据极其关系利用领域知识指导学习从数据中学习领域知识学习过程面临的假设空间太大数据挖掘vs知识发现（KDD）数据挖掘是KDD中利用算法处理数据的步骤逐渐演变成KDD的同义词

数据挖掘vs机器学习机器学习：利用经验来改善计算机系统自身的性能数据挖掘(知识发现)：从海量数据中找出有用的知识利用机器学习界提供的技术来分析海量数据利用数据库界提供的技术来管理海量数据数据挖掘vs统计学数据挖掘很多工作由统计方法完成目标相似，许多算法源于数理统计部分统计学家认为数据挖掘是统计学的分支大部分数据挖掘研究人员不这么认为数据挖掘vs传统数据分析方法数据源数据是海量的数据有噪声数据可能非结构化，异构多源传统数据分析方法：假设驱动给出一个假设，然后通过数据验证数据挖掘：发现驱动模式从数据中自动提取出来发现不能靠直觉发现的信息或知识挖掘出的信息越出乎意料，可能越有价值实现流程

各步骤之间互相影响、反复调整，形成一种螺旋式上升过程。DataMiningTasksPredictionMethodsUsesomevariablestopredictunknownorfuturevaluesofothervariables.DescriptionMethodsFindhuman-interpretablepatternsthatdescribethedata.From[Fayyad,et.al.]AdvancesinKnowledgeDiscoveryandDataMining,2019DataMiningTasks...Classification[Predictive]Clustering[Descriptive]AssociationRuleDiscovery[Descriptive]SequentialPatternDiscovery[Descriptive]Regression[Predictive]AnomalyDetection[Predictive]saedsayad/

data_mining_map.htmChallengesofDataMiningScalabilityDimensionalityComplexandHeterogeneousDataDataQualityDataOwnershipandDistributionPrivacyPreservationStreamingData相关学术会议SIGIR,KDD,ICDM,SDM,CIKM,PAKDDWWW,WSDMAAAI,IJCAIVLDB,SIGMOD,ICDEBigDataICML,NIPS…相关学术期刊IEEETransactionsonKnowledgeandDataEngineering(TKDE)ACMTransactionsonKnowledgeDiscoveryfromData(TKDD)ACMTransactionsonIntelligentSystemsandTechnology(TIST)ACMTransactionsonInformationSystems(TOIS)IEEETransactionsonSystems,Man,andCybernetics,PartBIEEETransactionsonNeuralNetwork(TNN)KnowledgeandInformationSystems(KAIS)PatternRecognition(PR)相关比赛阿里天池比赛:tianchi.aliyun/IJCAI:/index.php/repeat-buyers-prediction-competitionKaggle:https://kaggle/DataCastle:pkbigdata/ImageNet:/challenges/LSVRC/2019/indexKDDCup:https://kddcup2019/information.htmlAngryBirdsAICompetition:/Someofmyresearchwork…RecommenderSystemMotivation:InformationOverloadSolution:SearchEnginesRecommenderSystemsMissingValuePredictionWithCFApproach1:Neighborhood-basedapproachApproach2:Model-basedapproachApproach3:Time-awareapproachApproach4:NetworkcoordinatebasedapproachApproach5:Ranking-basedapproach45SimilarityComputationApproach1:Neighborhood-BasedUser-itemmatrix:M×N,eachentryisthefailureprobabilityofaWebservicePearsonCorrelationCoefficient(PCC)?0.5

SimilarUserSelectionApproach1:Neighborhood-BasedForauseru,asetofsimilarusersS(u)canbefoundby:Simk

isthekth

largestPCCvaluewiththecurrentuseru.Sim(u,a)>0istoexcludethedissimilarusers.Sim(u,a)canbecalculatedbyPCC.User-basedPrediction(UPCC)Approach1:Neighborhood-BasedGivenamissingvaluepu,i,iftheuseruhassimilarusers(S(u)≠null),themissingvaluecanbepredictedby:

and

areaveragefailureprobabilitiesofdifferentWebservicesobservedbyuseruandusera.wacanbecalcualtedby:WSRec:HybridPredictionApproachApproach1:Neighborhood-BasedSimilarusers+SimilarWebservicesUPCCIPCCExperimentsApproach1:Neighborhood-BasedMetricsofPredictionAccuracy

:theexpectedvalue

:thepredictedvalue

:thenumberofpredictedvalues50PerformanceComparisonApproach1:Neighborhood-Based51DrawbacksofNeighborhood-basedApproachApproach1:Neighborhood-BasedComputationalcomplexityMatrixsparsityproblemNoteasytofindsimilarusers(orsimilaritems)

Approach2:Model-basedApproachApproach2:Model-BasedAsmallnumberoffactorsinfluencingtheQoSperformanceAuser’sWebserviceQoSvaluescorrespondtoalinearcombinationofthefactorsEachrowofUTisasetoffeaturefactors,andeachcolumnofVisasetoflinearpredictors

MatrixFactorization(MF)s1s2s3s4s5s6

TheerrorbetweentheactualValueandthepredictionRegularizationterms[IEEETSC’13a]UTVNIMF:Neighborhood–IntegratedMatrixFactorizationApproach2:Model-BasedUser’sownratingRatingduetosimilarusersPerformanceComparisonApproach2:Model-BasedApproach3:Time-AwareApproachTime-awarepersonalizedQoSevaluationonWebservicesisessentialforAutomaticselectionDynamicalcomposition[ISSRE’11]Approach3:Time-AwareApproachModel-Based:TensorFactorizationApproach3:Time-AwareApproachUserLatentFeaturesLearningApproach3:Time-AwareApproachObjectivefunctionLocaloptimalsolutionisfoundbyincrementalgradientdescentTheerrorbetweenestimatedtensorandtheoriginaltensorRegularizationtermswhichconstrainthenormsofU,SandT,toavoidoverfittingproblemRegularizationtermwhichpreventsthepredictedQoSvaluesfromvaryingalotagainsttheaverageQoSvalueMissingValuePredictionApproach3:Time-AwareApproachGivenfeaturespacesU,SandT,amissingvalueispredictedbyevaluatinghowthefeaturesofcorrespondinguser,serviceandtimeapplytoeachother

Example:UserTimeServicelatent-servicematrixlatent-usermatrixu1u2u3u4u5latent-timematrixs1s2s3s4s5t1t2t3t4t5PerformanceComparisonsApproach3:Time-AwareApproachMatrixFactorizationextendedmethodsMF1Thismethodconsiderstheuser-service-timetensorasasetofuser-servicematrixslicesintermsoftime.ThenitappliesMFoneachmatrixslice.MF2Thismethodcompressestheuser-service-timetensorintoauser-servicematrix.ThenitappliesMFonthisuser-servicematrix.TensorFactorizationmethodsTFTensorfactorization-basedpredictionmethod.WSPredTensorfactorization-basedpredictionmethodwithaverageQoSvalueconstraints.ExperimentalResultsApproach3:Time-AwareApproachAsmallerMAEorRMSEvaluemeansabetterperformance

9~25%5~15%3~12%16~22%3~13%1~12%PerformanceimprovementofWSPredApproach4:NetworkCoordinateBasedKeyidea:leveragebothhistoricalQoSinformationandactivemeasurementstoenhanceQoSpredictionAdvantage:solvethecold-startprobleminMFmodelsAPrototypeofNetworkCoordinateSystemApproach4:NetworkCoordinate-basedPrediction[ICWS’12]AlgorithmOverviewApproach4:NetworkCoordinateBasedOfflineCoordinatesUpdatingOnlineWebServiceSelectionDistancematrixbetweennlandmarkswhereSquaredsumofpredictionerrorRegularizationtermEuclideandistanceminLandmarksApproach4:NetworkCoordinateBasedLandmarkCoordinateComputationDistancematrixbetweennlandmarksandwWebservicehostsminSquaredsumoferrorRegularizationtermWebservicehostApproach4:NetworkCoordinateBasedWebServiceCoordinateComputationminServiceuserWebservicehostsHistoricaldataReferenceinformationoflandmarksAvailablehistoricaldataconstraintsRegularizationtermApproach4:NetworkCoordinateBasedServiceUserCoordinateComputationThesetofWebserviceswithunknownresponsetimedataThecoordinateofserviceuseruThecoordinateofWebservicesiApproach4:NetworkCoordinateBasedQoSPredictionResultPerformanceComparisonApproach5:Ranking-BasedPredictionSelecttheoptimalWebservicefromthecandidatesNeighborhood-based

approaches:

PredictQoSvaluesrankthecandidates

Ranking-basedapproach:

RankthecandidatesdirectlywithoutpredictingQoSvaluesExpectedvalues:(2,3,5)on(ws1,ws2,ws3)Prediction1:(3,2,4);MAE=(|2-3|+|3-2|+|5-4|)/3=1Prediction2:(1,2,3);MAE=(|2-1|+|3-2|+|5-3|)/3=1.3Ranking-based:ExpectedRanking:ws1<ws2<ws3Prediction1:ws2<ws1<ws3Prediction2:ws1<ws2<ws3Approach5:Ranking-BasedPredictionUserpreferenceontwoWebserviceswhichhavebeeninvokedpreviously:UserpreferenceonpairsofWebservicesthathavenotbothbeeninvokedbythecurrentuser:Approach5:Ranking-BasedPredictionKendallRankCorrelationCoefficient(KRCC)NisthenumberofWebservices.Cisthenumberofconcordantpairsbetweentworankings.Disthenumberofdiscordantpairs.TargetWebservices:(ws1,ws2,ws3)User1observedresponse-time:(2,3,5)User2observedresponse-time:(1,2,3)User1:ws1<ws2,ws1<ws3,ws2<ws3User2:ws1<ws2,ws1<ws3,ws2<ws3N=3;C=3;D=0;Sim(user1,user2)=(3-0)/(3(3-1)/2)=1TargetWebservices:(ws1,ws2,ws3)User1observedresponse-time:(2,3,5)User2observedresponse-time:(3,2,1)User1:ws1<ws2,ws1<ws3,ws2<ws3User2:ws1>ws2,ws1>ws3,ws2>ws3N=3;C=0;D=3;Sim(user1,user2)=(0-3)/(3(3-1)/2)=-1Givenapreferencefunction,choosearankingthatagreeswiththepreferencesas