Daniel Stanley Tan edited untitled.tex  about 8 years ago

Commit id: efcfb78dc0bfb82a7e82154b4de1847de83ec0c5

deletions | additions      

       

Some existing ways to visualize high-dimensional data are through dimensionality reduction techniques like Random Projections \cite{bingham2001random,kaski1998dimensionality}, Self Organizing Maps (SOM) \cite{kohonen1990self}, Multidimensional Scaling (MDS) \cite{kruskal1964multidimensional} and Principal Components Analysis (PCA) \cite{dunteman1989principal} which significantly reduce the dimensions by mapping high dimensional data into lower dimensions. This mapping inevitably loses information but these algorithms are creative in doing this in such a way that useful distances are preserved and information loss is minimized. The only problem is that the time complexity of these algorithms are exponential which is not suitable for handling big data. Parallelizable implementations of SOM \cite{carpenter1987massively}, MDS \cite{varoneckas2015parallel} and PCA \cite{andrecut2009parallel} exist but it only reduces the complexity by a linear factor, which may be good for now but it won't scale well for the future.   Clustering is another technique used in data mining. For big data, the clustering algorithm needs to run in at least most  quasilinear time. There are many clustering algorithms that can do this such as BIRCH \cite{zhang1996birch}, FCM \cite{bezdek1984fcm}, DBSCAN \cite{ester1996density}, EM \cite{dempster1977maximum}, and OPTICS \cite{ankerst1999optics} to name a few. BFR (Bradley-Fayyad-Reina) \cite{bradley1998scaling} and CLIQUE \cite{agrawal1998automatic} seems promising for the task of big data visualization. BFR (Bradley-Fayyad-Reina) algorithm is a variant of K-Means that can handle large data. The idea is that if we assume the clusters to be normally distributed then we can summarize the clusters using its mean and standard deviation, effectively reducing the number of data points to be processed in the succeeding iterations. The notion of summarizing the data points and creatively reducing the number of data points may be applied to visualization to increase the speed with minimal loss of information. CLIQUE on the other hand is a subspace clustering algorithm, it looks for clusters in subsets of the dimensions. This may be useful in reducing the number of dimensions and also in revealing patterns that may be hidden due to the inclusion of some dimensions.