一种面向不确定数据流的聚类算法

作为大数据的重要组成,产生于传感器、移动电话设备、社交网络等的不确定流数据因其具有流速可变、规模宏大、单遍扫描及不确定性等特点,传统聚类算法不能满足用户高效实时的查询要求.首先利用MBR(minimum bounding rectangle)描述不确定元组的分布特性,并提出一种基于期望距离的不确定数据流聚类算法,计算期望距离范围的上下界剪枝距离较远的簇以减少计算量;其次针对簇内元组的分布特征提出了簇MBR的概念,提出一种基于空间位置关系的聚类算法,根据不确定元组MBR和簇MBR的空间位置关系排除距离不确定元组较远的簇,从而提高聚类算法效率;最后在合成数据集和真实数据集进行实验,结果验证了所提出算法的有效性和高效性.

A Cluster Algorithm for Uncertain Data Stream

As an important component of big data generated in the sensor， mobile phone devices， social networks etc.， uncertain streaming data have many characteristics， such as variable rate， large-scale， single-pass scanning， and uncertainty. Traditional clustering algorithms cannot meet efficient real-time inquiry requirements for the users. Firstly， MBR (minimum bounding rectangle) was used to describe the distribution characteristics of uncertain tuples. And then， a clustering algorithm based on expected distance was proposed for uncertain data stream. The bounds of expected distance range to filter the clusters with far distance can be calculated. Secondly， cluster MBR concept based on the distribution of the tuples in a cluster was presented. Then， a clustering algorithm was given， which excludes the clusters far from the uncertain tuple by the spatial location relationship between uncertainty tuple MBR and clusters MBR， thereby increasing the efficiency of clustering algorithm. Finally， experiments running on synthetic datasets and real datasets verify that the proposed algorithms are effective and efficient.