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

流式数据挖掘的发展流式数据挖掘的发展与统计学研究与统计学研究 朱建平朱建平 来升强来升强厦门大学经济学院计划统计系厦门大学经济学院计划统计系3/4/2023The Development and The Statistical Research for Streaming Data MiningZhuJian-pingLaiSheng-qiangDepartmentofPlanningandStatisticsoftheSchoolofEconomicsofXiamenUniversityxmjpzhuxmu.edu3/4/2023报告目的 本报告对近年来在国内外学界涌现出的流式数据挖掘的研究成果进行较为全面的介绍，分析了流式数据挖掘的研究现状。提出了统计学在流式数据挖掘研究中的发展趋势，以便更好让大 家深入的认识统计学和数据挖掘的结合，拓展统计学方法的研究思路。3/4/2023报告的基本内容一、流式数据挖掘的研究现状 二、流式数据挖掘中统计学的研究趋势 三、统计学研究的体会3/4/2023一、流式数据挖掘的研究现状 经过近二十年的发展，数据挖掘方法在众多领域被广泛研究和应用。在学术界，美国计算机学会(ACM)有多个主题为数据挖掘的学术会议，例如SIGMOD（Conference on Management of Data）、DMKD（Data Mining and Knowledge Discovery）和VLDB（VeryLargeDataBases）等。以数据挖掘为主题的国际期刊也有不少，其中影响较大的有超大数据库期刊(VLDB Journal)、数据挖掘与知识发现（Data Mining and Knowledge Discovery)和美国计算机学会数据库系统学报（ACM Transactions On Database Systems），并且一些系统科学、统计学、人工智能、临床医学等领域的重要刊物上也屡见数据挖掘理论及方法的应用研究。3/4/2023 近年来，国内外学界涌现了一大批针对流式数据挖掘的研究成果。所谓流式数据，指按照时间顺序无限增加的数据观测值向量所组成的数据序列，也可以将流式数据看成历史数据和不断增加的更新数据的并集。从定义易知，流式数据挖掘是数据挖掘的更一般形式。流式数据主要出现在大量实时监测和控制系统中，例如航天水利设备传感器组监控、气温水流等环境气象监测、以及金融市场实时交易监控等实时系统都会产生规模巨大的历史数据，并能在数分钟内就生成一个相当规模的更新数据集。3/4/2023 数据对象的复杂化和动态化向研究者提出了新的挑战。从总体上，国外在该领域的研究较为广泛，我们从数据挖掘的技术和挖掘的知识看，在流式数据挖掘的研究方面取得了一些成效。1.流式数据聚类。2.流式数据分类。3.时变模式识别。4.流式数据压缩。5.规则发现。3/4/2023 1.流式数据聚类 长期以来，数据挖掘的聚类分析都处在静态数据的层次上。这一方面是维数灾问题(coarse of dimensionality)没有得到很好的解决，常用的特征变换(feature transformation)和子空间选择(subspace selection)方法实际上都是有损失的降维技术，许多研究都试图提出新的降维方法，以尽可能地减少信息损失。另一方面是数据规模问题。由于计算机性能限制，大量的研究都在改进算法和降低复杂度。3/4/2023 然而，流式数据是历史数据与不断增加的更新数据的并集，因此除了以上提到的两个问题，流式数据聚类分析还应考虑：(1)如何反映流式数据在时间上的动态特征。现在基本是采用对时间窗内不同时刻观测值加权的办法(有些文献称之为“倾斜时间窗(tilted time window)”)，例如Aggarwal C.,et al.(2005)采用一个关于数据观测值生存时间的指数衰减函数对历史数据进行加权；(2)如何处理更新数据对已有聚类的影响。显然只有在(1)的基础上，这个问题才有可能解决，目前这方面研究几乎空白。3/4/20232.流式数据分类 在流式数据条件下，分类过程不仅仅是建立一个判别模型就完成了，更重要的是保证分类模型对于更新数据的适应性和分类稳定性。例如Hulten G.,et al.(2001)提出的动态决策树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回归能胜任大型流式数据的分类回归任务。3/4/20233.时变模式识别 这一问题源于如何在包含空间位置信息的流式数据中进行多目标路径相似性识别。从早期时空数据库中的规则挖掘到现在的动态时间翘曲(Dynamic Time Warping)研究，时变模式识别已经从寻找单一的、静态的时空规则发展到可以分别挖掘出具有时间相似性(similarity in time)、路径相似性(similarity in shape)、以及结构相似性(structural similarity)等三种不同相似类型的时变模式。Cao H.,et al.(2006)将回归分析中的均方误差和(Mean Square of Root Error)概念应用到函数型数据中，其实例分析的结果也很有说服力。3/4/20234.流式数据压缩 流式数据压缩是指在给定的误差设定下，把历史数据压缩为一个相对较小的概要数据集(synopsis data structure)，同时保证概要数据集对历史数据的代表性。流式数据压缩方法和统计模型结合较为紧密，例如线性拟合，多项式拟合，独立成分分析等统计和数学模型。Bagnall A.,et al.(2004)还证明如果流式数据是宽平稳的ARMA过程，则其0/1离散化的序列也将渐进地服从宽平稳的ARMA过程，并利用小波变换对离散化的0/1序列进行压缩。3/4/2023 相对于其他挖掘方法，规则发现更适合用于非标准流式数据的探索性分析。例如分析诸如DNA序列等字符型流式数据时，可以采用小波变换；而在分析点击流数据时，可将点击流数据映射为以所有互异链接为基本项的事务数据集，进而采用时态规则进行网页内容优化和个性化网页访问服务。由于规则的具体形式是非常依赖数据的，在更新数据不断获取的情况下，规则的有效性和稳定性问题也是一个值得深入研究的方面。方法之一是利用抽样误差公式进行抽样并根据抽样频数进行频数估计，另外一种方法称为top-k有损频数估计。5.规则发现3/4/2023 在应用方面，由于意识到数据挖掘的巨大商机，各大数据库系统公司也不断更新和完善自己的数据挖掘软件，其中应用最广泛的软件有SAS公司Enterprise Miner，IBM公司的Intelligent Miner，和SPSS公司的Clementine。最近Microsoft公司新推出的中小型数据库系统SQL2005也极大地改进和增强了数据挖掘功能。这些软件中基本都包括：决策树、聚类分析、规则挖掘、自组织图、神经网络、特征提取和可视化等功能。另外，有些软件还包括：遗传算法、EM算法、Monte Carlo模拟、记忆推理和文档挖掘等高级统计计算方法。3/4/2023 与国外相比，国内学术界对流式数据挖掘的研究刚刚开始，除了一些回顾性的研究外，其研究方向较为单一，且以流式数据下频繁模式挖掘的算法改进为主，如利用Chernoff不等式改进流式数据的频繁模式挖掘算法；对FP-Growth算法的改进，使之适应流式数据的频繁模式挖掘任务等。在应用方面，国内有关研究机构也开发了不少应用级的数据挖掘软件。其中，Markway软件是功能较全面的软件之一，该软件已经被国内高校和研究机构大量使用，并取得一致好评。3/4/2023二、流式数据挖掘中统计学的研究趋势 流流式式数数据据挖挖掘掘虽虽然然是是数数据据挖挖掘掘的的高高级级形形式式，但但仍仍然然依依托托于于数数据据库库、统统计计学学、人人工工智智能能、计计算算机机科科学学、以以及及信信息息科科学学等等众众多多交交叉叉学学科科。其其中中，各各种种统统计计方方法法也也被被广广泛泛使使用用，例例如如决决策策树树分分类类、近近邻邻聚聚类类、核核估估计、计、BayesBayes分析、广义估计、抽样理论、时序分析等等分析、广义估计、抽样理论、时序分析等等。但但是是，在在流流式式数数据据挖挖掘掘应应用用过过程程中中，统统计计学学也也遇遇到到了了不不少少难难题题，例例如如高高维维流流式式数数据据的的降降维维问问题题、流流式式数数据据的的压压缩缩问问题题和和抽抽样样问问题题、函函数数数数据据和和高高频频数数据据的的统统计计分分析析问问题题、数数据据丢丢失失和和异异常常发发现现问问题题、流流式式知知识识的的稳稳定定性性与与可可靠靠性性问问题题等等。这这些些跨跨学学科科的的研研究究问问题题既既是是挑挑战战，更更是是推推动动统统计计科科学学发发展展的的大大好好机机遇遇。我我们们应应该该明明确确统统计计学学在在流流式式数数据据挖挖掘掘研研究究中中的的趋趋势势，以以便便更更好好地地促促进进统统计计学学和和数数据据挖挖掘掘的的结结合合，解解决决在在实实际问题及理论研究中遇到难题。际问题及理论研究中遇到难题。3/4/2023 我们从统计学理论和方法的角度来审视流式数据挖掘的内容和方法，一方面有利于明确统计方法的应用现状和所面临的困难；另一方面可以引起统计学界对流式数据挖掘的广泛关注，也有利于统计学方法研究的拓展和深入。1.高维数据降维 2.流式数据压缩 3.流式数据的统计描述 4.重复观测数据分析 5.可视化分析3/4/2023 现代统计理论与方法研究的重要领域之一是高维数据的降维问题，它也是流式数据挖掘研究的主要内容：(1)在K-NN聚类的基础上，设计出合适的权重函数，使其既能满足降维的需要，又能充分反映时间变化的影响；(2)借鉴投影寻踪方法(pursue projection)的思想，在流式数据的高维空间中找出最优线性基向量并将其作为降维子空间，同时把相应的线性变换矩阵作为原维度的权重矩阵。进一步地，还可以研究如何将这一思想推广到非线性情形，使之适合更一般的数据降维任务；(3)选择适当的基函数对流式数据进行拟合。在这些方法研究中，重点是如何设计具有时变特征的权重因子。1.高维数据降维3/4/20232.2.流式数据压缩流式数据压缩 结合统计理论中时序分析的基本思想，结合统计理论中时序分析的基本思想，对流式数据中对流式数据中包含的不同性质、不同程度、不同周期的规律性特征进行包含的不同性质、不同程度、不同周期的规律性特征进行分离，用适当的广义可加模型进行描述，并采用时变参数分离，用适当的广义可加模型进行描述，并采用时变参数反映流式数据的动态特征。另外，还可以反映流式数据的动态特征。另外，还可以利用粗糙集利用粗糙集等知等知识推理方法进行约简，将大量不必要的细节信息泛化为若识推理方法进行约简，将大量不必要的细节信息泛化为若干代表性知识，实现知识泛化。干代表性知识，实现知识泛化。3/4/20233.流式数据的统计描述 借助现在统计理论函数型数据的观点，对流式数据进行函数数据判别分析、函数数据主成分分析、函数数据的聚类分析、以及函数数据回归分析等。此外，还可以采用高频数据的观点，对流式数据进行类似的分析。3/4/2023 传统多元统计分析都假设观测值都是一次获取的，很少考虑到重复观测记录的情形。在传统多元统计分析的基础上，针对流式数据可以对判别分析、主成分分析、相应分析等经典方法加以推广，使之适用于诸如流式数据等重复观测数据的情形。4.重复观测数据分析3/4/2023 可视化是反映统计分析结果的重要环节，在流式数据研究的过程中，对于复杂现象的统计分析结果，我们还可以通过计算机软件实 现流式数据挖掘结果的可视化，并 实现人机交互式的数据挖掘过程，使得分析结果更能体现使用价值。5.可视化分析3/4/2023 流式数据挖掘技术和方法研究的主要目的在于应用，其研究的成果可以对移动通信通话记录进行客户流失分析；对股市分钟交易数据的投机交易行为进行探测；通过网站的访问日志数据分析来优化网页内容，提高网站平均访问率和浏览时间等等。通过理论分析和实际应用研究，我们体会到，统计学应该随时地关注数据分析。哪里有数据，哪里就应该有统计分析。统计学方法一直就是数据挖掘研究的主要方法，在流式数据挖掘领域中必将发挥越来越重要的作用。统计学和数据挖掘的关系是相辅相成的，在流式数据挖掘中适当运用统计方法会显著提高挖掘的效率和效果。同时，流式数据挖掘中所出现的问题也将促进统计科学的进一步发展。三、统计学研究的体会3/4/2023参考文献n1 Aggarwal C.,Han J.,Wang C.and Wu P.,On high dimensional projected clustering of data streams J,Data Mining and Knowledge Discovery,10,2005,p251-273.n2 Hulten G.,Spencer P.and Domingos P.,Mining time-changing data streams J/OL,:/portal.acm.org,2001.n3 Hastie T.,Tibshirani R.and Friedman J.,The elements of statistical learning:data mining,inference,and predictionM,Springer-Verlag,2001,p55-80.n4 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.n5 Rousseeuw P.and Driessen K.,Computing LTS regression for large data sets J,Data Mining and Knowledge Discovery,12,2006,p29-45.n6 Tan P.,Steinbach M.and Kumar V.,Finding spatio-temporal patterns in earth science data A,KDD workshop on temporal data mining,2001,p1-12.n7 Bagnall A.,Ratanamahatana C.,Keogh E.,et al.,A bit level representation for time series data mining with shape based similarityJ,Data Mining and Knowledge Discovery,13,2006,p11-40.n8 Cao H.,Wolfson O.and Trajcevski G.,Spatio-temporal data reduction with deterministic error boundsJ,The VLDB Journal,15(3),2006,p211-228.n9 Cai Y.and Ng R.,Indexing spatio-temporal trajectories with chebyshev polynomialsA,In proc.of ACM SIGMOD,2004,p599-610.n10 Basak J.,Sudarshan A.,Trivedi D.and Santhanam M.,Weather data mining using independent component analysisJ,Journal of Machine Learning Research,5,2004,p239-253.n11 Bagnall A.and Janacek G.,Clustering time series with clipped dataJ,Machine Learning,58(2),2004,p151-178.n12 Aggarwal C.,On the use of wavelet decomposition for string classificationJ,Data Mining and Knowledge Discovery,10,2005,p117-139.n13 Xing D.and Shen J.,Efficient data mining for web navigation patternsJ,Information and Software Technology,46,2004,p55-63.n14 Wong R.and Fu A.,Mining top-k frequent itemsets from data streamsJ,Data Mining and Knowledge Discovery,13,2006,p193-217.n15 Manku G.and Motwani R.,Approximate frequency counts over data streamsA,In proc.of VLDB,2002.3/4/2023thanks for Your presenceAny Questions?3/4/2023