Author: h4rdy@WhaleShark
0x00 KNN(K-NearestNeighbor)算法
k近邻算法采用不同特征值之间的距离方法进行分类的一个分类算法。
0x01 最容易理解dKNN算法的一个例子
图中绿色圆要被分类到哪一类(蓝色方形?红色三角?)取离绿色圆最近的K个样本,哪类样本所占的比例多,就分到哪一类。当K=3的时候,红色三角形所占比例为2/3,绿色圆将被分类到红色三角形类。当K=5的时候,蓝色方形所占比例为3/5,绿色圆将被分类到蓝色方形类。
0x02 比较实际的利用KNN算法例子
有两个类型的电影,爱情片和动作片。我们以打斗镜头和亲吻镜头在电影中出现的次数对电影进行分类。并且我们有一些分好类了的数据集。
打斗镜头出现数量(次) | 亲吻镜头出现数量(次) | 电影类型 |
---|---|---|
2 | 10 | 爱情片 |
3 | 15 | 爱情片 |
4 | 11 | 爱情片 |
5 | 13 | 爱情片 |
5 | 14 | 爱情片 |
15 | 3 | 动作片 |
14 | 5 | 动作片 |
10 | 2 | 动作片 |
18 | 4 | 动作片 |
11 | 2 | 动作片 |
0x03 将数据特征化
将数据特征化用来计算数据集中的点与当前未知类别点之间的距离。
当给一个未知的数据让机器进行分类时:
经过计算可以得到:d1, d2, d3, d4, d5, d6…..
将得到的所有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 检测异常行为操作
一个标记了每个集合(每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的值理解为坐标系的坐标点。
第三步:测试算法并使用
#训练样本数
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 总结
此案例的关键点是将数据特征化,也就是将具体的命令转换为具体的数值。在检测异常行为操作这个案例中,因为是数据集为某个用户历史执行过的命令,因此我们以命令出现过的频率作为数据特征化的特征对操作命令向量化。当然在实际应用中不单单以频率为特征,还可以加入相似度等特征进行处理。