KNN(k-NearestNeighbor)はministデータセットを識別する

KNNアルゴリズムの紹介
KNN(K Nearest Neighbors,K近傍)アルゴリズムは機械学習のすべてのアルゴリズムの中で理論が最も簡単で,最も理解されている.KNNは実例に基づく学習であり,新しいデータと訓練データの特徴値との間の距離を計算した後,K(K>=1)個の距離が最も近い隣人を選択して分類判断(投票法)または回帰を行う.K=1の場合、新しいデータは近隣のクラスに単純に割り当てられる.KNNアルゴリズムは監督学習か無監督学習か.まず,監督学習と無監督学習の定義を見てみる.監督学習では,データには明確なlabel(分類は離散分布,回帰は連続分布)があり,機械学習によって生成されたモデルに基づいて新しいデータを明確なクラスに分けたり予測値を得たりすることができる.非監督学習では,データにlabelはなく,機械学習のモデルはデータから抽出されたpattern(決定的特徴やクラスタリングなどを抽出する)である.たとえばクラスタリングは,学習したモデルに基づいて,新しいデータが「より似ている」元のデータ集合を判断する機械である.KNNアルゴリズムが分類に用いられる場合,訓練データごとに明確なlabelがあり,新しいデータのlabelを明確に判断することもでき,KNNが回帰に用いられる場合も隣人の値から明確な値を予測するため,KNNは監督学習に属する.
KNNアルゴリズムフロー

は、データのすべての特徴から新しいデータと既知のカテゴリデータセットのデータ点との距離

を計算する距離計算方式を選択する.

は、距離の増加順に並べ替える、現在の距離と最も小さいk個の点

を選択する.

離散分類について、k点の出現頻度が最も多いカテゴリを予測分類として返す.回帰については予測値

としてk個の点の重み付け値を返す.

最終予測カテゴリ

として、返されるk個のカテゴリの中で最も出現回数の多いカテゴリを投票により選択する.
KNNアルゴリズムキー

データのすべての特徴を比較可能な量子化しなければならない.データフィーチャーに非数値のタイプがある場合は、それを数値に量子化する手段を講じなければならない.例えば、サンプルフィーチャーに色(赤と黒と青)の1つが含まれている場合、色間に距離がないということは、色を階調値に変換することによって距離計算を実現することができる.また、サンプルには複数のパラメータがあり、各パラメータには独自の定義ドメインと値範囲があり、distance計算に与える影響も異なり、値の大きい影響力が値の小さいパラメータを覆うなどします.公平のために、サンプルパラメータはいくつかのscale処理をしなければならない.最も簡単な方法は、すべての特徴の数値が正規化されていることだ.

は、2つのサンプル間の距離を計算するためにdistance関数を必要とする.距離の定義には、オーステナイト距離、余弦距離、漢明距離、マンハッタン距離などがたくさんあります.一般に、距離メトリックとしてオーステナイト距離を選択しますが、これは連続変数にのみ適用されます.通常,いくつかの特殊なアルゴリズムを用いてメトリックを計算すると,K近傍分類精度が著しく向上し,例えば,大エッジ近傍法や近傍成分分析法を用いることができる.

はKの値Kがカスタム定数であることを決定し、Kの値も最後の推定に直接影響し、1つの選択K値法はcross−validate(クロス検証)誤差統計選択法を用いる.クロス検証の概念の前提は、データサンプルの一部を訓練サンプルとし、一部をテストサンプルとし、例えば95%を訓練サンプルとして選択し、残りをテストサンプルとして使用することである.訓練データにより機械学習モデルを訓練し,試験データを用いて誤差率を試験した.cross-validate(クロス検証)誤差統計選択法は,異なるK値を比較した場合のクロス検証平均誤差率であり,誤差率が最も小さいK値を選択する.例えばK=1,2,3,…を選択し,K=iごとに100回のクロス検証を行い,平均誤差を算出し,最小のものを比較・選出する.

KNNアルゴリズムの長所と短所
一、簡単、有効.二、再訓練の代価が低い(基本的に訓練を必要としない).三、計算時間と空間は訓練セットの規模(場合によっては大きくない)に線形であり、サンプルが大きすぎると識別時間が長くなる.四、k値は確定しにくい.
mnist手書きデータ認識
mnistは、0-9から32*32の画像サイズの手書き数字を含むライブラリです.詳細はこちらを参照してください.
PILを使って、numpyこの2つのpythonライブラリ、インストールしていないのは私の别の1篇のブログを参照してインストールを配置することができて、これは多くコードが私の修正した大牛の原始コードが生成したことを言って、下の参考文献を参照して、私もすでにCSDNをアップロードして、1部は大牛の原始コードで、1部は新しいです
我々はKNNアルゴリズムを用いてmnist手書き数字を識別する必要があり、具体的な手順は以下の通りである:まず手書き数字を0列にし、原図中の黒画素点を1にし、白を0にし、TXTファイルに書く必要がある.pythonコード:

def img2vector(impath,savepath):
    ''' convert the image to an numpy array Black pixel set to 1,white pixel set to 0 '''
    im = Image.open(impath)
    im = im.transpose(Image.ROTATE_90)
    im = im.transpose(Image.FLIP_TOP_BOTTOM)

    rows = im.size[0]
    cols = im.size[1]
    imBinary = zeros((rows,cols))
    for row in range(0,rows):
        for col in range(0,cols):
            imPixel = im.getpixel((row,col))[0:3]
            if imPixel == (0,0,0):
                imBinary[row,col] = 0
    #save temp txt like 1_5.txt whiich represent the class is 1 and the index is 5
    fp = open(savepath,'w')
    for x in range(0,imBinary.shape[0]):
        for y in range(0,imBinary.shape[1]):
            fp.write(str(int(imBinary[x,y])))
        fp.write('
')
    fp.close()

結果はこうなります.
すべてのTXTファイルの0 1列を行ベクトルpythonコードに変更します.

def vectorOneLine(filename):
    rows = 32
    cols = 32
    imgVector = zeros((1, rows * cols)) 
    fileIn = open(filename)
    for row in xrange(rows):
        lineStr = fileIn.readline()
        for col in xrange(cols):
            imgVector[0, row * 32 + col] = int(lineStr[col])
    return imgVector

KNNはpythonコードを識別する:

def kNNClassify(testImput, TrainingDataSet, TrainingLabels, k):
    numSamples = dataSet.shape[0] # shape[0] stands for the num of row
    #calculate the Euclidean distance
    diff = tile(newInput, (numSamples, 1)) - dataSet # Subtract element-wise
    squaredDiff = diff ** 2 # squared for the subtract
    squaredDist = sum(squaredDiff, axis = 1) # sum is performed by row
    distance = squaredDist ** 0.5
    #sort the distance vector
    sortedDistIndices = argsort(distance)
    #choose k elements
    classCount = {} # define a dictionary (can be append element)
    for i in xrange(k):
        voteLabel = labels[sortedDistIndices[i]]
        #initial the dict
        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
    #vote the label as final return
    maxCount = 0
    for key, value in classCount.items():
        if value > maxCount:
            maxCount = value
            maxIndex = key
    return maxIndex 

*識別結果*参考文献:〔1〕大牛のブログ:http://blog.csdn.net/zouxy09/article/details/16955347［2］matlab実装KNN:http://blog.csdn.net/rk2900/article/details/9080821〔3〕分類アルゴリズムの長所と短所:http://bbs.pinggu.org/thread-2604496-1-1.html［4］コードダウンロードアドレス:http://download.csdn.net/detail/gavin__zhou/9208821 http://download.csdn.net/detail/gavin__zhou/9208827