K-近接アルゴリズムの紹介と実践

K-近接アルゴリズムの概要
KNNアルゴリズム(K-Nearest Neighbors)アルゴリズムは機械学習分野で広く用いられている分類アルゴリズムの一つであり,KNNとは,各サンプルの分類が最も近いK個の隣人で表すことができるということである.
KNNアルゴリズムの基本的な考え方は:
1、訓練セットデータが与えられ、各訓練セットデータはすでに分類されている.
2、初期のテストデータaを設定し、aからトレーニングセットのすべてのデータまでのユークリッド距離を計算し、ソートする.
3、訓練セットがaから最も近いK個の訓練セットデータを選択する.
4、k個の訓練セットデータを比較し、中に最も多く現れる分類タイプを選択し、この分類タイプは最終テストデータaの分類である.
PythonにおけるKNN関連API
pythonではsklearnのneighbors moduleを簡単に使用してKNNモデルを作成できます.
APIドキュメントでは、neighborsモジュールの方法は次のとおりです.
次に,簡単な例を用いてKNNアルゴリズムの実装について述べる.
K近接アルゴリズムのhello world
まず、2 D空間上のいくつかの点を作成してテストします.

from sklearn.neighbors import NearestNeighbors
import numpy as np
X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])

以上のコードから,我々の実験に用いる2次元空間に6つの試験点を作成し,次にKNNアルゴリズムを用いて,我々の6つの点に適した分類モデルを訓練することを示した.

#NearestNeighbors        
#n_neighbors=5,    5，    k        
#algorithm='auto',            ，auto                  
#fit(X)   X      
nbrs = NearestNeighbors(n_neighbors=2, algorithm="ball_tree").fit(X) 

これで、私たちの最も簡単なKNNの分類器が完成しました.次に効果を見てみましょう.

#   indices        k     ，distance    
distances, indices = nbrs.kneighbors(X)

結果は次の図のようになります.
1番目のマトリクスはdistancesマトリクスであり、2番目はk個の点に近い点の座標を表す.
次のコードの可視化結果も入力できます.

#      n          ，1      ，0         
print nbrs.kneighbors_graph(X).toarray() 

KNNアルゴリズムを用いて学習を監督する場合も非常に簡単です.
次の図に示します.
K近傍アルゴリズムを用いて異常動作を検出する
ハッカーがWebサーバに侵入した後、通常、いくつかのシステムの脆弱性を使用して権利を主張し、サーバのroot権限を獲得します.次の仕事では、Linuxサーバのbash操作ログを収集し、訓練を通じて特定のユーザーの使用習慣を識別し、さらに異常操作を識別します.
データの状況は次のようになります.
トレーニングデータには50人のユーザーの操作ログが含まれており、各ログには15000件の操作コマンドが含まれており、最初の5000件は正常な操作であり、後ろの10000件のランダムパッケージには異常な操作が含まれています.訓練を容易にするために、私たちは100のコマンドをlabelで1つの操作シーケンスと見なしています.txtには、各ユーザの後100の操作シーケンスに異常があるか否かに対応するラベルがある.正常は0、異常は1です.
ソースコードは次のとおりです.

# -*- coding:utf-8 -*-
import sys
import urllib
import re
from hmmlearn import hmm
import numpy as np
from sklearn.externals import joblib
import nltk
import matplotlib.pyplot as plt
from nltk.probability import FreqDist
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import classification_report
from sklearn import metrics
#     
N=90
def load_user_cmd(filename):
    cmd_list=[]
    dist_max=[]
    dist_min=[]
    dist=[]
    with open(filename) as f:
        i=0
        x=[]
        for line in f:
            line=line.strip('
')
            x.append(line)
            dist.append(line)
            i+=1
            # 100           
            if i == 100:
                cmd_list.append(x)
                x=[]
                i=0
    #         50         50   
    fdist =list(FreqDist(dist).keys())
    dist_max=set(fdist[0:50])
    dist_min = set(fdist[-50:])
    return cmd_list,dist_max,dist_min

#         
def get_user_cmd_feature(user_cmd_list,dist_max,dist_min):
    user_cmd_feature=[]
    for cmd_block in user_cmd_list:
        # 100        ，        ，              
        # list  set  
        f1=len(set(cmd_block))
        #FreqDist           :       
        fdist = list(FreqDist(cmd_block).keys())
        #      10   
        f2=fdist[0:10]
        #     10   
        f3 = fdist[-10:]
        f2 = len(set(f2) & set(dist_max))
        f3 = len(set(f3) & set(dist_min))
        #                     50          50        
        #f1:              
        #f2:          10                  
        #f3:           10                   
        x=[f1,f2,f3]
        user_cmd_feature.append(x)
    return user_cmd_feature

def get_label(filename,index=0):
    x=[]
    with open(filename) as f:
        for line in f:
            line=line.strip('
')
            x.append( int(line.split()[index]))
    return x

if __name__ == '__main__':    
    user_cmd_list,user_cmd_dist_max,user_cmd_dist_min=load_user_cmd("../data/MasqueradeDat/User3")
    user_cmd_feature=get_user_cmd_feature(user_cmd_list,user_cmd_dist_max,user_cmd_dist_min)
    #index=2   User3   label
    labels=get_label("../data/MasqueradeDat/label.txt",2)
    # 5000           50        
    y=[0]*50+labels
    x_train=user_cmd_feature[0:N]
    y_train=y[0:N]
    x_test=user_cmd_feature[N:150]
    y_test=y[N:150]
    neigh = KNeighborsClassifier(n_neighbors=3)
    neigh.fit(x_train, y_train)
    y_predict=neigh.predict(x_test)
    score=np.mean(y_test==y_predict)*100
    print(y_test)
    print(y_predict)
    print(score)
    print(classification_report(y_test, y_predict))
    print(metrics.confusion_matrix(y_test, y_predict))

実行してみると、精度は約83.3%で、結果はあまり理想的ではありません.
検証効果を向上させるには、異常操作の発生をより全面的に考慮する必要があります.そこで次に,全量比較を用いて,ユーザの異常の有無を再訓練する.
データ収集と洗浄の際,dictデータ構造を用いて,すべてのコマンドを再削除した後に大きなベクトル空間を形成し,各コマンドは特徴を表し,まずすべてのコマンドを遍歴することによって対応する語集を生成する.だからload_を書き直しましたuser_cmdメソッドは、次のとおりです.

def load_user_cmd_new(filename):
    cmd_list=[]
    dist=[]
    with open(filename) as f:
        i=0
        x=[]
        for line in f:
            line=line.strip('
')
            x.append(line)
            dist.append(line)
            i+=1
            if i == 100:
                cmd_list.append(x)
                x=[]
                i=0
    fdist = list(FreqDist(dist).keys())
    return cmd_list,fdist

語集を得た後,命令を量子化し,モデルの訓練を容易にする.だからget_を書き直すuser_Featureメソッドで、ユーザーフィーチャーを再取得します.

def get_user_cmd_feature_new(user_cmd_list,dist):
    user_cmd_feature=[]
    for cmd_list in user_cmd_list:
        v=[0]*len(dist)
        for i in range(0,len(dist)):
            if dist[i] in cmd_list:
                v[i]+=1
        user_cmd_feature.append(v)
    return user_cmd_feature

新しいモデルを訓練するのは以前の方法と同じです.
効果検証の場合、クロス検証を使用して、10回のランダムサンプリングと検証を通じて、検証の信頼性を高めます.

score=cross_val_score(neigh,user_cmd_feature,y,n_jobs = -1,cv=10)

最後に,精度が約93%程度の良好なモデルを得ることができた.
以上のいくつかの例を除き,KNNを用いたwebshell検出とrootkit検出の例を参考にすることができる.https://github.com/traviszeng/MLWithWebSecurity/tree/master/code/KNNsample