演化的数据流聚类算法研究

发布时间：2022-01-22 17:15

　　作为数据挖掘领域的一大分支,数据流挖掘一直是一大研究热点,现有的一些成果也已经在理论研究和实际应用中做出了重要的贡献。数据流挖掘的关键特征是通过一次扫描从海量,连续,动态演化的数据流中实时提取有价值的知识。然而,绝大多数算法都建立在数据有完整标签的基础上,且对数据流的演化形式（如,概念漂移,概念演化,特征演化等）有较强的假设,这极大地限制了数据流挖掘在实际场景中应用的广度和深度。因此,建立可靠的自适应聚类算法,使之能够有效应用于标签缺失的场景,并且对多种演化形式能快速适应及学习,是当前数据流挖掘领域的一个重要任务。本文的主要工作包括对概念演化数据流进行自适应的无监督学习以及对复杂的数据流进行特征演化的学习,本文的工作内容和主要创新点主要为以下三个方面:第一,针对概念演化数据流中滑动窗口（或衰减速率）不合适导致聚类表现变差以及聚类结果不能正确反映当前数据分布的问题,本文首次提出聚类生命周期的概念,并基于此提出聚类生命周期学习（CLL）算法,为每一个类在数据流中出现的时间和消亡的时间进行有效的预测。该算法通过为每一个带权微簇自适应地学习一个遗忘函数来调整微簇权重的衰减速率,加速组成过时概念... 

【文章来源】：电子科技大学四川省 211工程院校 985工程院校 教育部直属院校

【文章页数】：87 页

【学位级别】：硕士

【部分图文】：

概念漂移过程示例

第二章数据流聚类理论基础图2-1概念漂移过程示例。以二分类任务为例，实线（当前的分类超平面）发生偏移表示当前的数据的概念发生了漂移图2-2概念演化过程示例。不同颜色的圈用来跟踪同一个类（概念）的演化：黄色的类发生了合并，紫色的类发生了分裂，蓝色的类发生了扩张，绿色的类先缩小后消失，粉色的类出现般来说，距离当前时刻越近的数据越能反映当前数据流数据分布及变化趋势，而对于很久以前的数据，要采用衰减机制来“遗忘”它们，避免离群点的影响。如果我们把过时数据和当前数据看得一样重要，这样将无法有效挖掘出数据的演化特征。数据流挖掘中的衰减模型通常可以分为两类：基于窗口的模型和基于衰减函数的模型。基于窗口的模型：基于窗口的模型最初的概念是将数据流划分成一个个大小11

电子科技大学硕士学位论文图2-3滑动窗口模型[63]相同的数据块，每次只针对数据块中的数据进行学习与建模。然而这种不连贯的方式其实是将流式数据当作静态数据来处理，很大程度上破坏了数据流的连贯性，不仅对窗口大小的设置有很高的要求，而且对演化的检测和跟踪有很大的延迟，不能做出及时的应对措施。人们很快提出了滑动窗口的模型，在该模型中，只有最近的信息完整地保存在数据结构中以供挖掘。这种数据结构是一种类似队列的“先进先出”的结构，考虑的是从当前时刻到过去某一个固定时间段内的所有数据，如图2-3展现了滑动窗口的一个例子。很多数据流聚类算法都采用了滑动窗口的模型，然而这种模型虽然简单，但是仍面临很多问题。首先，传统方法中滑动窗口的长度通常是固定的，对窗口内的每个数据对象都是平等对待，每个对象的寿命都是相同的。这对一个窗口中相对重要的数据来说是不公平的。其次，滑动窗口大小的设置往往不是可靠的先验知识，我们很难去对其进行有效的估计。以数据流聚类为例，如图2-4所示，不同大小的滑动窗口会导致不同的聚类结果。通常，用户在没有解决方案的情况下会陷入一种权衡：选择一个小的窗口以便准确反映当前的数据分布和选择一个大的窗口以便处理更多的数据，在稳定的时期增加准确性。为了改进滑动窗口的这一缺陷，文献[38]中提出了一种自适应调节窗口大小的算法（ADWIN）来处理演化数据流中分布变化和概念漂移。在该算法中，滑动窗口的大小根据从窗口本身的数据观察到的变化速率重新计算，它的计算方法遵循以下的规则：当数据稳定时，为了获得更高的准确性，窗口将自动增长；当检测到发生演化时，窗口将自动收缩，从发生演化处截断，然后丢弃过时的数据。后来，由于ADWIN算法的时间效率不高，有学者在ADWIN的基


本文编号：3602590