流式数据挖掘的发展与统计学研究

1、流式数据挖掘的发展与统计学研究 朱建平 来升强厦门大学经济学院计划统计系7/18/2022The Development and The Statistical Research for Streaming Data MiningZhu Jian-ping Lai Sheng-qiangDepartment of Planning and Statistics of the School of Economics of Xiamen University 7/18/2022报告目的 本报告对近年来在国内外学界涌现出的流式数据挖掘的研究成果进行较为全面的介绍，分析了

2、流式数据挖掘的研究现状。提出了统计学在流式数据挖掘研究中的发展趋势，以便更好让大 家深入的认识统计学和数据挖掘的结合， 拓展统计学方法的研究思路。7/18/2022报告的基本内容一、流式数据挖掘的研究现状 二、流式数据挖掘中统计学的研究趋势 三、统计学研究的体会7/18/2022一、流式数据挖掘的研究现状 经过近二十年的发展，数据挖掘方法在众多领域被广泛研究和应用。在学术界，美国计算机学会(ACM)有多个主题为数据挖掘的学术会议，例如SIGMOD（Conference on Management of Data）、DMKD（Data Mining and Knowledge Discovery

3、）和VLDB（VeryLargeDataBases）等。以数据挖掘为主题的国际期刊也有不少，其中影响较大的有超大数据库期刊(VLDB Journal)、数据挖掘与知识发现（Data Mining and Knowledge Discovery)和美国计算机学会数据库系统学报（ACM Transactions On Database Systems），并且一些系统科学、统计学、人工智能、临床医学等领域的重要刊物上也屡见数据挖掘理论及方法的应用研究。7/18/2022 近年来，国内外学界涌现了一大批针对流式数据挖掘的研究成果。所谓流式数据，指按照时间顺序无限增加的数据观测值向量所组成的数据序列，也

4、可以将流式数据看成历史数据和不断增加的更新数据的并集。从定义易知，流式数据挖掘是数据挖掘的更一般形式。 流式数据主要出现在大量实时监测和控制系统中，例如航天水利设备传感器组监控、气温水流等环境气象监测、以及金融市场实时交易监控等实时系统都会产生规模巨大的历史数据，并能在数分钟内就生成一个相当规模的更新数据集。 7/18/2022 数据对象的复杂化和动态化向研究者提出了新的挑战。从总体上，国外在该领域的研究较为广泛，我们从数据挖掘的技术和挖掘的知识看，在流式数据挖掘的研究方面取得了一些成效。 1. 流式数据聚类。 2. 流式数据分类。 3. 时变模式识别。 4. 流式数据压缩。 5. 规则发现。

5、7/18/2022 1. 流式数据聚类 长期以来，数据挖掘的聚类分析都处在静态数据的层次上。这一方面是维数灾问题(coarse of dimensionality)没有得到很好的解决，常用的特征变换(feature transformation)和子空间选择(subspace selection)方法实际上都是有损失的降维技术，许多研究都试图提出新的降维方法，以尽可能地减少信息损失。另一方面是数据规模问题。由于计算机性能限制，大量的研究都在改进算法和降低复杂度。7/18/2022 然而，流式数据是历史数据与不断增加的更新数据的并集，因此除了以上提到的两个问题，流式数据聚类分析还应考虑：(1)如

6、何反映流式数据在时间上的动态特征。现在基本是采用对时间窗内不同时刻观测值加权的办法(有些文献称之为“倾斜时间窗(tilted time window)”)，例如Aggarwal C., et al.(2005)采用一个关于数据观测值生存时间的指数衰减函数对历史数据进行加权；(2)如何处理更新数据对已有聚类的影响。显然只有在(1)的基础上，这个问题才有可能解决，目前这方面研究几乎空白。7/18/20222. 流式数据分类 在流式数据条件下，分类过程不仅仅是建立一个判别模型就完成了，更重要的是保证分类模型对于更新数据的适应性和分类稳定性。例如Hulten G., et al.(2001)提出的动态

7、决策树CVFDT，可以根据更新数据动态地建立新枝或删除旧枝，有效的结合了历史信息和更新信息。Hastie T., et al.(2001)的一种分类回归树(Categorical And Regression Tree)的改进形式还可以完成对非数值型流式数据的分类任务。最近Lee S., et al.(2005)将广义估计方程(GEE)应用到决策树分类中，较好解决了混合型流式数据的分类问题。Rousseeuw P., et al.(2006)改进了稳健统计分析中的最小截断二乘法的估计方法(Least Trimmed Squares)，使LTS回归能胜任大型流式数据的分类回归任务。7/18/20

8、223. 时变模式识别 这一问题源于如何在包含空间位置信息的流式数据中进行多目标路径相似性识别。从早期时空数据库中的规则挖掘到现在的动态时间翘曲(Dynamic Time Warping)研究，时变模式识别已经从寻找单一的、静态的时空规则发展到可以分别挖掘出具有时间相似性(similarity in time)、路径相似性(similarity in shape)、以及结构相似性(structural similarity)等三种不同相似类型的时变模式。Cao H., et al.(2006)将回归分析中的均方误差和(Mean Square of Root Error)概念应用到函数型数据中，

9、其实例分析的结果也很有说服力。7/18/20224. 流式数据压缩 流式数据压缩是指在给定的误差设定下，把历史数据压缩为一个相对较小的概要数据集(synopsis data structure)，同时保证概要数据集对历史数据的代表性。流式数据压缩方法和统计模型结合较为紧密，例如线性拟合，多项式拟合，独立成分分析等统计和数学模型。Bagnall A., et al.(2004)还证明如果流式数据是宽平稳的ARMA过程，则其0/1离散化的序列也将渐进地服从宽平稳的ARMA过程，并利用小波变换对离散化的0/1序列进行压缩。7/18/2022 相对于其他挖掘方法，规则发现更适合用于非标准流式数据的探索

10、性分析。例如分析诸如DNA序列等字符型流式数据时，可以采用小波变换；而在分析点击流数据时，可将点击流数据映射为以所有互异链接为基本项的事务数据集，进而采用时态规则进行网页内容优化和个性化网页访问服务。由于规则的具体形式是非常依赖数据的，在更新数据不断获取的情况下，规则的有效性和稳定性问题也是一个值得深入研究的方面。方法之一是利用抽样误差公式进行抽样并根据抽样频数进行频数估计，另外一种方法称为top-k有损频数估计。5. 规则发现7/18/2022 在应用方面，由于意识到数据挖掘的巨大商机，各大数据库系统公司也不断更新和完善自己的数据挖掘软件，其中应用最广泛的软件有SAS公司Enterprise

11、 Miner，IBM公司的Intelligent Miner，和SPSS公司的Clementine。最近Microsoft公司新推出的中小型数据库系统SQL2005也极大地改进和增强了数据挖掘功能。这些软件中基本都包括：决策树、聚类分析、规则挖掘、自组织图、神经网络、特征提取和可视化等功能。另外，有些软件还包括：遗传算法、EM算法、Monte Carlo模拟、记忆推理和文档挖掘等高级统计计算方法。7/18/2022 与国外相比，国内学术界对流式数据挖掘的研究刚刚开始，除了一些回顾性的研究外，其研究方向较为单一，且以流式数据下频繁模式挖掘的算法改进为主，如利用Chernoff不等式改进流式数据的

12、频繁模式挖掘算法；对FP-Growth算法的改进，使之适应流式数据的频繁模式挖掘任务等。在应用方面，国内有关研究机构也开发了不少应用级的数据挖掘软件。其中，Markway软件是功能较全面的软件之一，该软件已经被国内高校和研究机构大量使用，并取得一致好评。7/18/2022二、流式数据挖掘中统计学的研究趋势 流式数据挖掘虽然是数据挖掘的高级形式，但仍然依托于数据库、统计学、人工智能、计算机科学、以及信息科学等众多交叉学科。其中，各种统计方法也被广泛使用，例如决策树分类、近邻聚类、核估计、Bayes分析、广义估计、抽样理论、时序分析等等。 但是，在流式数据挖掘应用过程中，统计学也遇到了不少难题，例

13、如高维流式数据的降维问题、流式数据的压缩问题和抽样问题、函数数据和高频数据的统计分析问题、数据丢失和异常发现问题、流式知识的稳定性与可靠性问题等。这些跨学科的研究问题既是挑战，更是推动统计科学发展的大好机遇。我们应该明确统计学在流式数据挖掘研究中的趋势，以便更好地促进统计学和数据挖掘的结合，解决在实际问题及理论研究中遇到难题。7/18/2022 我们从统计学理论和方法的角度来审视流式数据挖掘的内容和方法，一方面有利于明确统计方法的应用现状和所面临的困难；另一方面可以引起统计学界对流式数据挖掘的广泛关注，也有利于统计学方法研究的拓展和深入。 1. 高维数据降维 2. 流式数据压缩 3. 流式数据

14、的统计描述 4. 重复观测数据分析 5. 可视化分析7/18/2022 现代统计理论与方法研究的重要领域之一是高维数据的降维问题，它也是流式数据挖掘研究的主要内容：(1)在K-NN聚类的基础上，设计出合适的权重函数，使其既能满足降维的需要，又能充分反映时间变化的影响；(2)借鉴投影寻踪方法(pursue projection)的思想，在流式数据的高维空间中找出最优线性基向量并将其作为降维子空间，同时把相应的线性变换矩阵作为原维度的权重矩阵。进一步地，还可以研究如何将这一思想推广到非线性情形，使之适合更一般的数据降维任务；(3)选择适当的基函数对流式数据进行拟合。在这些方法研究中，重点是如何设计

15、具有时变特征的权重因子。1. 高维数据降维7/18/20222. 流式数据压缩 结合统计理论中时序分析的基本思想，对流式数据中包含的不同性质、不同程度、不同周期的规律性特征进行分离，用适当的广义可加模型进行描述，并采用时变参数反映流式数据的动态特征。另外，还可以利用粗糙集等知识推理方法进行约简，将大量不必要的细节信息泛化为若干代表性知识，实现知识泛化。7/18/20223. 流式数据的统计描述 借助现在统计理论函数型数据的观点，对流式数据进行函数数据判别分析、函数数据主成分分析、函数数据的聚类分析、以及函数数据回归分析等。此外，还可以采用高频数据的观点，对流式数据进行类似的分析。7/18/20

16、22 传统多元统计分析都假设观测值都是一次获取的，很少考虑到重复观测记录的情形。在传统多元统计分析的基础上，针对流式数据可以对判别分析、主成分分析、相应分析等经典方法加以推广，使之适用于诸如流式数据等重复观测数据的情形。4. 重复观测数据分析7/18/2022 可视化是反映统计分析结果的重要环节，在流式数据研究的过程中，对于复杂现象的统计分析结果，我们还可以通过计算机软件实 现流式数据挖掘结果的可视化，并 实现人机交互式的数据挖掘过程， 使得分析结果更能体现使用价值。5. 可视化分析7/18/2022 流式数据挖掘技术和方法研究的主要目的在于应用，其研究的成果可以对移动通信通话记录进行客户流失

17、分析；对股市分钟交易数据的投机交易行为进行探测；通过网站的访问日志数据分析来优化网页内容，提高网站平均访问率和浏览时间等等。 通过理论分析和实际应用研究，我们体会到，统计学应该随时地关注数据分析。哪里有数据，哪里就应该有统计分析。统计学方法一直就是数据挖掘研究的主要方法，在流式数据挖掘领域中必将发挥越来越重要的作用。统计学和数据挖掘的关系是相辅相成的，在流式数据挖掘中适当运用统计方法会显著提高挖掘的效率和效果。同时，流式数据挖掘中所出现的问题也将促进统计科学的进一步发展。 三、统计学研究的体会7/18/2022参考文献1 Aggarwal C., Han J., Wang C. and Wu

18、P., On high dimensional projected clustering of data streamsJ, Data Mining and Knowledge Discovery, 10, 2005, p251-273.2 Hulten G., Spencer P. and Domingos P., Mining time-changing data streamsJ/OL, :/, 2001.3 Hastie T., Tibshirani R. and Friedman J., The elements of statistical learni

19、ng: data mining, inference, and predictionM, Springer-Verlag, 2001, p55-80.4 Lee S., Kang H., Han S. and Kim K., Using generalized estimating equations to learn decision trees with multivariate responsesJ, Data Mining and Knowledge Discovery, 11, 2005, p273-393.5 Rousseeuw P. and Driessen K., Comput

20、ing LTS regression for large data setsJ, Data Mining and Knowledge Discovery, 12, 2006, p29-45.6 Tan P., Steinbach M. and Kumar V., Finding spatio-temporal patterns in earth science dataA, KDD workshop on temporal data mining, 2001, p1-12.7 Bagnall A., Ratanamahatana C., Keogh E., et al., A bit leve

21、l representation for time series data mining with shape based similarityJ, Data Mining and Knowledge Discovery, 13, 2006, p11-40.8 Cao H., Wolfson O. and Trajcevski G., Spatio-temporal data reduction with deterministic error boundsJ, The VLDB Journal, 15 (3), 2006, p211-228.9 Cai Y. and Ng R., Indexing spatio-temporal trajectories with chebyshev polynomialsA, In proc. of ACM SIGMOD, 2004, p599-610.10 Basak J., Sudarshan A., Trivedi D. and Santhanam M., Weather data mining using independent component analysisJ