【技术分享】KNN算法检测异常操作行为（文末有福利~）

0x00 KNN(K-NearestNeighbor)算法

k近邻算法是采用不同特征值之间的距离方法进行分类的一个分类算法。

• 优点: 精度高，对异常值不敏感

• 缺点: 计算复杂度高，空间复杂度高，对数据的局部结构非常敏感

• 所需数据源: 数值型和标称型

• 通常k为不大于20的整数

0x01 最容易理解的KNN算法的一个例子

图中绿色圆要被分类到哪一类(蓝色方形？红色三角?)取离绿色圆最近的K个样本，哪类样本所占的比例多，就分到哪一类。当K=3的时候，红色三角形所占比例为2/3，绿色圆将被分类到红色三角形类。当K=5的时候，蓝色方形所占比例为3/5，绿色圆将被分类到蓝色方形类。

对未知类别属性的数据集中的每个点依次执行以下操作:

1. 计算已知类别数据集中的点与当前未知类别点之间的距离

2. 按照距离递增次序排序

3. 选取与当前点距离最小的k个点

4. 确定前k个点所在类别的出现频率

5. 返回前k个点出现频率最高的类别作为当前点的预测分类

0x02 比较实际的利用KNN算法例子

有两个类型的电影，爱情片和动作片。我们以打斗镜头和亲吻镜头在电影中出现的次数对电影进行分类。并且我们有一些分好类了的数据集。

打斗镜头出现数量(次)	亲吻镜头出现数量(次)	电影类型
2	10	爱情片
3	15	爱情片
4	11	爱情片
5	13	爱情片
5	14	爱情片
15	3	动作片
14	5	动作片
10	2	动作片
18	4	动作片
11	2	动作片

0x03 将数据特征化

将数据特征化用来计算数据集中的点与当前未知类别点之间的距离。

分别以打斗镜头出现数量和亲吻镜头出现数量作为坐标系。

当给一个未知的数据让机器进行分类时:绿色点在坐标系中的坐标为(10, 5)

计算绿色点距离每个红色点和每个蓝色点的距离:

点到点的距离，可以根据勾股定理进行计算。

经过计算可以得到:

d1, d2, d3, d4, d5, d6.....

以此类推，当有N个常量的时候:

将得到的所有d进行递增次序排序,取前k个点,前k个点所在类别的出现频率高的那个类别即为对未知量的分类类别。

数值归一化

但是当数据集中某类数据的范围相比较其他数据范围更大的时候，即方程式中存在某个数字差值越大，就会对计算结果的影响越大。

例如:

这种情况下，(3000-1000)差值比(5-2)更大，就会造成(3000-1000)在计算结果中的权重更大。

在大多数情况下，我们对每个特征赋予的权重应该是一样的，因此有多个值的时候多个值应赋予相等的权重。在处理这种不同取值范围的特征值的时候，通常采用的方法是将数值归一化，比如将取值范围处理为0~1或 -1~1之间。

newValue=(oldValue−min)/(max−min)

例如在上述的电影分类中:当打斗镜头出现次数为5时，对5进行归一化得到新的结果:

0.2308=(5−2)/(15−2)

0x04 检测异常行为操作

一个1.5w行的cmd.txt文件，形如:

• 每1行为执行过的命令，每100行为一个集合。

一个标记了每个集合(每100行)，是否为异常行为的sign.txt(共150行)标记文件。0为正常，1为异常。

• 其中如果某个集合(每100行)中出现至少1个异常命令，即整个集合被标记为1

第一步: 数据特征提取

由于原始数据中标记文件是以100个数据为集合的，因此需要将a.txt文件数据进行整理及特征提取。将所有的命令整理得到cmd_list和frequency:

cmd_list = [['cpp','sh',...,'col'],['sh',...,'windows'],...['mailbox','ksh',...'ls']]
len(cmd_list) = 150

用FreqDist(统计文本词频)将所有的命令按频率高低整理为形如:

frequency_list = FreqDist(list(cmd_list)).keys()

frequency_list = ['vacation', 'sh', 'sendmail', 'cpp', 'xrdb', 'mkpts', 'test',....]

整理样本的标记结果，因为样本中前5k行为正常行为，因此标记结果都为

y = list()
a = open('sign.txt')
for line in a.readlines():
    line=line.strip('\n')
    y.append(line)

第二步: 将数据特征化

使用词集将操作命令向量化。将命令数据转换为具体的数值，以命令出现的频率作为参考进行将命令转化为具体数据特征。

user_cmd_feature = list()
for every_cmd_list in cmd_list:
    v = [0]*len(frequency_list)
    # 将按频率排序的所有的命令初始为0
    for i in range(0, len(frequency_list)):
            if list(frequency_list)[i] in every_cmd_list:
            # 判断按频率排序的所有的命令是否在每组命令中出现过
            v[i] += 1
    user_cmd_feature.append(v)

v的结果格式如图，可以将v的值理解为坐标系的坐标点。

第三步: 测试算法并使用

使用python库，传入数据进行计算。

#训练样本数
N = 90

x_train = user_cmd_feature[:N]
y_train = y[:N]
# 训练数据集

x_test = user_cmd_feature[N:]
y_test = y[N:]
# 测试数据集

neigh = KNeighborsClassifier(n_neighbors=3)
# 此处设置k=3
neigh.fit(x_train, y_train)

y_predict = neigh.predict(x_test)
# 传入测试数据
print(y_predict)
# 测试数据计算结果

score=np.mean(y_test==y_predict)*100
print(score)
# 正确率

0x05 总结

此案例的关键点是将数据特征化，也就是将具体的命令转换为具体的数值。在检测异常行为操作这个案例中，因为是数据集为某个用户历史执行过的命令，因此我们以命令出现过的频率作为数据特征化的特征对操作命令向量化。当然在实际应用中不单单以频率为特征，还可以加入相似度等特征进行处理。

0x06 参考

• 《web安全之机器学习入门》[https://item.jd.com/12158965.html]

• 《深度学习》[https://item.jd.com/12128543.html]

赠书福利

关注MLSRC官方微博，将有机会获赠深度学习领域奠基性的经典畅销书

---《深度学习》

截止时间：11月15日18：00

MLSRC ∣官方微博长按，识别二维码，加关注