Larg-Scale Data Analytics: Methodologies and Applications

大规模数据分析：方法和应用

• 批准号: RGPIN-2014-05721
• 负责人: Ghodsi, Ali
• 金额: $ 1.46万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=635100
• 关键词: Larg; Scale; Data; Analytics; Methodologies

Recent years have witnessed the rise of the big data era in computing and storage systems. With the great advances in information and communication technology, hundreds of petabytes of data are generated, transferred, processed and stored every day. The availability of this overwhelming amount of structured and unstructured data creates an acute need to develop fast and accurate algorithms to discover useful information that is hidden in big data. One of the crucial problems in the big data era is the ability to represent the data and its underlying information in a succinct and interpretable format. Although different algorithms for clustering and dimensionality reduction can be used to summarize big data, these algorithms tend to learn representations whose meanings are difficult to interpret. For instance, the traditional clustering algorithms such as k-means tend to produce centroids which encode information about thousands of data instances, but the meanings of these centroids are hard to interpret. Even clustering methods that use data instances as prototypes, such as k-medoid, learn only one representative for each of the resulting clusters; these alone are not sufficient to capture the insights of the data instances in this cluster. In addition, using medoids as representatives implicitly assumes that the data points are distributed as clusters and that the number of those clusters is known ahead of time. This assumption is not true for all data sets. On the other hand, traditional dimensionality reduction algorithms such as Latent Semantic Analysis (LSA) tend to learn a few latent concepts in the feature space. Each of these concepts is represented by a dense vector which combines thousands of features with positive and negative weights. This makes it difficult for the data analyst to understand the meaning of these concepts. Even if the goal of representative selection is to learn a low-dimension embedding of data instances, learning dimensions whose meanings are easy to interpret allows the understanding of the results of data mining and machine learning algorithms, such as understanding the meanings of data clusters in the low-dimensional space. The acute need to summarize big data to a format that is informative for data analysts motivates the development of new algorithms to directly select a few representative data instances and/or features. This problem can be generally formulated as the selection of a subset of columns from a data matrix, which is formally known as the Column Subset Selection (CSS) problem. Although many algorithms have been proposed for tackling the CSS problem, most of these algorithms focus on randomly selecting a subset of columns with the goal of using these columns to obtain a low-rank approximation of the data matrix. In this case, these algorithms tend to select a relatively large number of columns. When the goal is to select a very few columns to be directly presented to a data analyst or indirectly used to interpret the results of other algorithms, the randomized CSS methods do not produce a meaningful subset of columns. On the other hand, deterministic algorithms for CSS, although more accurate, do not scale to work on big matrices with massively-distributed columns. We propose to address these limitations by developing a new framework that we call Data Downdate. A large variety of important problems in machine learning and data mining such as variable selection, mining representative patterns, and most notably sparse approximation are all special cases of this framework.

近年来，计算和存储系统见证了大数据时代的兴起。随着信息和通信技术的巨大进步，每天生成、传输、处理和存储数百PB的数据。如此大量的结构化和非结构化数据的可用性迫切需要开发快速、准确的算法来发现隐藏在大数据中的有用信息。大数据时代的关键问题之一是以简洁且可解释的格式表示数据及其底层信息的能力。尽管可以使用不同的聚类和降维算法来总结大数据，但这些算法往往会学习其含义难以解释的表示。例如，传统的聚类算法（例如 k 均值）往往会生成对数千个数据实例的信息进行编码的质心，但这些质心的含义很难解释。即使使用数据实例作为原型的聚类方法（例如 k-medoid）也只能为每个结果聚类学习一个代表；仅这些不足以捕获该集群中数据实例的见解。此外，使用中心点作为代表隐式假设数据点作为簇分布，并且这些簇的数量是提前已知的。该假设并不适用于所有数据集。另一方面，传统的降维算法（例如潜在语义分析（LSA））倾向于学习特征空间中的一些潜在概念。这些概念中的每一个都由一个密集向量表示，该向量结合了数千个具有正权重和负权重的特征。这使得数据分析师很难理解这些概念的含义。即使代表性选择的目标是学习数据实例的低维嵌入，但易于解释含义的学习维度可以帮助理解数据挖掘和机器学习算法的结果，例如理解低维空间中数据簇的含义。将大数据总结为可为数据分析师提供信息的格式的迫切需求促使开发新算法来直接选择一些代表性的数据实例和/或特征。该问题通常可以表述为从数据矩阵中选择列子集，正式名称为列子集选择 (CSS) 问题。尽管已经提出了许多算法来解决 CSS 问题，但大多数算法都专注于随机选择列的子集，目的是使用这些列来获得数据矩阵的低秩近似。在这种情况下，这些算法往往会选择相对较多的列。当目标是选择极少数列直接呈现给数据分析师或间接用于解释其他算法的结果时，随机 CSS 方法不会生成有意义的列子集。另一方面，CSS 的确定性算法虽然更准确，但无法扩展到具有大规模分布列的大型矩阵。我们建议通过开发一个称为 Data Downdate 的新框架来解决这些限制。机器学习和数据挖掘中的各种重要问题，例如变量选择、挖掘代表性模式，以及最著名的稀疏逼近，都是该框架的特例。