A Cluster Algorithm for Uncertain Data Stream

doi:10.12068/j.issn.1005-3026.2016.12.002

Abstract

Abstract: 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.

Key words: uncertain data stream, cluster, big data, data mining, MBR (minimum bounding rectangle)

CLC Number:

TP391

HAN Dong-hong， WANG Kun， SHAO Chong-lei， MA Chang. A Cluster Algorithm for Uncertain Data Stream[J]. Journal of Northeastern University Natural Science, 2016, 37(12): 1677-1682.

References

[1]Liu L.From data privacy to location privacy:models and algorithms［C］//Proceeding of the 33rd International Conference on Very Large Data Bases.Vienna，2007:1429-1430.
[2]Deshpande A，Guestrin C，Madden S，et al.Model-driven data acquisition in sensor networks［C］// Proceeding of the 30th International Conference on Very Large Data Bases.Toronto，2004:588-599.
[3]Gu Y，Yu G，Zhang T C.RFID complex event processing techniques ［J］.Journal of Frontiers of Computer Science and Technology，2007，1(3):255-267.
[4]Jeffery S R，Garofalakis M N，Franklin M J.Adaptive cleaning for RFID data streams［C］//Proceeding of the 32nd International Conference on Very Large Data Bases.Seoul，2006:163-174.
[5]周傲英，金澈清，王国仁，等.不确定性数据管理技术研究综述［J］.计算机学报，2009，32(1):1-16.(Zhou Ao-ying，Jin Che-qing，Wang Guo-ren，et al.Summary of research on uncertain data management technology［J］.Chinese Journal of Computers，2009，32(1):1-16.)
[6]Sarma A D，Benjelloun O，Halevy A Y，et al.Working models for uncertain data［C］//Proceeding of the 22nd International Conference on Data Engineering.Washington DC，2006:145-157.
[7]Aggarwal C C，Han J W，Wang J，et al. A framework for clustering evolving data streams［C］//Proceeding of the 29th International Conference on Very Large Data Bases.Berlin，2003:81-92.
[8]Aggarwal C C，Yu P S.A framework for clustering uncertain data streams［C］//Proceeding of the 24th International Conference on Data Engineering.Cancun，2008:150-159.
[9]Aggarwal C C.On high dimensional projected clustering of uncertain data streams［C］//Proceedings of the 25th International Conference on Data Engineering.Shanghai，2009:1152-1154.
[10]Zhang C，Gao M，Zhou A Y.Tracking high quality clusters over uncertain data streams［C］ //Proceeding of the 25th International Conference on Data Engineering.Shanghai，2009:1641-1648.
[11]Huang G Y，Liang D P，Ren J D，et al.An algorithm for clustering uncertain data streams over sliding windows［C］// Proceeding of the 6th International Conference on Digital Content，Multimedia Technology and Its Applications.Seoul，2009:173-177.
[12]Cao K Y，Wang G R，Han D H，et al.A framework for high-quality clustering uncertain data stream over sliding windows［C］// Proceeding of the 13th International Conference on Web-Age Information Management.Harbin，2012:308-313.
[13]肖丹萍，叶东毅.基于免疫原理的不确定数据流聚类算法［J］.模式识别与人工智能，2012，25(5):826-834.(Xiao Dan-ping，Ye Dong-yi.An algorithm of uncertain data stream cluster based on immune principle［J］.Pattern Recognition and Artificial Intelligence，2012，25(5):826-834.)
[14]罗清华，彭宇，彭喜元.一种多维不确定数据流聚类算法［J］.仪器仪表学报，2013，34(6):1330-1337.(Luo Qing-hua，Peng Yu，Peng Xi-yuan.Multi-dimensional uncertain data stream clustering algorithm［J］.Chinese Journal of Scientific Instrument，2013，34(6):1330-1337.)
[15]胡德敏，余星.一种不确定数据流子空间聚类算法［J］.计算机应用研究，2014，31(9):2606-2608.(Hu De-min，Yu Xing.Subspace clustering algorithm for uncertain data stream［J］.Application Research of Computers，2014，31(9):2606-2608.)
[16]Luo Q H，Yan X Z，Li J B，et al.A dynamic distance estimation using uncertain data stream clustering in mobile wireless sensor networks［J］.Measurement，2014，55(9):423-433.(上接第1676页)
[2]Qin S J.An overview of subspace identification［J］.Computer & Chemical Engineering，2006，30(10/11/12):1502-1513.
[3]Gustafsson T.Recursive system identification using instrumental variable subspace tracking［C］// Proceedings of the 11th IFAC Symposium on System Identification.Fukuoka，1997.
[4]Oku H，Kimura H.Recursive 4SID algorithms using gradient type subspace tracking［J］.Automatica，2002，38(6):1035-1043.
[5]Houtzager I，van Wingerden J W，Verhaegen M.Recursive predictor-based subspace identification with application to the real-time closed-loop tracking of flutter ［J］.IEEE Transactions on Control Systems Technology， 2012，20(4):934-949.
[6]Choi S W，Martin E B，Morris A J，et al.Adaptive multivariate statistical process control for monitoring time-varying processes ［J］.Industrial & Engineering Chemistry Research，2006，45(9):3108-3118.
[7]Ding S X，Zhang P，Naik A，et al.Subspace method aided data-driven design of fault detection and isolation systems ［J］.Journal of Process Control，2009，19(9):1496-1510.
[8]Naik A S，Yin S，Ding S X，et al.Recursive identification algorithms to design fault detection systems ［J］.Journal of Process Control，2010，20(8):957-965.