python実装knnアルゴリズム

機械に触れたばかりで勉強して間もなく、『機械学習実戦』を読んで、今日本のknnアルゴリズムを1回たたいて、書いたのはとても精錬して、pythonに触れたばかりで、まだnumpyに触れたことがないので、読書ノートを書きます.
knnが10大データマイニングアルゴリズムに属するのは比較的簡単です.しかし、彼は分類器カテゴリの学習を監督するアルゴリズムなので、データの練習が必要です.

の利点:精度が高く、異常数値に敏感ではなく、データ入力仮定がない.

欠点:計算の複雑度が高く、空間の複雑度が高い

適用データ範囲:数値型と公称型

knnアルゴリズムとは:
簡単に言えば,K近傍アルゴリズムは異なる特徴値間の距離を測定する方法を用いて分類される.その動作原理は、訓練サンプルセットと呼ばれるサンプルデータのセットが存在し、サンプルセットの各データにラベルが存在することである.すなわち、サンプルセットの各データと属する分類との対応関係を知り、ラベルのない新しいデータを入力した後、新しいデータの各特徴とサンプルセットデータに対応する特徴を比較する.次いで、アルゴリズムは、サンプルセットの特徴が最も類似しているデータの分類ラベルを抽出する.一般に,サンプルデータセットの前のk個の最も類似したデータのみを選択し,これがK近傍アルゴリズム名の由来である.
Pythonを用いてデータをインポートするまずKNNという名前を作成する.pyのpythonモジュール、中のコードは:

#!/usr/bin/python
# -*- coding: utf-8 -*-

#__author__ = 'Mr Cai'


from numpy import  *
import  operator

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

プログラムを実行してrunという名前を作成します.pyのpythonモジュール、KNNを使います.pyモジュールの関数なのでrun.pyではimport KNNでモジュールをインポートします.

K近隣アルゴリズムを実現する一般的な流れ:
(1)既知種別データセットの点と現在点との距離を算出する(2)距離インクリメント順にソートする(3)現在点との距離が最も小さいk個の点を選択する(4)前k個の点が存在する種別の出現頻度を決定する(5)前k個の点の中で最も出現頻度が高い種別を現在点の予測分類として返す

**コード実装run.py**

#!/usr/bin/python
# -*- coding: utf-8 -*-

#__author__ = 'Mr Cai'
from numpy import *
import operator
import KNN

#    
group, labels = KNN.creatrDataSet()

def classify(inX, dataSet, labels, k):

    #       。          
    dataSetSize = dataSet.shape[0]

    #tile:numpy    。tile        ，    4      。diffMat               。    
    diffMat = tile(inX, (dataSetSize,1)) - dataSet    #tile(x,(y,z))    x  z ，  y 

    #           
    sqDiffMat = diffMat**2

    #     ，            
    sqDistances = sqDiffMat.sum(axis=1)   #axis = 0,      axis = 1,   

    #  ，    。
    distances = sqDistances**0.5

    #    
    sortedDistances = distances.argsort()  #           

    #       k  。
    classCount = {}
    for i in range(k):
        numOflabel = labels[sortedDistances[i]]
        classCount[numOflabel] = classCount.get(numOflabel,0) + 1 #  

    #  
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1),reverse=True)

    return sortedClassCount[0][0]

if __name__ == '__main__':
    print classify([0,0],group,labels,3)

コードの知識点のまとめ:

辞書のget()関数辞書のget()関数は、2つのパラメータを受信する.最初のパラメータはクエリーするkeyであり、2番目は辞書にkeyが存在しない場合に返される値です.例:d={‘key’:’value’}print d.get(‘key’,‘not found’)は、

の機能を完了する

if d.has_key('key'):    
  print d['key']   
else:   
  print 'not found'   

辞書のitem()とitemgetter()の違い
python辞書のitemsメソッドの役割:辞書内のすべての項目をリストで返すことができます.辞書項目の概念を理解していない場合は、Pythonマッピングタイプの辞書の基礎知識を参照してください.辞書は無秩序であるため,items法で辞書のすべての項目を返すのも順序がない.
python辞書のiteritemsメソッドの役割:itemsメソッドと比較してほぼ同じですが、その戻り値はリストではなく反復器です.

 ：
>>>x = {'title':'python web site','url':'www.iplaypython.com'}
>>>x.items()
>>>[('url', 'www.iplaypython.com'), ('title', 'python web site')]

 ：
>>> f = x.iteritems()
>>> f
0xb74d5e3c>
>>> type(f)
'dictionary-itemiterator'>    #       
>>> list(f)
[('url', 'www.iplaypython.com'), ('title', 'python web site')]

pythonのsorted()関数詳細sorted関数:Pythonに組み込まれているソート関数sortedはlistまたはiteratorをソートできます.公式サイトのドキュメントを参照してください.http://docs.python.org/2/library/functions.html?highlight=sorted#sortedこの関数の原型はsorted(iterable[,cmp[,key[,reverse]]]))パラメータ解釈:(1)iterableはソートするlistまたはiterableを指定し、言うまでもなく;(2)cmpは関数であり、ソート時に比較する関数を指定し、studentsがクラスオブジェクトのlistであるなどの関数またはlambda関数を指定することができる.コードは、students=[(‘john’,‘A’,15),(‘jane’,‘B’,12),(‘dave’,‘B’,10)]sorted(students,key=lambda student:student[2])(3)keyを関数とし、ソートする要素のどれをソートするかを指定し、関数は上記の例で説明します.コードは、sorted(students,key=lambda student:student[2])keyが指定するlambda関数機能は、要素studentを除去する3番目のドメイン(すなわちstudent[2])であるため、sortedソート時にstudentsのすべての要素の3番目のドメインでソートされます.上のoperatorがあります.itemgetter関数は、この関数で実現することもでき、例えばstudentの3番目のドメインソートによって、sorted(students,key=operator.itemgetter(2))sorted関数もマルチレベルソートすることができ、例えば2番目のドメインと3番目のドメインに基づいてソートすることができ、sorted(students,key=operator.itemgetter(1,2))は、2番目のドメインに基づいてソートし、3番目のドメインに基づいてソートします.(4)reverseパラメータは言うまでもなく、bool変数であり、昇順か降順かを表し、デフォルトはfalse(昇順配列)であり、Trueと定義されると降順で配列される.

operator.itemgetter(1)の解釈はsorted()関数のkey値が1つの関数を受信する必要があるため、辞書の2番目のパラメータに従ってソートすることを意味する.operator.itemgetter関数operatorモジュールが提供するitemgetter関数は、オブジェクトのどの次元のデータを取得するために使用され、パラメータはいくつかのシーケンス番号(すなわち、取得する必要があるデータのオブジェクト内のシーケンス番号)であり、以下に例を示す.

a = [1,2,3] 
>>> b=operator.itemgetter(1)      //    b，      1    
>>> b(a) 
2 

>>> b=operator.itemgetter(1,0)  //    b，      1    0   
>>> b(a) 
(2, 1)

気をつけてitemgetter関数は値ではなく、オブジェクトに作用して値を取得する関数を定義します.