大数据研究徐宗本.ppt

Exploring Big Data Analysis:Fundamental Scientific ProblemsZongben Xu(Xian Jiaotong University)Email: Homepage:http:/OutlinelBig Data:Opportunities and ChallengeslSome More Scientific Problems in Big Data Analysis and ProcessinglSome Advances on Big Data ResearchBig DataA term for a collection of data that are very large and complex so that it is difficult to process and analyze using on-hand database management tools,traditional data processing methods and analysis methodologies.(Wikipedia)ZB(1021),EB(1018),PB(1015),TB(1012),GB(109),MB(106)Big Data:Opportunities and ChallengesWhy difficulty?Big data challenges the existing information technologies,management paradigm,statistical and computa-tional sciences.VolumeBig Data:Opportunities and Challengesl PBZB in scalel Distributed storage and processing necessaryl Growing tremendouslyl Data flowl Multisource,correlated,heterogeneousl Unstructured,unreliable,inconsistent.lTotal dataset embodies great valuel Individual or small subset contains less informationVelocityVarietyValueWhat opportunities：Big data embody great values that might not be explored in small sized data.Scientific ResearchesHigh-energy physicsAstronomyLife scienceGeosciences and remote sensingSocial GovernanceBusinessNew chance of getting benefit/incomesValuable customer findingMarketingBig Data:Opportunities and ChallengesThe fourth paradigm of researchA systematic approach uniquely applicable to modern management(Jims Gray)Big data view of assessing public policiesManagement ScienceBig data research:A real inter/multidisciplinary activities.Data acquisition&data managementData storage&processingData understandingApplicationsMath and StatisticsInformation ScienceEngineeringslFundamentallChallenge 1Big Data:Opportunities and ChallengeslFundamentallChallenge 2lFundamentallChallenge 3lFundamentallChallenge 4Management ScienceBig data research:A real inter/multidisciplinary activities.Data acquisition&data managementData storage&processingData understandingApplicationsMath and statisticsInformation ScienceEngineeringslFundamentallChallenge 1Challenges 1:Data Resource Management&Public PoliciesAcquisition;Quality;Standard;Sharing;Privacy protection;Safety;Data-driven managementBig Data:Opportunities and ChallengeslFundamentallChallenge 2lFundamentallChallenge 3lFundamentallChallenge 4Architecture;System/Software/Algorithm;Scalability/Complexity;Real time processingChallenges 2:IT&Science for Big DataRepresentation(Uniform scheme;Complexity);Modeling(Parent space identification;sampling);Mining(Clustering;Classification;Regression;Prediction;Variable Selection);Analytics(Relevance Analysis;Latent variable analytics;Statistical inference);Computation(Subsampling;Complexity;Distributed computation)Challenges 3:Statistics&Computation for Big Data AnalyticsHighly domain-specific;Any data-driven fields(Social media based;Trade data based;Record(Survey,Observation)based;Empirical data based;Experimental data based)Challenges 4:Big Data EngineeringsManagement ScienceBig data research:A real inter/multidisciplinary activities.Data acquisition&data managementData storage&processingData understandingApplicationsMath and statisticsBig Data Industry(Value chain management,Business pattern,)Information ScienceEngineeringslFundamentallChallenge 1Big Data:Opportunities and ChallengeslFundamentallChallenge 2lFundamentallChallenge 3lFundamentallChallenge 4OutlinelBig Data:Opportunities and ChallengeslSome More Scientific Problems in Big Data Analysis and ProcessinglSome Advances on Big Data ResearchHigh dimensionality problem：The number of features(p)is far larger than the sample size(n),and n varies with p(n=n(p)Classical Classical：npnp;High-DHigh-D：pnpn;Big dataBig data：pn(p)pn(p).Solution Asymptotical normalityProblem 1:High DimensionalityLinear model:Data：Matrix form:Core open questionslHow to add priors so that a high-D problem can be well defined?lSparse modelinglHigh-D statisticslHigh-D data mining(clustering stability ,classification consistency)lHot Issues：Sparse modeling(compressed sensing;low rank decomposition of matrix;sparse learning）Problem 1:High DimensionalitySub-sampling problem:A big data set has to be processed by some types of divide-and-conquer schemes,like Hadoop system.The Big Data Bootstrap.Kleiner et.al.2012 ICML Problem 2:Sub-samplingX X1 1X X2 2X X3 3X Xn nMap(random sub-sampling)D1DkDm.Reduce(aggregation)DIntermediate solution f1Intermediate solution f2Intermediate solution fmFinal estimation f*Problem 2:Sub-samplingD1TransitivityTransitivity Core open questionslHow to sub-sampling/aggregate so that the final f*models properly D lIs distributed processing feasible?lHow about traditional sub-sampling technologies work?lSub-sampling axiom(Similarity;Transitivity,)D2D3Problem 3:Computational ComplexityComputational Complexity Problems：Traditionally,computational complexity concerns with how difficult a problem can be solved,or how much computation cost must be paid an algorithm to solve a problem.Traditional settingBig data settingProblem 3:Computational ComplexityD1D2D3ExchangeProcessing Core open questionslHow to properly define complexity in big data setting?lEasy or difficult,a given big data problem?lHow to establish complexity theory for some specific types of big data problems?lFlow data Dti (easy Ati(Dti)yields Rti withinti=ti+1-ti)lDistributed processing (easy processing time data exchange time)Real&distributed computation problem:Parallel and distri-buted processing are necessary,perhaps become uniquely available way of processing for big data.The main challenges come from:Problem 4:R/D ComputationHDFSHBaseMapReduceHadooplReal timelFeasibilitylEfficiencylScalabilityNew D2D1D1+D2Xu et.al.Efficiency speed-up for evolutionary computation Fundamentals and Fast-Gas.AMC 2003Code Core open questionslThe IT for supporting fast storage/reading/ranking.?lProblem decomposability:Can and how a data modeling problem be decomposed into a series of sub-data set dependent problems?lSolution assemblies:How can the solution of a problem be assembled with its sub-solution(component solutions)?lDifficult or easy of a specific data flow computation problem?Problem 4:R/D ComputationProblem 5:Unstructured Processing Unstructured data processing problems:Structured data are those that can be represented with finite number of rules and can be processed within acceptable time;Otherwise,unstructured.The main challenge:(Structured data)lMultisourcedlHeterogeneouslUnderstanding:cognition dependent(Unstructured data)UnstructureddatatextImageVideoUnified processing platformDecision：Problem 5:Unstructured Processing Core open questionslHow to build a uniform platform on How to build a uniform platform on which different types of unstructured which different types of unstructured data can be processed simultaneouslydata can be processed simultaneouslylHow to develop the cognition How to develop the cognition consistent approaches for consistent approaches for unstructured data modeling?unstructured data modeling?Problem 6:VisualizationVisualization analysis：Using visual-consistent figures or graphics to exhibit the intrinsic structure and patterns in high dimensional big data.A basic tool for human-machine interface and expanding applications.Data space(H-d)Feature Space(L-d)VisualizationVisualized space（2d）FacebookWordleWhisperFeature extractionProblem 6:VisualizationMicrosoft T-drive Yuan et al.,2010 Core open questionslEssential feature extraction of H-d data(dimension-reduction)?lStructured representation of imaginal thinking?lHow to construct appropriate visualized space?lHow to map a problem in feature space(Data space)to a representation problem in visualized space?OutlinelBig Data:Opportunities and ChallengeslSome More Scientific Problems in Big Data Analysis and ProcessinglSome Advances on Big Data Research(1)HighDimensionality Problem -Sparse Modeling -Clustering Stability(2)R/D Computation Problem -Feasibility of Hadoop-based Algorithms -Unveiling Traffic Anomalies(3)Unstructured Data Processing -Visual Clustering Machine Some Advances in My GroupSparsity(of x):There exists a characteristic quantity q(x)such that q(x)is of singularity(i.e.,smaller than the normal).(1)H-d problem:Sparse modeling1st order:2nd order:3rd order:l Unique Solvability Theory(Signal recovery)RIP:for L0(Candes&Tao,2006);for Lq(Cai&Zhang,2013;Wang et.al,2013)Coherence:for L1(Donoho&Elad,2003)l Thresholding Representation Theory(1)H-d problem:Sparse modeling is analytically expressible only if is analytically expressible only if (Xu,2010;Xu et.al,2012;Zeng et.al 2014)Theoriesl Xu ZB,Data modeling:Visual Psychology Approach and L(1/2)Regularization Theory,Proceeding of ICM,2010l Xu et.al,L(1/2)Regularization:A Thresholding Representation Theory and A Fast Solver,IEEE TNNLS,2012l Zeng et.al,L(1/2)Regularization:Convergence of Iterative Half Thresholding Algorithm,IEEE TSP,2014;(1)H-d problem:Sparse modelinglFrom linear to nonlinearlFrom 1st ordet to higher order lFrom unconstrained to constrainedlGreedy-type:OMP(Tropp,2006),CoSaMp(Deedell&Tropp,2009),SP(Dai,2009)lConvex-type:Linear programming(Candes et.al,2006),FPC(Yin et.al,2008),FISTA(Beck et.al,2009)lNonconvex-type:Reweigted L1(Candes et.al,2008),IRLS(Daubechies et.al,2010)Half thresholding(Xu et.al,2012),Smoothing(Chen et.al,2013)AlgorithmsExtensionsClustering:Categorize a data set into subgroups according to data similarity;The basis of pattern recognition.(1)H-d problem:Clustering stabilityTraditional K-means：H-d setting：Given a data flowlVariable dimension(pt)lVariable sample size n(pt)lCt C*(Consistency+Stability)New Challenges:(1)H-d problem:Clustering stabilityNew Modeling (Feature decomposable)New Concept(Optimal Clustering)New Theory:If the data flow are mixture Gaussian distributed,then 1)The sparse K-Means is consistent2)The optimal solution is stable (Chang,Lin&Xu,Sparse K-Means via l/l0 Penalty for High-dimensional Data Clustering,2014.)Regression：Find an estimation for the correspondence between input(X)and output(Y)based on finite number of observations S=(xi,yi),i=1,n.(2)R&D computation problem -Feasibility of Hadoop-based regressionTraditional approach:RERMModel:Theory:(Regression function)based on the fact the hypothesis error:Big Data Setting:S is too big to process in a central computer.Then the distributed processing has to be made.Global Machine.Local Machines(2)R&D computation problem -Feasibility of Hadoop-based regressionHydoop-based regression：Step 1New Challenge:hypothesis errorStep 2S1S2S3SmSNew methodology：Using the random sampling equality to estimate the hypo-thesis error(Random sampling equality quantifies the fact that a differentiable function cannot attain its large values anywhere if its derivatives are bounded on a sufficiently dense discrete set).(2)R&D computation problem -Feasibility of Hadoop-based regressionFeasibility Theory：Under certain conditions,the Hydoop-based regression algorithm is feasible in the sense of consistency(Chang&Xu,Distributed Regression for Big Data:A Feasibility Theory,ICML 2014)Unveiling Traffic Anomalies:Traffic anomalies monitoring is a typical flow big data problem,which needs real time processing.(2)R&D computation problem -Unveiling Traffic AnomaliesTopology of IP NetworkAnomaly Matrix：ATraffic Matrix：ZLLA-LADM LLA-LADM Algorithm is used to solve the Algorithm is used to solve the above model.above model.(2)R&D computation problem -Unveiling Traffic Anomalies2nd order sparsity modellAbilene IP NetworkData:http:/internet2.edu/observatory/achive/data-collections.html11 nodes，41 links，121 OD flowsone-week period：2003/11/8-2003/11/145-minute intervals,T=2016(2)R&D computation problem -Unveiling Traffic AnomaliesCore Idea:View a data modeling problem as a cognition problem,and solve the problem by simulating visual psychology principles.We develop the model in low-dimension through visual intuition and transmit it to high-dimension by mathematical induction.(Leung&Xu,IEEE TPAMI,2000)regression clustering Traditional approach:data structure-basedNew approach:cognition-basedWhy can I recognize it so easily?classification (3)Unstructured Problem -Visual Clustering Machine A Basic Visual Principle:The distribution of light strength reaching at retina is controlled by the distance between the object and retina,or the curvature of crystalline lens.Visual imaging system at retina levelRetina levelVisual Cortex level(3)Unstructured problem -Visual Clustering Machine Scale Space Representation:View the distance or curvature of lens as the scale,the image,i.e.,the light strength,of an object can be represented in multiple scales Witkin,IJCAI,1983;Perona,PAMI,1990.Let denote the light strengths distribution of an object in real world,and be its distance to the retina,then the projected image on the retina is modeled asLinear diffusion modelMultiscale representation of Lena image with increasing nonlinear diffusion model:(3)Unstructured Problems -Visual Clustering MachineData image(data):Multi-scale representation:=0.2=1.0Multi-scale evolution：Scale Space Clustering:View a datum as a light point,and the data set as an image,then we observe the clustering structures from the multi-scale representation of the data image Leung,Zhang&Xu,IEEE Trans.PAMI,2000.Data set=2.0(3)Unstructured Problems -Visual Clustering MachineA blobCentroid:Gradient flow:300 clusters:0.023 clusters:1 cluster:What is blob?A light blob is a cluster.It corresponds to a set of data,starting from which the same local maximum is reached.(3)Unstructured Problems -Visual Clustering Machine3 basic problemsStep 1.Given a set of scales with .At ,each datum is a cluster center and its blob center is itself.Let .Step 2.Find the new blob center at for each blob center at scale by discretization scheme.Merge the clusters whose blob centers arrive at the same blob center into a new cluster.Step 3.If there are more than two clusters,let ,go to step 2.A hierarchical clustering procedure How to discretize scale?What is real clustering?Does clusters monotonically evolve?(3)Unstructured Problems -Visual Clustering MachineData image Hierarchical clustering How to discretize scale?,is Webers constant(Webers law)in psychophysics Weber,1834.scale(3)Unstructured Problems -Visual Clustering MachinelDoes clusters monotonically evolve?We have proved that the number of cluster centers is monotonically and regularly decreasing.lWhat is real clustering?Through defining the lifetime of a cluster,we provided a cognition based solution for“what is real clustering?”Hierachical clustering Lifetime curve(3)Unstructured Problems -Visual Clustering MachineApplication in image segmentationSSC:scale space based clusteringNcut:normalized cut algorithm Shi&Malik,PAMI,2000Input imagesGround-truthVClustSSCNcutMean-shift(3)Unstructured Problems -Visual Clustering MachineExtensive Applications：nGeographic data analysis（Lans research group in University of Geogia);nImage processing（DeMenthon research gr