信息技术XINXUISHU2021年第3期改进的kNN分类算法在工业物联网中的应用 高增亮-王霞"，杨鹏2
(1.工业互联网创新中心(上海)有限公司，上海201306；
2.上海华峰创享互联网络科技有限公司，上海201315)
摘要：在工业物联网中，k近邻分类(kNN)被广泛应用于缺陷产品识别和异常检测。但kNN自身存在计算复杂度高、不适用于分布式环境等缺点。因此，文中提出了一种安全有效的分布式kNN分类算法，以防止信息泄漏和控制流泄漏，同时支持分布式服务器上的大规模数据分类。首先设计了一个安全有效的向量同态加密方案。在该方案的基础上，提出了DkNN，有效地实现了数据流的机密性、kNN查询和类标记，同时实现了对加密数据的同态操作。实验结果表明，提出的DkNN算法能够满足实际需要。 关键词：工业物联网；机器学习；安全和隐私；kNN
中图分类号：TP391文献标识码：A文章编号：1009-2552(2021)03-0021-05
sis 6326
DOI:10.13274/jki.hdzj.2021.03.005
Application of improved kNN classification algorithm in industrial Internet of Things
GAO Zeng-liang1,WANG Xia1,YANG Peng2
(1.Industrial Internet Innovation Center(Shanghai)Co.,Ltd・,Shanghai201306,China； 2.Shanghai Huafeng Chuangxiang Internet Technology Co.,Ltd・,Shanghai201315,China)
Abstract:In the industrial Internet of Things,k-nearest neighbor classification is widely used in defective product identification and abnormal detection.However,kNN itself has high computational complexity and is not suitable for distributed environments・Therefore,this paper proposes a safe and effective distributed kNN classification algorithm to prevent information leakage and control flow leakage,while supporting large-scale data classification on distributed servers・First,a safe and effective vector homomorphic encryption scheme is designed by constructing a key exchange matrix and a noise matrix.On the basis of the designed VHE scheme,DkNN is proposed,which effectively realizes the confidentiality of data stream,kNN query and class labeling,and simultaneously realizes the homomorphic operation of enciypted data.Experimental results show that the proposed DkNN algorithm can meet actual needs・
Key words:Industrial internet of things;machine learning；security and privacy；kNN
o引言
随着人工智能技术的飞速发展，智能控制以其模仿人类操作者的方式，为工业物联网(HOT)
基金项目：国家自然科学基金(61502061)
作者简介：髙增亮(1987-)，男，学士，研究方向为工业互联网领域标识解析、工业互联云平台、大数据分析等技术研
究和系统开发。的智能化、自动化和经济化带来了新的途径。作为最常用的机器学习算法之一，k-最近邻算法(K-NearestNeighbor,kNN)根据相邻对象的多个投票结果，将对象划分为k个近邻中最常见的类［4旳。但kNN算法计算复杂度高，如果需要分析的数据量大、特征量大，则需要消耗大量的计算资源［6'7］o如何在保证准确率的前提下实现高
—21—
改进的kNN分类算法在工业物联网中的应用—
—高增亮等
效、安全的kNN分类，仍然是一个具有挑战性的课题29〕。此外，现有的控制方案假设数据维护在一个功能强大的服务器上，而工业控制系统通常是分布式的，这意味着需要一个分布式解决方案。本文针对智能工业控制系统提出了一种安全有效的分布式kNN分类算法(Distributed kNN, DkNN)o首先设计了一个安全高效的VHE方案(secure and efficient vector homomorphic encryption, SEVHE)，实现了语义安全和高效的数据加密，然后在设计的SE-VHE的基础上提出了DkNN，以支持对加密训练样本进行高效的kNN分类，且分类精度高。此外，考虑到数据是在多个服务器上单独维护的，利用Map/Reduce体系结构实现了并行分布式的数据分类。
1SEVHE的原理
1.1VHE的不足
原始的VHE"®不够安全，无法抵抗现有的攻击，即攻击者可以分别从密钥交换矩阵或密文中恢复密钥或明文向量[⑴。此外，在原始VHE 中，每个向量和矩阵中的元素都表示为二进制字符串。高维向量的运算是逐点进行的，需要大容量的公钥加密，计算量大。由于原始VHE中向量或矩阵的二进制表示，对高维向量的运算会导致大量的计算和通信开销。例如，加密一个500维的向量，公钥的大小应为120MB，加密时间最长为27s，因此原始VHE不能用于IloT。在本文中，设计了一个新的VHE方案，它是DkNN的密码原语，具有更好的安全性和更高的性能。SEV11E源于原始VHE。具体地说，在 密钥生成过程中，设计了一种新的密钥交换矩阵来防止基于可逆矩阵的密钥恢复，并在数据加密中使用噪声向量对明文向量进行模糊处理。这样，就不能分别从密文和密钥交换矩阵中恢复明文向量和密钥，从而实现了IND-CPA(Indistinguishability under chosen-plaintext attack)安全。此外，由于不使用向量或矩阵的二进制表示,SEVHE具有公钥大小小和加密时间开销低的优点。
1.2方案描述
首先介绍了生成SEVHE参数的两种重要算法Gen I n v和Trans o
—22—
算法1生成两个矩阵人和厶，其中M"，其中n由密钥大小决定。注意k值越大，厶和12的随机性越好。
算法1Genlnv
输入：几
输出山，近
生成两个单位矩阵人,/2eZ；xn
for i=1to k do
随机生成向量:[s,d,o],s,〃r{-1,0,1}
if o=0then
交换列厶[刃和
交换行虹叮和皿刃
elseif oH0then
A[$]—A[叮一。・/】[〃]
/[d]j/】"]+o-/2[5]
endif
endfor
算法2Trans
输入：S°m
输出:S,M
生成两个矩阵PsFn-Genhw(n')
生成两个矩阵，卩和xw
构造两个矩阵,S x=[/,r]其中/是m的单位矩阵，并r S/j—TA t
且M，=[4]e<x"
计算S=S t P s和M=P m M,
设计了一种新的密钥交换操作Trans，其中n 和"分别表示旧密钥矩阵e Z；xn和变换后的密钥矩阵S e Z：x“'的维数。修改后的密钥切换操作在算法2中进行了描述。
在算法2中，给定一个密文c°w和它的密钥S“d，那么S和M被生成。因此，新密文可由c=计算，其正确性由式(1)保证：
Sc=SMc old=S t P s P m M t c M
="，叫九；二S old c o,d(1)
SEVHE由四个概率多项式时间算法组成: VHE=(VHE.Setup,VHE.KG,VHE.Enc,VHE. Dec)o
①VHE.Setup(入)，在给定一个安全参数入，
改进的kNN分类算法在工业物联网中的应用—
—高增亮等
m,n,p,q,w随机选取m<n和q》p，在Z(/上
选取一个离散高斯噪声分布;V。注意，模数g是根据入选择的，以保证安全性。系统参数Param=
(m,n,p,q,w，x)已公开。
②VHE.KG(Param)，执行算法2生成(S, M)—升讪)，其中/£是一个单位矩阵。
密钥S w Z；xn保持私有，加密密钥M丘被释放。注意，根据算法2可知SM=wI o
③VHE.Enc(%,M)，在Z；处随机选择一个
小噪声向量er"，明文x加密为c=Mx+e，其中"Z；为明文向量为密文向量,MeZ；xm 为加密密钥。注意，为了保证明文的安全性，加入噪声e来生成密文。
④VHE.Dec(c,S)，通过计算％|来恢
I W」g
复明文％E Z；，其中c e Z；是对应的密文,S e
Z；g是密钥。请注意，解密的正确性由式(2)保证：
x I=F(他+e)I=L+5e I
\W\I U)」g I W A
(2)
容易看出，要用密钥S正确地从c中恢复久，就必须满足I Sei<；号。具体来说，有切Sil el<；号。因此,11：£表示丨el的上界，那么可以得到
与E<w/2[10]的原始VHE相比，方案中丨e I 的上界有所降低。然而，如果E的设置正确，它在应用于D
kNN时并不影响其正确性。
甘德怀此外,SEVHE支持原始VHE的所有同态运算，包括加法、线性变换和加权内积〔⑹。然而，保证同态的条件也会随之改变。
2DkNN算法原理
在这一节，讲说明提出了DkNN算法是如何实现基于SEVHE的加密训练样本的kNN分类。
2.1相似度的安全计算
这些设备将训练数据集D上传到云中分布的服务器上。。可以表示为一个包含"个数据记录，…，殆的表。在D中，每个记录有=
[hi，...,Em]，具有m+1个属性,i=1,2, (71)
特别地，第(m+1)-个属性q是类标签。然后，控制中心有一个查询集，包括N个查询q｛,q2,…，张，其中每个查询为qj=助，…，g加],7=1, 2,…,N。
为了保护数据集，将D=\t x,t2，-,t n｝的密文D'存储在云中的一个服务器(或多个服务器进行存储复制)。
科学研究方法论控制中心对数据集进行kNN查询，并从云端获取工业控制系统的分类结果。控制中心发送的N个查询qt，q2,,q N也受到保护。在重新接收加密的N个查询后，云中的主服务器将这些查询拆分并映射到维护数据的服务器。每个分布式服务器计算存储的数据记录与每个查询qj之间的相似度得分，出qj中最相似的k条记录。这里用：MV分类中的内积g"，来评价相似性。每个服务器计算的相似性分数返回到主服务器，并进一步转发到控制中心。然而，在这个过程中，主要的挑战是如何从加密的f，和Qj中计算为了解决这个问题，在加密的h上使用线性变换运算，在DkNN中使用变换矩阵G=q：。
2.2算法组成
初始化负责初始化整个系统，为kNN分类准备训练数据集。
①设置：控制中心调用设置来生成系统参数Param、加密密钥和密钥S。。然后，控制中心向公众发布Param和并对50保密。
②数据上传：设备记录加密训练数据集D=仏，切…儿｝。具体而言，数据记录h中的ti [15]和的+1](即类标签q)分别被加密。也就是说，装置首先计算/；[1：m]—VHE.Enc(i;
)和c*VHE.Enc(q,Mo)，其中t' Jl：m]是心的前m个属性的密文,c；是相应类标签c,.的密文。然后，设备将D'=｛(仍[1：m],c；), lWiWn｝上传到云端服务器。此外，为了提高计算开销，该装置还可以对-进行整体加密：说―VHE.Enc(i(,M0)o这样，可以为设备保存加密操作。
分类利用线性变换运算，利用加密后的匕基于内积计算相似度得分。
①QueryGen：对于单个查询向量g=[91，乞，
—23—
改进的kNN分类算法在工业物联网中的应用—
—高增亮等，有一个对应的转换矩阵，为式(3)所示:
⑷Qi…％°
00001
G—(3)
控制中心需要计算查询与数据记录之间的相
似度得分。如果有N个查询91川2，控制中
心必须逐一计算这些查询的相似度得分。为了减
少操作次数，可以使用批处理技术同时处理N个
查询。具体地说，对应于/V个查询的转换矩阵可
以构造为式(4)：
绝缘子串"Vn G=:
Q n\
o-
o
<71m
GVm
(4)
L0
这样，控制中心可以执行N次加密查询，同时获得相似度得分。
②ScoreCalculate：云上的主服务器从控制中心收到加密的查询，即密钥交换矩阵M，将M分 发给所有维护数据集的服务器。在接收到M后，每个服务器计算D'中每个巧的相似性分数如;，并将"+,••/｝发送给主服务器。由于K岛,…是独立的，多个服务器可以并行计算加密的内积在这里，相似度是查询向量和数据集的内积，每个是相似度的密文。主服务器最终收集从分布式服务器返回的所有加密相似度分数并将其转发给控制中心。
为了处理实际中大量的训练数据，利用Map/ Reduce的并行框架计算矩阵乘法为NJM x D'，其中M是用户查询对应的密钥交换矩阵，/)'=｛肾再,…，瑶是加密的训练数据集,M=上，…, s；｝是加密的相似性分数。对于Map/Reduce上的矩阵乘法，可以考虑元素对的基本技术，即映射器独立地计算每对元素的乘法，而reducer将每个输出元素的结果合并。然而，这种逐元素技术带来了大量的计算和通信开销。由于…上是独立的，分布式服务器使用相同的密钥交换矩阵M 来计算加密的相似性分数，因此采用逐列分块技术来提高矩阵乘法的效率，其中第一个矩阵M可以分解成行向量，第二矩阵”可分解为列向量。
③LabelDec：控制中心用新的密钥&将M解密为N=\Gt,\i=\,-,n\得到Gt：—VHE.Dec 如式(5)所示，其中为相似性得分,q为类标签。
rq T t i[l-m]
Gt严(5)
c i
对于N个查询的批量计算，控制服务器使用新的密钥&解密得到厲，如式(6)所示，其中g", [l：m]为相似度,q为类标签。
血[1：771厂
血[1：m]
Gt i=(6) 7么[1：m]
6
④Majority V ote：控制中心从k个最近邻的投票中计算出多数类，最后为每个查询乞获取类标签勺。
2.3安全标记
DkNN保护训练数据集D、查询向量g和相应分类结果q的机密性。具体地说，训练数据集D 由SEVHE加密，其IND-CPA安全性可以归结为容错学习问题(learning with error,LWE)。在没有S o的情况下，任何敌方都无法获得关于D的任何信息。查询向量g用算法2转换生成为也可以认为是G在密钥S。和&下的加密。在算法2中进行转换，除了G的度外，不能从M中提取G 的任何信息。根据SE-VHE的同态操作，类标签Cq也被SEVHE加密，只有控制中心能够用新的密钥S，恢复Gt io由于SEVHE是IND-CPA安全的，类标签Cq的保密性基于LWE问题。综上所述，只要S。和&由控制中心私自保存，并且LWE 问题是一个棘手的问题，那么在DkNN中，任何敌人都无法获得任何关于D、g或f的知识。
3实验与结果
西南票务网
3.1实验设置
为了证明DkNN的有效性，在此进行实验。实验中,DkNN中的设备和控制中心的计算任务在运行WindowslO的17CPU和16GB内存的笔记本电脑上进行，云计算在E5CPU和32GB内存的服务器上执行，系统为CentOS8.10
—24—
改进的kNN 分类算法在工业物联网中的应用——高增亮 等
3.2 结果与评估在UClg 中对多个数据集运行传统的kNN 算法和DkNN 算法，并比较结果。
表1在多个数据集中的准确度对比结果
数据集
n N m kNN
DkNN
banknote 107927540.970.97cread it 522
131
15
0.88
0.87vote 18547160.900.89
spambase 3680
921
570.880.87letter 1244311
16
0.99
0.99mfeat-zemike
32080470.810.81
nursery 6868
1718
8
0.98
0.98
(a )时间开销
一"* — Dimension m=32
(&)m
u >b s
1S O U
u话语标记
.2l B
.a u n u l u l o
CJ
0.50
0.49
0.48
0.470.460.45图1 DkNN 算法性能测试结果
20
40 60 80 100
Number of Queries
(b )通信开销
如表1所示,DkNN 可以达到与传统kNN 算
法几乎相同的分类精度。这里的训练数据的数量 是n，训练中的每个属性的数目是ni,kNN 的查询
数目是2。值得注意的是，尽管DkNN 算法不能
获得比传统kNN 算法更高的分类精度，但它具有 隐私保护的重要优点。原始的kNN 不能提供这
个属性，而在HoT 屮它是必须的，因为保护用户 的隐私是至关重要的。训练数据集是从IIoT 中
各种传感器的数据流、系统状态或测量值中提取 出来的，这些数据非常敏感。因此，有必要用
DkNN 算法来保护IIoT 中的私有信息。
图1展示了 DkNN 算法的性能测试结果。由图1可知，如图1(a)所示，生成M 的时间
成本随着查询的数量而增加。在QueryGen 阶段 中的通信开销随着查询的数量而缓慢增加，如图
1(b)所示。特别是，如果查询数超过100,DkNN 可以将通信开销减少50%。4结束语
本文针对智能工业控制系统提出了一种安全
有效的分布式kNN 分类算法。具体来说，设计了
一个新的VHE 方案，它满足语义安全性，并且在 公钥存储和向量加密方面具有高效性。利用所设
计的VHE 算法，提出了一种基于相似度的DkNN 算法对分布式服务器上的大规模加密数据进行有 效分类。在实验中，展示了提出DkNN 算法的精 确度与kNN 算法相似。
参考文献：
[1] 王莹，王金旺.T 业物联网技术方案及发展大潮[J].
电子产品世界,2018,25(3) ：9 -14.
[2] Kohn W , Zabinsky Z , Nerode A. A micro-grid distribu
ted intelligent control and management system [ J ]. IEEE Transactions on Smart Grid , 2015, 6(6) ：2964 -
2974.
[3] 左培良，梁春光，周琴•工业自动化中物联网技术的
应用研究[J].科技创新与应用,2019(5) =124 -125.
[4] 韩林峰，吴晟.通过评分特征优化基于K 近邻的协同
过滤算法[J].信息技术,2018,42(12):75 -79.
[5] 秦一菲，马明辉，王岩松，等•基于改进KNN 算法的交
通流异常数据修复方法[J].计算机测量与控制，
2018,26(12) ：180 -184.
[6 ] Dairi A , Harrou F , Sun Y , et al. Obstacle detection for
intelligent transportation systems using deep stacked au toencoder and k-nearest neighbor scheme [ J ]. IEEE Sensors Journal , 2018： 5122 -5132.
[7] 伏浩铭.一种改进的ML-KNN 多标记分类方法研究
[D].成都：电子科技大学,2017.
[8] 梁聪，夏书银，陈子忠•基于参考点的改进k 近邻分类
算法[J].计算机工程,2019,45(2)=167 - 172.
(下转第31页)
—25
—
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议