k-近隣アルゴリズム(kNN)

引用する
本節では,kNNアルゴリズムの基本理論と距離測定法を用いて物品を分類する方法を紹介する.次に、pythonを使用してテキストファイルからデータをインポートして解析し、多くのデータソースが存在する場合、距離を計算する際に発生する一般的なエラーを回避する方法について説明します.
k-近隣アルゴリズムの概要
k‐近隣(k Nearest Neighbors)アルゴリズムを,異なる特徴間の距離を測定する方法で分類した.その動作原理は、サンプルデータセットが存在し、サンプルセットの各データにラベルが存在することです.すなわち、サンプルの各データと所属分類の対応関係を知っています.ラベルのない新しいデータを入力した後、新しいデータの各特徴とサンプルセットデータに対応する特徴を比較し、アルゴリズムはサンプルセットの特徴が最も類似しているデータの分類ラベルを抽出する.一般に,試料データセットの前のk個の最も類似したデータのみを選択し,これがk−近隣アルゴリズムにおけるkの出所であり,通常kは20未満の整数である.最後に,k個の最も類似したデータの中で出現回数が最も多い分類を,新しいデータの分類として選択する.
k-近隣アルゴリズムの利点は精度が高く、異常値に敏感ではなく、データ入力仮定がないことである.欠点は計算の複雑さが高く,空間の複雑さが高いことである.数値および公称型データに適用されます.
準備知識:pythonを使用してデータをインポートする
まず、kNNという名前を作成する.pyのpythonモジュールを追加し、次のコードを追加します.

from numpy import *
import operator

def createDataSet():
    group = array([[1.0,1.1],[1.0,1.0],[0,0.1]])
    labels =['A','A','B','B']
    return group,labels

python開発環境に入ったら、次のコマンドを入力します.

>>> import kNN
>>> group,labels =kNN.createDataSet()
>>> group
array([[ 1. ,  1.1],
       [ 1. ,  1. ],
       [ 0. ,  0.1]])
>>> labels
['A', 'A', 'B', 'B']

kNNアルゴリズムの実装
k近隣アルゴリズムを使用して、各グループのデータをクラスに分割します.その擬似コードは次のとおりです.
不明なカテゴリ属性のデータセットの各ポイントについて、次の操作を行います.

既知のカテゴリデータセットのポイントと現在のポイントとの間の距離を計算する.

は、距離の増加に従って順序付けされる.

現在の点から最も距離の小さいk個の点を選択する.

は、前のk点が存在するカテゴリの出現頻度を決定する.

は、前のk点の出現頻度が最も高いカテゴリを現在の点の予測分類として返す.

python関数classify()プログラムは次のようになります.

def classify(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX, (dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5
    sortedDistIndicies = distances.argsort()     
    classCount={}          
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    sortedClassCount = sorted(classCount.iteritems(),
      key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

注意:classify()関数には4つの入力パラメータがあります.分類に使用される入力ベクトルはinX、入力されるトレーニングサンプルセットはdataSet、ラベルベクトルはlabels、最後のパラメータkは、ラベルベクトルの要素数とマトリクスdataSetの行数が同じである最近隣接するデータを選択するための数を表します.
例:k近隣アルゴリズムを用いてデートサイトのペアリング結果を改善する
デートサイトでk近隣アルゴリズムを使用するには:

データ収集:テキストファイルを提供します.

データの準備:pythonを使用してテキストファイルを解析します.

解析データ:Matplotlibを使用して2 D拡散図を描画します.

トレーニングアルゴリズム:このステップはk近隣アルゴリズムには適用されません.

テストアルゴリズム:一部のデータをテストサンプルとして使用します.テストサンプルと非テストサンプルの違いは、テストサンプルはすでに分類が完了したデータであり、事前に分類が実際のカテゴリと異なる場合はerrorとマークすることである.

アルゴリズム:簡単なコマンドラインプログラムを生成し、いくつかの特徴データを入力して、相手が自分の好きなタイプであるかどうかを判断することができます.

データの準備:テキストファイルからデータを解析する
データをテキストファイルに保存し、サンプルデータごとに1行、合計1000行を占めます.まず,特処理データを分類器が許容できるフォーマットに変更しなければならない.kNNでpyでfile 2 matrixの関数を作成し、入力フォーマットの問題を処理します.テキストレコードをNumPyに変換する解析プログラムを以下に示します.

def file2matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())         #get the number of lines in the file
    returnMat = zeros((numberOfLines,3))        #prepare matrix to return
    classLabelVector = []                       #prepare labels return   
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat,classLabelVector

解析データ:Matplotlibを使用して散点図を作成する
まずMatplotlibを用いて元のデータの散点図を作成する.次の手順に従います.

import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,1],datingDataMat[:,2])
plt.show( )

データの準備:数値の正規化
手順は次のとおりです.

def autoNorm(dataSet)
    minVal =dataSet.min(0)
    maxVal =dataSet.max(0)
    ranges =maxVal-minVal
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shap[0]
    normDataSet = dataSet - tile(minVal,(m,1))
    normDataSet = normDataSet/tile(ranges.(m,1))
    return normDataSet,ranges, minVal

参考資料
[1]Peter Harrington, "Machine Learning in Action"ISBN 9781617290183,Printed in the United States of America. Manning Publications.
Machine Learning&Pattern Recognitionの詳細については、このブログと新浪微博songziに注目してください.tea.