数据分析

来自iCenter Wiki
跳转至： 导航、 搜索

数据分析

数据分析是一类统计方法，其主要特点是多维性和描述性。有些几何方法有助于揭示不同的数据之间存在的关系，并绘制出统计信息图，以更简洁的解释这些数据中包含的主要信息。其他一些用于收集数据，以便弄清哪些是同质的，从而更好地了解数据。数据分析是数学与计算机科学相结合的产物。

数据解析（Data Analytic），是指对数据集（DataSet）的属性值进行统计，以发现有用的信息。

  • Data analysis/Data mining

https://en.wikipedia.org/wiki/Data_analysis.

Data analysis is a process of inspecting, cleansing, transforming, and modeling data with the goal of discovering useful information, informing conclusions, and supporting decision-making. Data analysis has multiple facets and approaches, encompassing diverse techniques under a variety of names, while being used in different business, science, and social science domains.

Data mining is a particular data analysis technique that focuses on modeling and knowledge discovery for predictive rather than purely descriptive purposes, while business intelligence covers data analysis that relies heavily on aggregation, focusing mainly on business information.

  • Data Analytic

Data Analytics is the "extensive use of data, statistical and quantitative analysis, explanatory and predictive models, and fact-based management to drive decisions and actions." It is a subset of business intelligence, which is a set of technologies and processes that use data to understand and analyze business performance.

Data Analytics is the discovery, interpretation, and communication of meaningful patterns in data. Especially valuable in areas rich with recorded information, analytics relies on the simultaneous application of statistics, computer programming and operations research to quantify performance.

https://en.wikipedia.org/wiki/Analytics.

数据分析的算法

频繁项目集发现

查找频繁项目集ItemSets。其中最有名的算法是A-Priori算法。

从数据集中抽取频繁集，抽取的结果往往采用if-then 形式的规则集合来表示，这些规则被称为关联规则（association rule）。频繁项目集发现常常被看成关联规则挖掘（association rule mining）或关联规则发现。

基于位图的PCY算法。

  1. Park, Jong Soo, Ming-Syan Chen, and Philip S. Yu. An effective hash-based algorithm for mining association rules. ACM Sigmod 1995.

基于位图的A-Priori算法加速。

  1. Sung-Tan Kim et al., "BAR: bitmap-based association rule: an implementation and its optimizations." ACM MoMM 2009.

对比度设置学习

对比度设置学习（对比集分析）是一种关联规则的学习 ，旨在找出有意义的不同的群体之间的差异，通过逆向工程的关键预测指标，确定每一个特定的组。

基于位图的对比集挖掘算法加速。

  1. Gangyi Zhu et al., SciCSM: Novel Contrast Set Mining over Scientific Datasets Using Bitmap Indices, SSDBM 2015.

独立元素计数

FM（Flajolet-Martin）算法

  1. Flajolet, Philippe, and G. Nigel Martin. "Probabilistic counting algorithms for data base applications." FoCS 1983.


窗口内计数问题

DGIM（Datar-Gionis-Indyk-Motwani）算法

  1. Datar, M., Gionis, A., Indyk, P., & Motwani, R. (2002). Maintaining stream statistics over sliding windows. SIAM journal on computing, 31(6), 1794-1813.

基数预估

基数预估或估计（Cardinality Estimation），评估一个集合中不同数据项的个数的近似算法。比如，访问一个网站的独立IP个数。

基数预估主要研究如何统计一组数据中不同元素的个数。这看似是一个简单的工作，当时当数据量达到亿级时，想要在所有情况下短时间准确计算出不同元素个数是十分困难的。但是这在构造索引表的初始地址申请估计中有一些作用。同时在大数据时代的今天，高效地处理海量的数据也是十分必要的，而已有的算法hyperloglog给出了一个合理的回答，它能够较为准确地估计出不同元素的个数同时仅用少量的存储空间。

注意到对于一个[0,1]均匀分布，如果随机抽取n个点，那么期望下最小点的值为1/n。这给出了对于基数的一个可行估计，即可以通过求出所有值的最小值m,估计n为1/m。利用这个思想可以先通过hash函数来在保持数据重复性不变的情况下，保证数据的均匀随机性，之后即可应用这种方法完成估计。在实际中可以应用另一种方法——分析每个数据中结尾连续0的数目，以该连续数目最大值的2的幂次进行估计。

为进一步细化估计，可以采用将数据的值域分成若干小区间，对于每个小区叫分析，最后再合并。合并不是简单的合并，常规方法是求算术平均数，而hyperloglog却采用求调和平均数的方式并辅以常数的修正来完成组合。

注意到在中估计下如果基数太大或者太小都会严重影响结果的准确性，hyperloglog对此进行了处理。当划分后的值域小区域无法被大部分填满后，就可以利用填满的值域小区域的数目对结果进行估计，当每个小区域都被大量填满后，就需要对结果进行一定程度的修正。

利用这种方法可以利用极少的空间资源完成对海量数据的操作，因为主要的空间用于划分的值域小区域，而只需要很少的值域小区间就可以使得结果与准确解之间的差距被控制在可以接受的范围内。


  1. Flajolet, Philippe, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. "Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm." DMTCS Proceedings 1 (2008).
  2. Heule, Stefan, Marc Nunkesser, and Alexander Hall. "HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm." In Proceedings of the 16th International Conference on Extending Database Technology, pp. 683-692. ACM, 2013.

统计频率算法

问题：Frequency Estimation, 估计某个element重复出现次数, 比如, 某个用户对网站访问次数

  • Count-Min Sketch 算法

前面要求不需要精确的计数，Count-Min Sketch 就是用来解决此类问题的算法。

这个算法的技巧是：不存储所有的不同的元素，只存储它们Sketch的计数。

  • 基本的思路

创建一个长度为 x 的数组，用来计数，初始化每个元素的计数值为 0；

对于一个新来的元素，哈希到 0 到 x 之间的一个数，比如哈希值为 i，作为数组的位置索引；

这是，数组对应的位置索引 i 的计数值加 1；

那么，这时要查询某个元素出现的频率，只要简单的返回这个元素哈希望后对应的数组的位置索引的计数值即可。

  • 如何优化？

使用多个数组，和多个哈希函数，来计算一个元素对应的数组的位置索引；

那么，要查询某个元素的频率时，返回这个元素在不同数组中的计数值中的最小值即可。

改进的算法比原始的算法精确多了，但还是会有冲突，但是冲突少多了。

  • 算法评价

只会估算偏大，永远不会偏小；

只需要固定大小的内存和计算时间，和需要统计的元素多少无关；

对于低频的元素，估算值相对的错误可能会很大。

这个其实就是bloom过滤器在统计方面的变型。

  1. Cormode, Graham, and Shan Muthukrishnan. "An improved data stream summary: the count-min sketch and its applications." Journal of Algorithms 55.1 (2005): 58-75.

聚类（Clustering）

聚类是对点集按照某种距离测度将它们聚成多个簇的过程。聚类目标是使得同一簇内的点之间距离较短，而不同的簇中的点之间距离较大。

一般把数据聚类归纳为一种非监督式学习。

距离测量

  • K-均值聚类方法
  • 基于密度的聚类方法（DBSCAN）
  • 均值漂移聚类（MeanShift）
  • 用高斯混合模型（GMM）的最大期望（EM）聚类
  • 凝聚式层次聚类（HAC, Hierarchical Agglomerative Clustering）
  • 图团体检测（Graph Community Detection）

相关性挖掘

相关性测度（Correlation Metrics ）

地球移动距离（Earth Mover's Distance, EMD）

香农熵（Shannon's Entropy）

互信息（Mutual Information）

条件熵（Conditional Entropy）


相关性挖掘（Correlation Mining）

相关性分析位图索引加速。

  1. Yu Su et al., In-Situ Bitmaps Generation and Efficient Data Analysis based on Bitmaps, HPDC 2015.


子群发现（subgroup mining）

基于位图索引的子群发现方法加速。

  1. Yi Wang et al., SciSD: Novel Subgroup Discovery Over Scientific Datasets Using Bitmap Indices, #OSU-CISRC-3/15-TR03, March 2015.


参考教材

  1. Leskovec, Jure, Anand Rajaraman, and Jeffrey David Ullman. Mining of massive datasets. Cambridge University Press, 2014. MMDS_book
  • 基于概率的数据结构

大数据处理中基于概率的数据结构，https://www.cnblogs.com/fxjwind/p/3289221.html

https://highlyscalable.wordpress.com/2012/05/01/probabilistic-structures-web-analytics-data-mining/

  • 基数估计算法

解读Cardinality Estimation算法（第一部分：基本概念）, http://blog.codinglabs.org/articles/algorithms-for-cardinality-estimation-part-i.html

解读Cardinality Estimation算法（第二部分：Linear Counting）, http://blog.codinglabs.org/articles/algorithms-for-cardinality-estimation-part-ii.html

解读Cardinality Estimation算法（第三部分：LogLog Counting）, http://blog.codinglabs.org/articles/algorithms-for-cardinality-estimation-part-iii.html

解读Cardinality Estimation算法（第四部分：HyperLogLog Counting及Adaptive Counting）, http://blog.codinglabs.org/articles/algorithms-for-cardinality-estimation-part-iv.html

取自“http://wiki.icenter.tsinghua.edu.cn/icenterwiki/index.php?title=数据分析&oldid=49807”