吉林大学学报(工学版) ›› 2013, Vol. 43 ›› Issue (06): 1626-1630.doi: 10.7964/jdxbgxb201306031
杨静, 赵家石, 张健沛
YANG Jing, ZHAO Jia-shi, ZHANG Jian-pei
摘要：
为了解决高维数据流降维处理中对实时性要求较高的问题,提出了一种基于Johnson-Lindenstrauss转换的数据流降维方法,并论证了在异步数据流情况下该方法的有效性。该方法通过一个去随机化的Johnson-Lindenstrauss转换,在保护任意两点数据之间距离的约束下将高维空间的数据流投影到低维空间,使用种子生成随机哈希函数,由哈希函数构造随机转换矩阵,在数据更新的同时进行降维处理。该方法有效地降低了计算复杂度,实现了亚线性时间的数据流降维处理。实验结果表明:该方法在保证了准确性的情况下提高了执行效率。
中图分类号:
| [1] Aggarwal C C. Data Streams: Models and Algorithms[M]. New York: Springer-Verlag, 2007.[2] 姚劲勃, 余宜诚, 于卓尔, 等. 基于PCA降维协同过滤算法的改进[J]. 吉林大学学报: 信息科学版, 2011, 29(5): 494-497. Yao Jin-bo,Yu Yi-cheng,Yu Zhuo-er,et al.Improvement on collaborative filtering algorithm based on PCA default-values[J].Journal of Jilin University(Information Science Edition),2011,29(5):494-497.[3] Kuzmin D, Warmuth M K. Online kernel PCA with entropic matrix updates [C]//International Confer-ence on Machine Learning, New York, NY, USA,2007: 465-472.[4] Hisada M, Ozawa S, Zhang K, et al. A novel incremental linear discriminant analysis for multitask pattern recognition problems[J]. Lecture Notes in Computer Science, 2009, 5506: 1163-1171.[5] Weng J, Zhang Y, Hwang W S. Candid covariance-free incremental principal component analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(8): 1034-1040.[6] Kim T K, Stenger B, Kittler J, et al. Incremental linear discriminant analysis using sufficient spanning sets and its applications[J]. International Journal of Computer Vision, 2011, 91(2): 216-232.[7] Indyk P. Stable distributions, pseudorandom generators, embeddings, and data stream computation[J]. Journal of the ACM, 2006, 53(3): 307-323.[8] Menon A K, Phamg V A, Chawla S, et al. An incre-mental data-stream sketch using sparse random projections[DB/OL].[2012-01-05]. http:[C]//cseweb.ucsd.edu/~akmenon/SparseRP.pdf.[9] Johnson W B, Lindenstrauss J. Extensions of Lipschitz mappings into a Hilbert space[J]. Contemporary Mathematics, 1984, 26:189-206.[10] Achlioptas D.Database-friendly random projections:Johnson-Linden strauss with binary coins[J].Journal of Computer and System Sciences,2003,66(4):671-687.[11] Daniel M K,Nelson J.Sparser Johnson-Lindenstrauss transforms[C]//In Proceddings of the 23th Annual ACM-SIAM Symposium on Discrete Algorithms,NewYork,USA,2012:1195-1206. |
| [1] | 董飒, 刘大有, 欧阳若川, 朱允刚, 李丽娜. 引入二阶马尔可夫假设的逻辑回归异质性网络分类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1571-1577. |
| [2] | 顾海军, 田雅倩, 崔莹. 基于行为语言的智能交互代理[J]. 吉林大学学报(工学版), 2018, 48(5): 1578-1585. |
| [3] | 王旭, 欧阳继红, 陈桂芬. 基于垂直维序列动态时间规整方法的图相似度度量[J]. 吉林大学学报(工学版), 2018, 48(4): 1199-1205. |
| [4] | 张浩, 占萌苹, 郭刘香, 李誌, 刘元宁, 张春鹤, 常浩武, 王志强. 基于高通量数据的人体外源性植物miRNA跨界调控建模[J]. 吉林大学学报(工学版), 2018, 48(4): 1206-1213. |
| [5] | 黄岚, 纪林影, 姚刚, 翟睿峰, 白天. 面向误诊提示的疾病-症状语义网构建[J]. 吉林大学学报(工学版), 2018, 48(3): 859-865. |
| [6] | 李雄飞, 冯婷婷, 骆实, 张小利. 基于递归神经网络的自动作曲算法[J]. 吉林大学学报(工学版), 2018, 48(3): 866-873. |
| [7] | 刘杰, 张平, 高万夫. 基于条件相关的特征选择方法[J]. 吉林大学学报(工学版), 2018, 48(3): 874-881. |
| [8] | 王旭, 欧阳继红, 陈桂芬. 基于多重序列所有公共子序列的启发式算法度量多图的相似度[J]. 吉林大学学报(工学版), 2018, 48(2): 526-532. |
| [9] | 杨欣, 夏斯军, 刘冬雪, 费树岷, 胡银记. 跟踪-学习-检测框架下改进加速梯度的目标跟踪[J]. 吉林大学学报(工学版), 2018, 48(2): 533-538. |
| [10] | 刘雪娟, 袁家斌, 许娟, 段博佳. 量子k-means算法[J]. 吉林大学学报(工学版), 2018, 48(2): 539-544. |
| [11] | 曲慧雁, 赵伟, 秦爱红. 基于优化算子的快速碰撞检测算法[J]. 吉林大学学报(工学版), 2017, 47(5): 1598-1603. |
| [12] | 李嘉菲, 孙小玉. 基于谱分解的不确定数据聚类方法[J]. 吉林大学学报(工学版), 2017, 47(5): 1604-1611. |
| [13] | 邵克勇, 陈丰, 王婷婷, 王季驰, 周立朋. 无平衡点分数阶混沌系统全状态自适应控制[J]. 吉林大学学报(工学版), 2017, 47(4): 1225-1230. |
| [14] | 王生生, 王创峰, 谷方明. OPRA方向关系网络的时空推理[J]. 吉林大学学报(工学版), 2017, 47(4): 1238-1243. |
| [15] | 马淼, 李贻斌. 基于多级图像序列和卷积神经网络的人体行为识别[J]. 吉林大学学报(工学版), 2017, 47(4): 1244-1252. |
|
||