大数据研究(英文)课件.pptx
Exploring Big Data Analysis:Fundamental Scientific Problems,Outline,Big Data:Opportunities and ChallengesSome More Scientific Problems in Big Data Analysis and ProcessingSome Advances on Big Data Research,Big 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 Challenges,Why difficulty?Big data challenges the existing information technologies,management paradigm,statistical and computa-tional sciences.,Volume,Big Data:Opportunities and Challenges,PBZB in scale Distributed storage and processing necessary,Growing tremendously Data flow,Multisource,correlated,heterogeneous Unstructured,unreliable,inconsistent.,Total dataset embodies great value Individual or small subset contains less information,Velocity,Variety,Value,What opportunities：Big data embody great values that might not be explored in small sized data.,Scientific Researches,High-energy physicsAstronomyLife scienceGeosciences and remote sensing,Social Governance,Business,New chance of getting benefit/incomesValuable customer findingMarketing,Big Data:Opportunities and Challenges,The fourth paradigm of researchA systematic approach uniquely applicable to modern management(Jims Gray)Big data view of assessing public policies,Management Science,Big data research:A real inter/multidisciplinary activities.,Data acquisition&data management,Data assess&processing,Data understanding,Applications,Math and Statistics,Information Science,Engineerings,FundamentalChallenge 1,Big Data:Opportunities and Challenges,FundamentalChallenge 2,FundamentalChallenge 3,FundamentalChallenge 4,Management Science,Big data research:A real inter/multidisciplinary activities.,Data acquisition&data management,Data assess&processing,Data understanding,Applications,Math and statistics,Information Science,Engineerings,FundamentalChallenge 1,Big Data:Opportunities and Challenges,FundamentalChallenge 2,FundamentalChallenge 3,FundamentalChallenge 4,Management Science,Big data research:A real inter/multidisciplinary activities.,Data acquisition&data management,Data assess&processing,Data understanding,Applications,Math and statistics,Information Science,Engineerings,FundamentalChallenge 1,Big Data:Opportunities and Challenges,FundamentalChallenge 2,FundamentalChallenge 3,FundamentalChallenge 4,Outline,Big Data:Opportunities and ChallengesSome More Scientific Problems in Big Data Analysis and ProcessingSome Advances on Big Data Research,High dimensionality problem：The number of features(p)is far larger than the sample size(n),and n varies with p(n=n(p)Classical：np;High-D：pn;Big data：pn(p).,Solution Asymptotical normality,Problem 1:High Dimensionality,Linear model:,Data：,Matrix form:,Core open questions,How to add priors so that a high-D problem can be well defined?Sparse modelingHigh-D statisticsHigh-D data mining(clustering stability,classification consistency),Hot Issues：Sparse modeling(compressed sensing;low rank decomposition of matrix;sparse learning）,Problem 1:High Dimensionality,Sub-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-sampling,X1X2X3Xn,Map(random sub-sampling),D1,Dk,Dm,.,.,Reduce(aggregation),D,Intermediate solution f1,Intermediate solution f2,Intermediate solution fm,Final estimation f*,Problem 2:Sub-sampling,D1,Transitivity,Core open questions,How to sub-sampling/aggregate so that the final f*models properly D?Is distributed processing feasible?How about traditional sub-sampling technologies work?Sub-sampling axiom(Similarity;Transitivity,),D2,D3,Problem 3:Computational Complexity,Computational Complexity Problems：Traditionally,computational complexity concerns with how difficult a problem can be solved,or how much computation cost must be paid an algorithm solves a problem.,Traditional settingBig data setting,Problem 3:Computational Complexity,D1,D2,D3,Exchange,Processing,Core open questions,How to properly define complexity in big data setting?Easy or difficult,a given big data problem?How to establish complexity theory for some specific types of big data problems?Flow data Dti(easy Ati(Dti)yields Rti withinti=ti+1-ti)Distributed 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 Computation,HDFS,HBase,MapReduce,Hadoop,Real timeFeasibilityEfficiencyScalability,Xu et.al.Efficiency speed-up for evolutionary computation Fundamentals and Fast-Gas.AMC 2003,Code,Core open questions,The IT for supporting fast storage/reading/ranking.?Problem decomposability:Can and how a data modeling problem be decomposed into a series of sub-data set dependent problems?Solution assemblies:How can the solution of a problem be assembled with its sub-solution(component solutions)?Difficult or easy of a specific data flow computation problem?,Problem 4:R/D Computation,Problem 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),MultisourcedHeterogeneousUnderstanding:cognition dependent,(Unstructured data),Problem 5:Unstructured Processing,Core open questions,How to build a uniform platform on which different types of unstructured data can be processed simultaneouslyHow to develop the cognition consistent approaches for unstructured data modeling?,Problem 6:Visualization,Visualization 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),Visualization,Visualized space（2d）,Facebook,Wordle,Whisper,Feature extraction,Problem 6:Visualization,Microsoft T-drive Yuan et al.,2010,Core open questions,Essential feature extraction of H-d data(dimension-reduction)?Structured representation of imaginal thinking?How to construct appropriate visualized space?How to map a problem in feature space(Data space)to a representation problem in visualized space?,Outline,Big Data:Opportunities and ChallengesSome More Scientific Problems in Big Data Analysis and ProcessingSome 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 Group,Sparsity(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 modeling,1st order:,2nd order:,3rd order:,Unique Solvability Theory(Signal recovery)RIP:for L0(Candes Wang et.al,2013)Coherence:for L1(Donoho&Elad,2003)Thresholding Representation Theory,(1)H-d problem:Sparse modeling,is analytically expressible only if(Xu,2010;Xu et.al,2012;Zeng et.al 2014),Theories,Xu ZB,Data modeling:Visual Psychology Approach and L(1/2)Regularization Theory,Proceeding of ICM,2010 Xu et.al,L(1/2)Regularization:A Thresholding Representation Theory and A Fast Solver,IEEE TNNLS,2012 Zeng et.al,L(1/2)Regularization:Convergence of Iterative Half Thresholding Algorithm,IEEE TSP,2014;,(1)H-d problem:Sparse modeling,From linear to nonlinearFrom 1st ordet to higher order From unconstrained to constrained,Greedy-type:OMP(Tropp,2006),CoSaMp(Deedell&Tropp,2009),SP(Dai,2009)Convex-type:Linear programming(Candes et.al,2006),FPC(Yin et.al,2008),FISTA(Beck et.al,2009)Nonconvex-type:Reweigted L1(Candes et.al,2008),IRLS(Daubechies et.al,2010)Half thresholding(Xu et.al,2012),Smoothing(Chen et.al,2013),Algorithms,Extensions,Clustering:Categorize a data set into subgroups according to data similarity;The basis of pattern recognition.,(1)H-d problem:Clustering stability,Traditional K-means：,H-d setting：Given a data flow,Variable dimension(pt)Variable sample size n(pt)Ct C*(Consistency+Stability),New Challenges:,(1)H-d problem:Clustering stability,New Modeling(Feature decomposable),New Concept(Optimal Clustering),New Theory:If the data flow are mixture Gaussian distributed,then The sparse K-Means is consistentThe 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 regression,Traditional approach:RERM,Model:,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.,(2)R&D computation problem-Feasibility of Hadoop-based regression,Hydoop-based regression：,Step 1,New Challenge:hypothesis error,Step 2,S1,S2,S3,Sm,S,New methodology：Using the random sampling inequality to estimate the hypo-thesis error(Random sampling inequality 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 regression,Feasibility 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 Anomalies,Topology of IP Network,Anomaly Matrix：A,Traffic Matrix：Z,LLA-LADM Algorithm is used to solve the above model.,(2)R&D computation problem-Unveiling Traffic Anomalies,2nd order sparsity model,Abilene IP Network,Data:http:/internet2.edu/observatory/achive/data-collections.html,11 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 Anomalies,Core 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-based,New approach:cognition-based,Why 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 level,Retina level,Visual 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 as,Multiscale representation of Lena image with increasing,(3)Unstructured Problems-Visual Clustering Machine,Data image(data):,Multi-scale representation:,=0.2,=1.0,Multi-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 Machine,A blob,Centroid:,Gradient flow:,300 clusters:0.02,3 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 Machine,3 basic problems,Step 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 Machine,Data image,Hierarchical clustering,How to discretize scale?,is Webers constant(Webers law)in psychophysics Weber,1834.,scale,(3)Unstructured Problems-Visual Clustering Machine,Does clusters monotonically evolve?We have proved that the number of cluster centers is monotonically and regularly decreasing.What 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 Machine,Application in image segmentation,SSC:scale space based clusteringNcut:normalized cut algorithm Shi&Malik,PAMI,2000,Input images,Ground-truth,VClust,SSC,Ncut,Mean-shift,(3)Unstructured Problems-Visual Clustering Machine,Extensive Applications：Geographic data analysis（Lans research group in University of Geogia);Image processing（DeMenthon research group in University of Maryland）;Protein analysis（Leherte group in Namur University）;GAMAX system in Environment and Geography Information Lab of Chinese Academy of Sciences.,Analysis for protein,Application to image segmentation,Mean Shift Dorin Comaniciu,IEEE Trans.PAMI,2002,(3)Unstructured Problems-Visual Clustering Machine,Concluding Remarks,Big data era is coming,brings various opportunities and severe challenges.Big data research is really inter/multi-disciplinary.4 fundamental scientific themes are proposed.6 more specific scientific problems are suggested for big data analysis,and some advances are reported.Big data research must make difference,Thanks,
