跨层精度自动调节的k均值聚类近似计算方法

doi:10.19665/j.issn1001-2400.2020.03.007

摘要/Abstract

摘要：

随着人工智能在嵌入式平台上的应用,k均值聚类算法作为人工智能方法的基础,促使其在嵌入式平台上实现,而能耗是制约算法在嵌入式平台上实现的关键。为了降低k均值聚类在嵌入式平台上的能耗,提出一种针对k均值聚类的跨层精度自动调节的近似计算方法。首先, 分别从数据点到质心的距离和数据点变化趋势两个方面对迭代过程进行约束,提出精度自动调节的方法; 然后, 从结构级设计外部存储器的数据重组与访问方法,实现存储器的近似访问; 设计精度自动调节的近似加法器与乘法器,最终实现k均值聚类算法的近似计算。实验结果表明,这种近似计算方法在基本不影响聚类质量的前提下,与精确计算相比较可降低55%~58%的能耗,节省能耗的比例最高。

关键词: 近似计算, 精度自动调节, k均值聚类, 能耗

Abstract:

With the application of artificial intelligence on the embedded platform, the k-means clustering algorithm, as the basis of the artificial intelligence method, is implemented on the embedded platform. Energy consumption is the key for the algorithm implementation on the embedded platform. In order to reduce the energy consumption of the k-means on the embedded platform, an approximate computing method based on cross-layer dynamic precision scaling for the k-means is proposed. First, the iteration process is constrained from the distance between data point to centroid and data point change trend. And a dynamic precision scaling method is proposed. Then the data reorganization and access method of external memory is designed from the structural level, which can realize the access of approximate memory. In addition, the approximate adder and multiplier are designed which can automatically adjust the calculation accuracy. Finally, the approximate computing of the k-means is realized. Experimental results show that the proposed method can reduce the energy consumption by 55%~58% compared with the accurate computing without affecting the quality of clustering. The proportion of the energy saving is the highest.

Key words: approximate computing, dynamic precision scaling, k-means clustering, energy consumption

中图分类号:

TP18

李钊,袁文浩,任崇广,黄程程,董霄霄. 跨层精度自动调节的k均值聚类近似计算方法[J]. 西安电子科技大学学报, 2020, 47(3): 50-57.

LI Zhao,YUAN Wenhao,REN Chongguang,HUANG Chengcheng,DONG Xiaoxiao. Approximate computing method based on cross-layer dynamic precision scaling for the k-means[J]. Journal of Xidian University, 2020, 47(3): 50-57.

图/表 7

图1

图2

图3

图4

图5

表1

图6

参考文献 18

[1]	WANG C, CHEN Z G, SHANG K, et al. Label-removed Generative Adversarial Networks Incorporating with K-Means[J]. Neurocomputing, 2019,361:126-136. doi: 10.1016/j.neucom.2019.06.041
[2]	刘景美, 韩庆庆, 沈志威, 等. 采用k均值聚类的物理层密钥生成方案[J]. 西安电子科技大学学报, 2019,46(1):8-13.
	LIU Jingmei, HAN Qingqing, SHEN Zhiwei, et al. Method for Secret Key Generation Using k-menas Clustering[J]. Journal of Xidian University, 2019,46(1):8-13.
[3]	REZA M N, NA I S, BAEK S W, et al. Rice Yield EstimationBased on k-means Clustering with Graph-cut Segmentation using Low-altitude UAV Image[J]. Biosystems Engineering, 2019,177:109-121. doi: 10.1016/j.biosystemseng.2018.09.014
[4]	刘永利, 郭呈怡, 刘静, 等. 结合FCS的多视图模糊聚类算法[J]. 西安电子科技大学学报, 2019,46(4):99-106.
	LIU Yongli, GUO Chengyi, LIU Jing, et al. Multi-view Fuzzy Clustering Algorithm Using FCS[J]. Journal of Xidian University, 2019,46(4):99-106.
[5]	CAPO M, PEREZ A, LOZANO J A. An Efficient Approximation to the k-means Clustering for Massive Data[J]. Knowledge-Based Systems, 2017,117:56-69. doi: 10.1016/j.knosys.2016.06.031
[6]	DENG T T, CROOKES D, SIDDIQUI F, et al. A New Real-time FPGA-based Implementation of k-means Clustering for Image [C]//Communications in Computer and Information Science: 924(2). Heidelberg: Springer Verlag, 2018: 468-477.
[7]	AMATO F, BARBARESCHI M, COZZOLINO G, et al. Outperforming Image Segmentation by Exploiting Approximate k-means Algorithm [C]//Springer Proceedings in Mathematics and Statistics: 217. New York: Springer New York LLC, 2017: 31-38.
[8]	HU J J, LI Z J, YANG M, et al. A High-accuracy Approximate Adder with Correct Sign Calculation[J]. Integration, 2019,65:370-388. doi: 10.1016/j.vlsi.2017.09.003
[9]	JAVED R H, SIDDIQUE A, HAFIZ R, et al. ApproxCT:Approximate Clustering Techniques for Energy Efficient Computer Vision in Cyber-physical Systems [C]//Proceedings of the 2018 International Conference on Open Source Systems and Technologies. Piscataway: IEEE, 2018: 64-70.
[10]	HUANGP H, WANG C H, MA R Z, et al. A Hardware/Software Co-design Method for Approximate Semi-supervised k-means Clustering [C]//Proceedings of the 2018 IEEE Computer Society Annual Symposium on VLSI. Washington: IEEE Computer Society, 2018: 575-580.
[11]	SAEGUSA T, MARUYAMA T. An FPGA Implementation of k-means Clustering for Color Images Based on Kd-tree [C]//Proceedings of the 2006 International Conference on Field Programmable Logic and Applications. Washington: IEEE Computer Society, 2006: 567-572.
[12]	TIAN Y, ZHANG Q, WANG T, et al. ApproxMA: Approximate Memory Access for Dynamic Precision Scaling [C]//Proceedings of the 2015 ACM Great Lakes Symposium on VLSI. New York: ACM, 2015: 337-342.
[13]	FADAEI A, KHASTEH S H. Enhanced k-means Re-clustering over Dynamic Network[J]. Expert Systems with Application, 2019,132:126-140. doi: 10.1016/j.eswa.2019.04.061
[14]	YU S S, CHU S W, WANG C M, et al. Two Improved k-means Algorithm[J]. Applied Soft Computing Journal, 2018,68:747-755. doi: 10.1016/j.asoc.2017.08.032
[15]	ZHANG G, ZHANG C C, ZHANG H Y. Improved k-means Algorithm Based on Density Canopy[J]. Knowledge-Based Systems, 2018,145:289-297. doi: 10.1016/j.knosys.2018.01.031
[16]	CHIPPA V K, MOHAPATRA D, ROY K, et al. Scalable Effort Hardware Design[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2014,22(9):2004-2016. doi: 10.1109/TVLSI.2013.2276759
[17]	ZHANG Q, XU Q. ApproxIt: a Quality Management Framework of Approximate Computing for Iterative Methods[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017,148(11):1-13.
[18]	CHIPPA V K, ROY K, CHAKRADHAR S T, et al. Managing the Quality vs. Efficiency Trade-off Using Dynamic Effort Scaling[J]. Transactions on Embedded Computing Systems, 2013,12(2):90.

数据集	功耗
数据集	Proposed	ApproxMA	HAA	DES
Iris	5.757	5.962	6.457	6.157
Breasttissue	5.783	5.998	6.487	6.187
Seeds	5.790	6.157	6.517	6.199
Glass	5.792	6.174	6.527	6.207