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

发布时间：2018-07-13 07:52

【摘要】：作为大数据的重要组成,产生于传感器、移动电话设备、社交网络等的不确定流数据因其具有流速可变、规模宏大、单遍扫描及不确定性等特点,传统聚类算法不能满足用户高效实时的查询要求.首先利用MBR(minimum bounding rectangle)描述不确定元组的分布特性,并提出一种基于期望距离的不确定数据流聚类算法,计算期望距离范围的上下界剪枝距离较远的簇以减少计算量;其次针对簇内元组的分布特征提出了簇MBR的概念,提出一种基于空间位置关系的聚类算法,根据不确定元组MBR和簇MBR的空间位置关系排除距离不确定元组较远的簇,从而提高聚类算法效率;最后在合成数据集和真实数据集进行实验,结果验证了所提出算法的有效性和高效性.
[Abstract]:As an important component of big data, uncertain flow data are generated from sensors, mobile phone devices, social networks, etc., because of its variable flow rate, large scale, single pass scan and uncertainty, etc. The traditional clustering algorithm can not meet the requirements of efficient real-time query. Firstly, (minimum bounding rectangle) is used to describe the distribution characteristics of uncertain tuples, and an uncertain data stream clustering algorithm based on expected distance is proposed to calculate the clusters with long pruning distance between the upper and lower bounds of the expected distance to reduce the computational complexity. Secondly, the concept of cluster MBR is proposed according to the distribution characteristics of tuples in clusters, and a clustering algorithm based on spatial location relationship is proposed. According to the spatial location relationship of uncertain tuple MBR and cluster MBR, the cluster far away from uncertain tuple is excluded. In order to improve the efficiency of the clustering algorithm, the experimental results on the synthetic data set and the real data set show that the proposed algorithm is effective and efficient.
【作者单位】： 东北大学计算机科学与工程学院;沈阳理工大学机械工程学院;
【基金】：国家自然科学基金资助项目(61173029;61332006;61672144)
【分类号】：TP311.13

【相似文献】

相关期刊论文 前10条

1 崔斌;卢阳;;基于不确定数据的查询处理综述[J];计算机应用;2008年11期

2 周逊;李建中;石胜飞;;不确定数据上两种查询的分布式聚集算法[J];计算机研究与发展;2010年05期

3 徐雪松;;时间序列不确定数据流中异常数据检测方法[J];电子设计工程;2011年19期

4 徐雪松;李玲娟;郭立玮;;基于优化策略的不确定数据流预测方法[J];计算机工程;2011年21期

5 徐雪松;沈红红;陶帆;胡晓璐;崔伟;;基于小波分析的不确定数据流异常数据检测[J];软件导刊;2011年11期

6 钱江波;王志杰;陈华辉;王海斌;;不确定数据流自适应并行连接算法及应用[J];电信科学;2012年02期

7 向剑平;乔少杰;胡剑;;基于不确定数据理论的道路相关度度量方法[J];计算机工程与设计;2012年06期

8 曹振丽;孙瑞志;李勐;;面向不确定数据的农产品追溯方法[J];农业机械学报;2013年07期

9 蒋涛;高云君;张彬;周傲英;乐光学;;不确定数据查询处理[J];电子学报;2013年05期

10 王爽;杨广明;朱志良;;基于不确定数据的频繁项查询算法[J];东北大学学报(自然科学版);2011年03期

相关会议论文 前7条

1 高聪;申德荣;于戈;聂铁铮;寇月;;一种基于不确定数据的挖掘频繁集方法[A];第二十五届中国数据库学术会议论文集（二）[C];2008年

2 周逊;李建中;石胜飞;;不确定数据上聚集查询的分布式处理算法[A];第26届中国数据库学术会议论文集（A辑）[C];2009年

3 王晓伟;黄九鸣;贾焰;;分布式不确定数据上的概率Skyline计算[A];NDBC2010第27届中国数据库学术会议论文集A辑二[C];2010年

4 艾文凯;张剡;柏文阳;;基于用户偏好的不确定数据阈值轮廓查询算法[A];NDBC2010第27届中国数据库学术会议论文集(B辑)[C];2010年

5 陆叶;王丽珍;张晓峰;;从不确定数据集中挖掘频繁Co-location模式[A];第26届中国数据库学术会议论文集（A辑）[C];2009年

6 孙永佼;王国仁;;P2P环境中不确定数据Top-k查询处理算法[A];第26届中国数据库学术会议论文集（B辑）[C];2009年

7 张潮;李晨;王勇;张阳;;uPOSC4.5:一种针对不确定数据的PU学习决策树算法[A];NDBC2010第27届中国数据库学术会议论文集(B辑)[C];2010年

相关博士学位论文 前9条

1 陈静玉;面向不确定数据流的聚类和模式挖掘技术研究[D];西安电子科技大学;2014年

2 马荔瑶;信任函数建模的认知不确定性数据分析与学习[D];中国科学技术大学;2016年

3 汤克明;不确定数据流中频繁数据挖掘研究[D];南京航空航天大学;2012年

4 梁春泉;不确定数据流分类算法研究[D];西北农林科技大学;2014年

5 高明;不确定数据的世系管理和相似性查询[D];复旦大学;2011年

6 董俊;不确定数据中数据挖掘方法的研究[D];燕山大学;2012年

7 孙永佼;P2P环境下排序查询处理和分类技术的研究[D];东北大学;2012年

8 王爽;不确定数据流频繁模式挖掘算法研究[D];东北大学;2013年

9 王晓伟;基于概率数据库的偏好查询研究[D];国防科学技术大学;2011年

相关硕士学位论文 前10条

1 孙凤姣;概率XML数据文档的分发技术研究[D];大连海事大学;2015年

2 李雨明;不确定数据的挖掘算法研究[D];上海交通大学;2015年

3 曹庆傲;不确定性数据Top-k查询算法与实现[D];贵州大学;2015年

4 武婷婷;基于MapReduce的不确定查询处理技术的研究与实现[D];东北大学;2013年

5 李红;不确定数据流查询处理算法的研究[D];黑龙江大学;2015年

6 甘果;基于不确定数据的范围查询算法的研究与实现[D];东北大学;2014年

7 张昕;基于分布式极限学习机的不确定数据流分类技术的研究与实现[D];东北大学;2014年

8 刘斌;基于聚集约束条件的不确定数据清洗与Top-k查询[D];国防科学技术大学;2013年

9 林佳丽;基于密度的不确定数据离群点检测研究[D];重庆大学;2015年

10 郎泓钰;面向不确定数据的最近邻分类方法研究[D];辽宁师范大学;2015年

，

本文编号：2118693