12.46 分类型数据流聚类算法
在许多真实的应用中经常产生连续到达的数据，诸如网络流量监控、股票市场、信用卡欺诈检测、网站点击流和超市的客户交易等。由于到达的数据随着时间变化，所以数据的分布也将随着时间发生变化。比如在社会网络分析中，一些人可能逐渐从一个主题转换到另一个主题，而一些人可能很快改变他们的兴趣，利用聚类分析可以发现不同群体在不同时间段行为模式。针对数值型数据，数据流的聚类问题已经做了大量的研究[21-24] 。
针对分类型数据，为挖掘动态Web 站点用户日志的演化，Nasraoui et al [25] 提出了一个 Web 用户挖掘框架，并且能够从一个真实网站的 Web 日志文件中发现用户的使用模式。Chen etal [26] 提出了一个分类型数据流的聚类框架，该框架在不同的滑动窗口下检测漂移的概念，并且基于当前窗口产生聚类结果，通过可视化对不同窗口聚类结果之间的关系进行展示。然而，在这个框架中，需要设置太多的参数增加了在不同应用中的困难。Cao et al [27-29] 基于滑动窗口技术和粗糙集的隶属函数、概念的上下近似，定义了两个概念间的距离，提出了概念漂移检测算法和数据标签算法，设计了可视化算法去观察不同滑动窗口下聚类结果的演化过程，实验结果表明，提出的框架不但能精确地检测到概念漂移 , 而且能提供高质量的聚类结果。此外，用户能通过可视化方法跟踪用户感兴趣类的演化趋势。但以上提及的这些方法仍面临如下两个问题：① 将新到达的数据子集聚类问题看作类标记问题，仅使用对象和类之间的相似性来确定到达对象的类标签。由于缺乏有效性标准和优化策略，无法去调整或优化聚类结果。② 聚类优化函数和漂移概念检测指标之间缺乏关联性，这样可能忽略聚类结果有效性对漂移概念检测的影响。对于新到达的数据子集，当它的聚类结果很差时，漂移概念检测结果可能是不正确的。为了克服这些问题，Bai etal [30] 建立了一个优化模型来解决分类型数据流的聚类问题，该模型充分考虑了类代表的确定性和前后相连时刻聚类结果的连续性。基于该优化模型，获得了一个概念漂移检测指标。理论分析发现，最小化目标函数等同于最小化漂移检测指标的值。通过融合检测指标和优化模型，提出了一种新的方法去捕获分类型数据流上的聚类结构的演变趋势，该方法可以有效地避免聚类有效性对概念漂移检测结果的影响。通过真实数据集，展示了提出的聚类优化算法的有效性。