论文部分内容阅读
随着计算机网络、数据库、多媒体等技术的飞速发展和日益普及,数据流模型在传感器网络、金融证券分析、数据挖掘、制造业和天文等领域得到了广泛的应用。和传统的数据模型相比,数据流模型具有截然不同的特点:数据量无穷;对问题要求快速响应;数据概念随时间变化。传统的数据挖掘技术主要是针对静态和有限的数据,很难被应用到数据流这种新的模型中去,这促使越来越多的研究人员深入研究数据流模型,设计出新的数据处理方案。本文分析了当前数据流挖掘中的频繁元素挖掘、数据流分类、卸载处理和特征选择等关键技术,并针对其中的一些问题提出了改进方案和算法。论文的主要工作和创新点有:1.提出了HCOUNT+算法来挖掘数据流上的频繁元素。HCOUNT+算法采用了一个辅助的措施来改进HCOUNT算法,虽然增加了有限的空间开销,但较大地提高了HCOUNT算法的准确率。HCOUNT+算法仅需要(1 +α)·(e/ε)·ln(-M/(lnp))(α<1)个计数器,就能够估算每个元素的值,且最大误差不超过ε。在此基础之上,本文还提出了SL-HCOUNT+算法来挖掘数据流上最近出现的所有频繁元素,而不仅仅是传统算法所挖掘的TOP ? K的频繁元素。理论证明HCOUNT+算法和SL-HCOUNT+算法在挖掘频繁元素上具有较好的时间复杂度和空间复杂度,实验结果证实了这两种算法有较高的查询精度。2.提出了基于逻辑回归的ELRClass算法来处理数据流的分类问题。逻辑回归有一些优良的特点:运行效率高;能在小样本上获得很高的分类准确率;能非线性处理离散的和连续的数据。ELRClass算法使用逻辑回归到滑动窗口中的数据,持续监测和更新当前的分类器。如果分类器性能的变坏是由于突发噪声而引起,则保持原有的分类器。如果检测到概念发生漂移,则构建和使用新的分类器。实验结果验证了ELRClass算法的有效性。3.提出了几个基于支持向量机的算法来处理数据流的多分类问题。本文首先分别为一对一算法、一对多算法和DB2算法提出了一个增量式的改进算法One2One,One2Rest和LDB2,这些算法有对大容量数据进行多分类的能力。在每个增量步骤仅仅保留支持向量,这些支持向量加到下一个批次数据作为训练样本,构建若干个二分类器。在测试阶段,LDB2算法平均使用log2N个分类器,One2All算法使用N个分类器,One2One算法使用N ( N - 1)/2个分类器,所以LDB2算法比One2All算法和One2One算法的测试速度都要快。实验结果显示LDB2算法比One2One算法和One2Rest算法的分类交叉准确率都要高。本文还提出了一个能实时检测局部概念漂移并随之自适应调整的数据流分类算法IncreDB2。当局部概念漂移出现时,IncreDB2算法不是重新构造一个全新的DB2层次分类树,而是仅更新漂移所影响的局部结点,具有较好时间运行效率。实验结果表明该算法可以有效解决数据流分类中出现的局部概念漂移的问题。4.提出了RLS算法来进行数据流管理系统的卸载处理。本文指出查询操作符的选择率会由于卸载操作的执行而改变,在卸载操作前后可能会有突变。而传统的卸载算法在确定卸载地点时候,通常假定选择率在卸载前和卸载后保持不变,这使传统算法得到的卸载地点并不是最合适的。与传统卸载算法不同的是, RLS算法使用卸载操作后的选择率,而不是卸载操作前的选择率来确定最合适的卸载地点。实验结果表明RLS算法具有较好的查询准确率。5.提出了两个基于OCFS算法的特征选择算法POCFS和POCFS+。大部分的特征选择算法是贪婪算法,不能提供最优解,而最近提出的基于正交中心思想的最优特征选择算法(OCFS算法)能依据正交中心函数获得最优解。与OCFS算法为所有的类选择相同特征不同的是,POCFS算法和POCFS+算法为不同的类对选择不同的特征,从而可以分类算法选择更合适的特征。另外,除了采用能量函数外,POCFS+算法还定义了特征分数的递减比率来加速确定最优特征数量的选择过程。实验结果表明分类算法中采用POCFS算法能获得与采用OCFS算法相似的分类准确率,但是有更好的时间开销,而采用POCFS+算法能进一步提高数据流分类的运行效率和分类效果。