论文部分内容阅读
【摘要】数据流聚类是目前国际数据库和数据管理领域的新型研究热点，综述了数据流聚类的研究进展，在介绍数据流聚类的相关理论和常用技术的基础上，探讨了目前基于聚类的数据流演化国内外研究的状况，最后展望了将来可能的研究方向。
【关键词】数据流 聚类 交互式数据
【中图分类号】G64 【文献标识码】A 【文章编号】2095-3089（2014）04-0236-01
一、数据流及其聚类
在线交互式数据分析与处理的难点在于从多源异构，复杂内联和动态演化的角度构建新的数据处理策略与方法。基于在线数据获得的知识通常具有不确定性、不完整性、不协调性和不恒常性等特点，对在线数据进行提炼、排疑、融合、重组等处理，结合数据的动态变化规律定性和定量地分析隐藏在数据中的知识演化规律，从而为提高数据的应用价值提供解决方案和技术支撑。
在线交互式数据处理应该具备在线短的时间内，有效地整合与调度资源、数据源之间彼此关联、快速演化形式、进而提出在用户体验方面与之前业务截然不同的表現，适应在线信息服务的灵活性和快速演化的要求。基本的动态数据模型有三种：1.动态模糊数据模型DFDM；2.动态模糊数据的扩展模型EMDFD；3.动态模糊关系数据模型DFRDM。
随着时间的变化，数据的统计性质往往会发生变化，即数据的分布是随时间而变化的，这也被称为“分布漂移”。造成这种分布变化的因素可以分为两种，一种是数据本身的本质“概念”变化，另一种是噪声的变化，如在不同的时刻，搜集数据时条件不相同，数据噪声也不相同，在这样的数据上的聚类就是一个新问题——演化聚类。在数据流上进行聚类，其基本任务就是要在对当前数据进行聚类的同时，随着新数据的不断流入，动态地调整和更新聚类的结果以真实反映数据流的聚类形态。这种在线的增量聚类使得常规的聚类技术难以在数据流上直接应用，算法必须要满足如下要求：1.内存限制。由于内存容量有限，不可能将数据量庞大的数据流全部存储于内存，再进行聚类。在内存中只维护一个反应当前数据流特征的概要数据结构是目前常用的技术；2.实时性。数据流聚类要求具备很短的响应时间，能够响应anytime的用户聚类请求，要求算法处理速度快；3.单遍扫描或者有限次扫描。在对数据流进行聚类时，只能按数据点流入的顺序访问一次或几次。以上只是基本要求，对一个搞笑的实时数据流聚类算法来说，还必须考虑：1.聚类簇数事先未知。算法不可能预知数据流将会被分为几个聚类簇，不但如此，随着新数据不断地流入，聚类簇数目和状态都在不断地变化；2.对孤立点的分析能力。由于数据流的不断流动和进化，当前时间窗口内的孤立点，有可能随着新数据的加入变成一个新聚类簇，也有可能仍然是孤立点而被剔除，聚类算法必须能对这一情况及时鉴别和处理；3.聚类形状任意。传统的基于欧式距离的相似度准则易于产生球形聚类，真实数据流所隐含的聚类簇一般包含很多非凸形状的聚类，算法必须具备识别任意形状聚类的能力。
二、目前国内外研究状况分析
在演化聚类中，算法最终的目的是要为每个时刻的数据给出聚类结果，该结果不仅要求能够把当前时刻的数据划分的很好，还要求各时刻的聚类模式在时间轴上保持一定的连续性。聚类结果应保持时间轴上的连续性是演化聚类问题中很重要的一点，它来自于实际应用的需要。在实际应用中，这样的性质能带来很多益处。演化聚类算法可以是在线的，第一个在线的演化数据聚类方法是CHAKRABARTI D等在evolutionary clustering论文中提出。他们在静态聚类的损失函数上增加一个时间损失项，每一个聚类都被匹配到上一时刻距离最近的那个聚类，把所有这种配对的聚类之间的距离相加作为时间损失。这种启发式最近匹配方法可能不稳定，会对聚类中心小的扰动十分敏感。
在研究中，其中包括两种数据形式：1.与传统的学习问题相同，数据样本被表示为共同的有限维特征空间中的向量。2.关系型数据。数据样本没有自身的特征表示，而只有样本之间的链接关系，这样的数据实际构成一个图，图的结点就是一个样本点，而随时间推进，结点之间的链接关系会发生变化，之前存在的链接可能消失，之前没有的链接可能建立。在非参数贝叶斯方法中能够发现多个关联演化子集中的复杂演化模式，包括聚类的出现、变化、消失以及在不同子集之间的传播，而且，在该方法中，所有的聚类数都是从数据中自动学习，不需要人为指定。另外，在马尔可夫跳转模型中不难发现难点在于如何定义“状态”以及不同时刻之间的转移矩阵。该方法采用了传统的优先混合模型，需要用户指定每一时刻的聚类数目，属于参数化方法。
在最近的数据流聚类研究中，有将多种原有技术进行结合使用，也有很多新颖的方法不断出现，其中受到广泛关注的3类方法是基于网格的数据流聚类技术、子空间聚类技术、混合属性数据流聚类，代表了当前数据流聚类研究的主流方向。
（一）D-Stream算法
网格聚类首先将数据局空间网格化为由一定数目的网格单元组成的网格结构，然后将数据流映射到网格结构中，应用类似于密度的方法，形成网格密度的概念，网格空间里相邻的高密度网格的集合代表一个聚类，聚类操作就在网格上进行。
（二）GSCDS算法
最近的研究中，子空间聚类技术也被借鉴到数据流模型，最近公布的GSCDS算法就是一个代表。子空间聚类算法是一类在数据空间的所有子空间搜寻聚类的方法，根据搜索策略不同一般分为自底向上的模式和自顶向下的模式。GSCDS算法充分利用自底向上网格方法的压缩能力和自顶向下网格方法处理高维数据的能力，将它们结合起来应用于实时数据流。
（三）HCluStream算法
真实数据流一般具有混合属性，全连续或全离散属性的数据流在现实中几乎不存在，而目前大多的算法仅局限于处理连续属性，对离散属性采取简单的舍弃方法。为了使算法有效处理真实数据流，有专家学者提出了一种基于混合属性的数据聚类算法HCluStream。
三、未来集中研究的几个方向
针对在线数据实时分类的研究，将在线数据流进行整合，从而应用到具体问题中。这些数据流中往往包含多种类型的数据，不仅是数值型数据，还包含其他类型的数据，因此该算法能对这些数据类型进行实时分类。在线交互式数据具有不确定性，不稳定性等特点。不同类型的是数据，例如在线视频流，各自具有不同的特点。从解决实际问题的角度出发，需要对这些多源异质数据源特性进行深入分析，但是目前研究中对多源异质数据源的特征提取考虑较少。其主要原因是对这些数据流对时间的要求很高，数据特征不明显、并且数据量巨大，进行分析有很大的难度。针对动态数据分析进行抽象建模是解决问题的关键。目前针对在线交互式数据问题的研究中，常见的解决思路是将数据提取后进行静态分析，再利用相关的成熟理论和方法进行求解，不能实现真正意义上的是实时性，这样建立的模型存在的一个主要问题是为了模型的标准化，忽略了一些实际问题要素。
未来的研究会集中在以下几个方面：第一，基于资源约束的自适应实时数据流聚类。主要针对无线传感网络等资源约束环境进行数据流聚类。第二，高维度实时数据流的聚类。大多数真实数据流都具有高维特性，高维空间中对象分布稀疏，噪声不易识别，是一个较难解决的问题，也给聚类带来严重的障碍。第三，分布式环境下的多数据流实时聚类。在分布式环境中，数据流广泛分布于分散的、异构的数据源中，研究新的技术使其在分布式环境具有更好的健壮性和更高的效率是一个亟需解决的难题。
参考文献：
[1]金澈清，钱卫宁.流数据分析与管理综述[J].软件学报，2004，15（8）；1172-1181.
[2]周晓云，张柏礼.高维数据流聚类及演化分析研究[J].计算机研究与发展，2006，43（11）：2005-2011.
【关键词】数据流 聚类 交互式数据
【中图分类号】G64 【文献标识码】A 【文章编号】2095-3089（2014）04-0236-01
一、数据流及其聚类
在线交互式数据分析与处理的难点在于从多源异构，复杂内联和动态演化的角度构建新的数据处理策略与方法。基于在线数据获得的知识通常具有不确定性、不完整性、不协调性和不恒常性等特点，对在线数据进行提炼、排疑、融合、重组等处理，结合数据的动态变化规律定性和定量地分析隐藏在数据中的知识演化规律，从而为提高数据的应用价值提供解决方案和技术支撑。
在线交互式数据处理应该具备在线短的时间内，有效地整合与调度资源、数据源之间彼此关联、快速演化形式、进而提出在用户体验方面与之前业务截然不同的表現，适应在线信息服务的灵活性和快速演化的要求。基本的动态数据模型有三种：1.动态模糊数据模型DFDM；2.动态模糊数据的扩展模型EMDFD；3.动态模糊关系数据模型DFRDM。
随着时间的变化，数据的统计性质往往会发生变化，即数据的分布是随时间而变化的，这也被称为“分布漂移”。造成这种分布变化的因素可以分为两种，一种是数据本身的本质“概念”变化，另一种是噪声的变化，如在不同的时刻，搜集数据时条件不相同，数据噪声也不相同，在这样的数据上的聚类就是一个新问题——演化聚类。在数据流上进行聚类，其基本任务就是要在对当前数据进行聚类的同时，随着新数据的不断流入，动态地调整和更新聚类的结果以真实反映数据流的聚类形态。这种在线的增量聚类使得常规的聚类技术难以在数据流上直接应用，算法必须要满足如下要求：1.内存限制。由于内存容量有限，不可能将数据量庞大的数据流全部存储于内存，再进行聚类。在内存中只维护一个反应当前数据流特征的概要数据结构是目前常用的技术；2.实时性。数据流聚类要求具备很短的响应时间，能够响应anytime的用户聚类请求，要求算法处理速度快；3.单遍扫描或者有限次扫描。在对数据流进行聚类时，只能按数据点流入的顺序访问一次或几次。以上只是基本要求，对一个搞笑的实时数据流聚类算法来说，还必须考虑：1.聚类簇数事先未知。算法不可能预知数据流将会被分为几个聚类簇，不但如此，随着新数据不断地流入，聚类簇数目和状态都在不断地变化；2.对孤立点的分析能力。由于数据流的不断流动和进化，当前时间窗口内的孤立点，有可能随着新数据的加入变成一个新聚类簇，也有可能仍然是孤立点而被剔除，聚类算法必须能对这一情况及时鉴别和处理；3.聚类形状任意。传统的基于欧式距离的相似度准则易于产生球形聚类，真实数据流所隐含的聚类簇一般包含很多非凸形状的聚类，算法必须具备识别任意形状聚类的能力。
二、目前国内外研究状况分析
在演化聚类中，算法最终的目的是要为每个时刻的数据给出聚类结果，该结果不仅要求能够把当前时刻的数据划分的很好，还要求各时刻的聚类模式在时间轴上保持一定的连续性。聚类结果应保持时间轴上的连续性是演化聚类问题中很重要的一点，它来自于实际应用的需要。在实际应用中，这样的性质能带来很多益处。演化聚类算法可以是在线的，第一个在线的演化数据聚类方法是CHAKRABARTI D等在evolutionary clustering论文中提出。他们在静态聚类的损失函数上增加一个时间损失项，每一个聚类都被匹配到上一时刻距离最近的那个聚类，把所有这种配对的聚类之间的距离相加作为时间损失。这种启发式最近匹配方法可能不稳定，会对聚类中心小的扰动十分敏感。
在研究中，其中包括两种数据形式：1.与传统的学习问题相同，数据样本被表示为共同的有限维特征空间中的向量。2.关系型数据。数据样本没有自身的特征表示，而只有样本之间的链接关系，这样的数据实际构成一个图，图的结点就是一个样本点，而随时间推进，结点之间的链接关系会发生变化，之前存在的链接可能消失，之前没有的链接可能建立。在非参数贝叶斯方法中能够发现多个关联演化子集中的复杂演化模式，包括聚类的出现、变化、消失以及在不同子集之间的传播，而且，在该方法中，所有的聚类数都是从数据中自动学习，不需要人为指定。另外，在马尔可夫跳转模型中不难发现难点在于如何定义“状态”以及不同时刻之间的转移矩阵。该方法采用了传统的优先混合模型，需要用户指定每一时刻的聚类数目，属于参数化方法。
在最近的数据流聚类研究中，有将多种原有技术进行结合使用，也有很多新颖的方法不断出现，其中受到广泛关注的3类方法是基于网格的数据流聚类技术、子空间聚类技术、混合属性数据流聚类，代表了当前数据流聚类研究的主流方向。
（一）D-Stream算法
网格聚类首先将数据局空间网格化为由一定数目的网格单元组成的网格结构，然后将数据流映射到网格结构中，应用类似于密度的方法，形成网格密度的概念，网格空间里相邻的高密度网格的集合代表一个聚类，聚类操作就在网格上进行。
（二）GSCDS算法
最近的研究中，子空间聚类技术也被借鉴到数据流模型，最近公布的GSCDS算法就是一个代表。子空间聚类算法是一类在数据空间的所有子空间搜寻聚类的方法，根据搜索策略不同一般分为自底向上的模式和自顶向下的模式。GSCDS算法充分利用自底向上网格方法的压缩能力和自顶向下网格方法处理高维数据的能力，将它们结合起来应用于实时数据流。
（三）HCluStream算法
真实数据流一般具有混合属性，全连续或全离散属性的数据流在现实中几乎不存在，而目前大多的算法仅局限于处理连续属性，对离散属性采取简单的舍弃方法。为了使算法有效处理真实数据流，有专家学者提出了一种基于混合属性的数据聚类算法HCluStream。
三、未来集中研究的几个方向
针对在线数据实时分类的研究，将在线数据流进行整合，从而应用到具体问题中。这些数据流中往往包含多种类型的数据，不仅是数值型数据，还包含其他类型的数据，因此该算法能对这些数据类型进行实时分类。在线交互式数据具有不确定性，不稳定性等特点。不同类型的是数据，例如在线视频流，各自具有不同的特点。从解决实际问题的角度出发，需要对这些多源异质数据源特性进行深入分析，但是目前研究中对多源异质数据源的特征提取考虑较少。其主要原因是对这些数据流对时间的要求很高，数据特征不明显、并且数据量巨大，进行分析有很大的难度。针对动态数据分析进行抽象建模是解决问题的关键。目前针对在线交互式数据问题的研究中，常见的解决思路是将数据提取后进行静态分析，再利用相关的成熟理论和方法进行求解，不能实现真正意义上的是实时性，这样建立的模型存在的一个主要问题是为了模型的标准化，忽略了一些实际问题要素。
未来的研究会集中在以下几个方面：第一，基于资源约束的自适应实时数据流聚类。主要针对无线传感网络等资源约束环境进行数据流聚类。第二，高维度实时数据流的聚类。大多数真实数据流都具有高维特性，高维空间中对象分布稀疏，噪声不易识别，是一个较难解决的问题，也给聚类带来严重的障碍。第三，分布式环境下的多数据流实时聚类。在分布式环境中，数据流广泛分布于分散的、异构的数据源中，研究新的技术使其在分布式环境具有更好的健壮性和更高的效率是一个亟需解决的难题。
参考文献：
[1]金澈清，钱卫宁.流数据分析与管理综述[J].软件学报，2004，15（8）；1172-1181.
[2]周晓云，张柏礼.高维数据流聚类及演化分析研究[J].计算机研究与发展，2006，43（11）：2005-2011.