基于秩2更新的多维数据流典型相关跟踪算法

doi:10.3969/j.issn.0372-2112.2012.09.011

电子学报 ›› 2012, Vol. 40 ›› Issue (9): 1765-1774.DOI: 10.3969/j.issn.0372-2112.2012.09.011

基于秩2更新的多维数据流典型相关跟踪算法

杨静, 李文平, 张健沛

哈尔滨工程大学计算机科学与技术学院, 黑龙江哈尔滨 150001

收稿日期:2011-10-24 修回日期:2012-04-16 出版日期:2012-09-25
- 作者简介:
- 杨静 女,1962年2月出生于黑龙江省哈尔滨市.现为哈尔滨工程大学计算机科学与技术学院教授、博士生导师.主要研究方向为数据库与知识工程、数据挖掘技术、隐私保护、软件理论等. E-mail:yangjing@hrbeu.edu.cn 李文平 男,1979年10月出生于贵州省大方县.现为哈尔滨工程大学计算机科学与技术学院博士研究生.研究方向为数据库与知识工程、软件理论、数据挖掘技术、隐私保护. E-mail:liwenping@hrbeu.edu.cn 张健沛 男,1956年11月出生于哈尔滨市.现为哈尔滨工程大学计算机科学与技术学院教授、博士生导师.主要研究方向为数据库理论与应用、数据挖掘技术、软件理论、社会网络等. E-mail:zhangjianpei@hrbeu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61073043,No.61073041); 黑龙江省自然科学基金 (No.F200901); 哈尔滨市科技创新人才研究专项资金 (优秀学科带头人) (No.2011RFXXG015,No.2010RFXXG002); 高等学校博士学科点基金 (No.20112304110011)

A Tracking Algorithm Based on Rank Two Modifications for Canonical Correlation Analysis of Multidimensional Data Streams

YANG Jing, LI Wen-ping, ZHANG Jian-pei

College of Computer Science and Technology, Harbin Engineering University, Harbin, Heilongjiang 150001, China

Received:2011-10-24 Revised:2012-04-16 Online:2012-09-25 Published:2012-09-25
- Supported by:
- National Natural Science Foundation of China (No.61073043, No.61073041); Natural Science Foundation of Heilongjiang Province, China (No.F200901); Harbin Science and Technology Innovation Talents Research Fund of Heilongjiang Province (Excellent Academic Leader) (No.2011RFXXG015, No.2010RFXXG002); Doctoral Program Fund for Higher Education (No.20112304110011)

摘要/Abstract

摘要： 现存的多维数据流典型相关分析(Canonical Correlation Analysis,简称CCA)算法主要是基于近似技术的求解方法,本质上并不是持续更新的精确算法.为了能在时变的环境中持续、快速而精确地跟踪数据流之间的相关性,本文提出一种多维数据流典型相关跟踪算法TCCA.该算法基于秩2更新理论,通过并行方式持续更新样本协方差矩阵的特征子空间,进而实现多维数据流典型相关的快速跟踪.理论分析及仿真实验结果表明,TCCA具有较好的稳定性、较高的计算效率和精度,可以作为基本工具应用于数据流相关性检测、特征融合、数据降维等数据流挖掘领域.

Abstract: Existing algorithms for canonical correlation analysis(CCA) of multidimensional data streams are mostly based on approximate techniques,but are not the precise algorithms for updates in essence.In this study,a novel canonical correlation analysis algorithm,called TCCA(Tracking CCA),is proposed for tracking the correlations rapidly and accurately between two multidimensional data streams in the time-varying environments.By introducing the technique of rank two modifications to update the eigen-subspace of the sample covariance matrix in parallel,TCCA can rapidly track the correlations of data streams.Theoretical analysis and experimental results indicate that the TCCA algorithm has better stability,high computational efficiency and accuracy.It could be presented as a basic tool for correlation detection on data streams,feature fusion,dimension reduction and other areas of data streams mining.

Key words: multidimensional data streams, canonical correlation analysis, rank two modifications, fast tracking, eigen-subspace

中图分类号:

杨静, 李文平, 张健沛. 基于秩2更新的多维数据流典型相关跟踪算法[J]. 电子学报, 2012, 40(9): 1765-1774.

YANG Jing, LI Wen-ping, ZHANG Jian-pei. A Tracking Algorithm Based on Rank Two Modifications for Canonical Correlation Analysis of Multidimensional Data Streams[J]. Acta Electronica Sinica, 2012, 40(9): 1765-1774.

参考文献

[1] Sakurai Y,Papadimitriou S,et al.BRAID:stream mining through group lag correlations. Jennifer W.SIGMOD 2005:Proceedings of the ACM SIGMOD International Conference on Management of Data. New York:ACM Press,2005.599-610.
[2] Sakurai Y,Faloutsos C,et al.Fast discovery of group lag correlations in streams[J].ACM Transactions on Knowledge Discovery from Data,2010,5(1):Article 5.
[3] Yunyue Zhu,Dennis Shasha.StatStream:statistical monitoring of thousands of data streams in real time. Philip A B.VLDB 2002:Proceedings of the 28th International Conference on Very Large Data Bases. Hong Kong SAR:Elsevier Press,2002.358-369.
[4] Papadimitriou S,Jimeng Sun,et al.Streaming pattern discovery in multiple time-series. Klemens B.VLDB 2005:Proceedings of 31st International Conference on Very Large Data Bases. New York:ACM Press,2005.697-708.
[5] Tiancheng Zhang,Dejun Yue,et al.Adaptive correlation analysis in stream time series with sliding windows[J].Computers and Mathematics with Applications,2009,57(6):937-948.
[6] Mueen A,Nath S,et al.Fast approximate correlation for massive time-series data. Ahmed E.SIGMOD 2010:Proceedings of the 2010 International Conference on Management of Data. New York:ACM Press,2010.171-182.
[7] Galen Reeves,Jie Liu,et al.Managing massive time series streams with multi-scale compressed trickles[J].Proceedings of the VLDB Endowment,2009,2(1):97-108.
[8] Harold Hotelling.Relations between two sets of variates[J].Biometrika,1936,28(3):321-377.
[9] 孙权森,曾生根,等.典型相关分析的理论及其在特征融合中的应用[J].计算机学报,2005,28(9):1524-1533. SUN Quran-Sen,ZENG Sheng-Gen,et al.The theory of canonical correlation analysis and its application to feature fusion[J].Chinese Journal of Computers,2005,28(9):1524-1533.(in Chinese)
[10] Chaudhuri K,Kakade S M,et al.Multi-view clustering via canonical correlation analysis. Bottou L.ICML 2009:Proceedings,Twenty-Sixth International Conference on Machine Learning. New York:ACM Press,2009.129-136.
[11] Olcay Kursun,Ethem Alpaydin,et al.Canonical correlation analysis using within-class coupling[J].Pattern Recognition Letters,2011,32(2):134-144.
[12] Guha S,Gunopulos D,et al.Correlating synchronous and asynchronous data streams. Lise G.Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,KDD '03. New York:ACM Press,2003.529-534.
[13] 杨雪梅,董逸生,等.高维数据流的在线相关性分析[J].计算机研究与发展,2006,43(10):1744-1750. Yang Xuemei,Dong Yisheng,et al.Online correlation analysis for multiple dimensions data streams[J].Journal of Computer Research and Development,2006,43(10):1744-1750.(in Chinese)
[14] 王永利,徐宏炳,等.基于低阶近似的多维数据流相关性分析[J].电子学报,2006,34(2):293-300. WANG Yong-li,XU Hong-bing,et al.A correlation analysis algorithm based on low-rank approximation for multiple dimension data streams[J].Acta Electronica Sinica,2006,34(2):293-300.(in Chinese)
[15] Wang Yongli,Zhang Gongxuan,et al.ApproxCCA:an approximate correlation analysis algorithm for multidimensional data streams[J].Knowledge-Based Systems,2011,24(7):952-962.
[16] 彭岩,张道强.半监督典型相关分析算法[J].软件学报,2008,19(11):2822-2832. Peng Y,Zhang DQ.Semi-supervised canonical correlation analysis algorithm[J].Journal of Software,2008,19(11):2822-2832.(in Chinese)
[17] 顾晶晶,陈松灿,等.用局部保持典型相关分析定位无线传感器网络节点[J].软件学报,2010,21(11):2883-2891. GU Jing-jing,CHEN Song-can,et al.Localization in wireless sensor network using locality preserving canonical correlation analysis[J].Journal of Software,2010,21(11):2883-2891.(in Chinese)
[18] DeGroat R D,Roberts R A.SVD update algorithms and spectral estimation application. Donald E K.Nineteenth Asilomar Conference on Circuits,Systems&Computers. Washington:IEEE Computer Society Press,1985.601-605.
[19] 张贤达.矩阵分析与应用[M].北京:清华大学出版社,2004.630-637.
[20] Sherman J,Morrison W J.Adjustment of an inverse matrix corresponding to a change in one element of a given matrix[J].Ann Math Statist,1950,21(1):124-127.
[21] Gene H Golub,Charles F Van Loan.Matrix Computations(third edition)[M].Baltimore and London:The Johns Hopkins University Press,1996.461-467,341-350.
[22] 高惠璇.应用多元统计分析[M].北京:北京大学出版社,2005.41-44.
[23] Peters G,Wilkinson J H.Eigenvalues of Ax=Bx with band symmetric A and B[J].The Computer Journal,1969,12(4):398-404.

基于秩2更新的多维数据流典型相关跟踪算法

A Tracking Algorithm Based on Rank Two Modifications for Canonical Correlation Analysis of Multidimensional Data Streams

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

[1]	杨柳, 利强, 邵怀宗. Open-MUSIC：基于度量学习与特征子空间投影的电磁目标开集识别算法[J]. 电子学报, 2022, 50(6): 1310-1318.
[2]	陈若男, 孙晓颖, 刘国红. 一种计算有效的Nystrom特征子空间匹配主用户频谱感知新算法[J]. 电子学报, 2017, 45(7): 1553-1558.
[3]	贺治华;张旭峰;黎湘;庄钊文. 一种GTD模型参数估计的新方法[J]. 电子学报, 2005, 33(9): 1679-1682.