分類方法:KNNアルゴリズムの全面的な解析
7400 ワード
分類方法:KNNアルゴリズムの全面的な解析
テキストリンク:http://kakazai.cn/index.php/Kaka/Jqxx/query/id/8
文書ディレクトリ一、孟母三遷とKNN 二、別名 三、歴史 四、アルゴリズム (1)核心思想 (2)アルゴリズム記述 (3)時間複雑度分析 (4)アルゴリズムの長所と短所分析 五、アルゴリズムの変種 (1)隣接する重み を増加する.(2)k個の隣接 を一定半径範囲の点で置換.六、sklearnにおけるKNNの実現 コア関数KNeighborsClassifier() 最も隣接する隣人を探し出す:kneighbors() 7、コードケース 単純アプリケーション 8、応用分野 (1)分類問題 (2)回帰問題 参照 一、孟母三遷とKNN
「昔孟母、隣を選ぶ」——『三字経』
孟母三遷は子供にもっと良い成長環境を与えるためで、彼女は居住地の環境が子供の成長に深く影響していることを知っているからだ.また,KNNアルゴリズムは,1つのサンプルポイントのカテゴリが最も近いサンプルポイントから複数のカテゴリによって投票されて決定されると考えている.
KNNアルゴリズムを用いて孟母が移転したかどうかを記述することができる.ある居住地で10人の子供が孟母の息子と遊んでいて、最も親しいと仮定します.そのうち8人がいたずらっ子で、2人だけが礼儀をわきまえていると、孟母の息子はいたずらっ子の影響を受けやすく、いたずらっ子にもなりやすいので、引っ越します.逆に、2人だけがいたずらで、残りの8人が礼儀正しいなら、孟母の息子ももっと礼儀正しく、残ってもいいかもしれません.
朱に近づく者は赤く、墨に近づく者は黒く、一人で最も環境に親しむ最も主要な力がこの人を形作った.これもKNNが私たちに伝えたいことです.
二、別名
K近隣アルゴリズム
k-nearest neighbor classification
三、歴史
KNNは1968年にCoverとHartによって最初の近接アルゴリズムを提案した.
四、アルゴリズム
(1)核心思想
すべてのサンプルポイントにカテゴリがマークされているデータセットが与えられます.新しいサンプルポイントが来て、そのカテゴリを予測するために、それに最も近いkポイントを見つけて、このkポイントのカテゴリを統計して、カテゴリaがサンプルポイントの数が最も多い場合、新しいサンプルポイントを予測するカテゴリはaです.
KNNは、データセットにラベルがあるため、監視アルゴリズムに属している.未知のサンプルポイントのカテゴリを予測できる分類(classification)方法でもある.訓練セットを事前に処理せず、未知のサンプルポイントを予測するときにのみ分類されるため、怠惰学習(lazy learning)にも属します.
(2)アルゴリズム記述
1)kの選択
kが小さすぎると、騒音点に影響されます.kが大きすぎると、隣人に他のカテゴリのサンプルポイントがたくさん含まれます.適切なkの選択はアルゴリズムの性能に大きな影響を及ぼす.
2)距離
距離のメトリックは、サンプルポイントの類似性を測定することができます.テキスト分類では,余弦距離はユークリッド距離よりも試料の類似性を測定できる.次元が高い場合、ユークリッド距離の計算が問題になります.
(3)時間複雑度分析
データセットのサンプルポイント個数はnであり,各サンプルポイントの次元はdであり,距離メトリックはユークリッド距離を用いると仮定する.他の距離メトリック方式を採用することもできます.
ステップ1:Aとn個のサンプル点の距離を計算するには、その複雑さはO(nd)である.
ステップ2:計算された距離をソートするには、少なくともO(nlogn)の複雑さです.
第3ステップ:k個の隣接するカテゴリを統計し、最大のカテゴリを探し出し、その複雑度は少なくともO(k)である.
全時間複雑度はO(nd)+O(nlogn)+O(k)であった.kはnに比べて非常に小さい可能性があり、無視できる.
したがって,1つのサンプル点のカテゴリを判断する時間的複雑さはO(nlogn)である.
以上の分析では、brute-force法を暴力的に検索してk人の隣人を見つけると仮定した.小型データセットではbrute−forceは競争力があるが,サンプル数が増加するにつれてbrute−forceは不可能になった.
brute‐force法の計算効率の低下を解決するために,BallTree,KDDTreeのような種々のツリーベースのデータ構造が発明された.これらの構造は、要約サンプル距離情報を効率的に符号化することによって、所望の距離計算量を低減する.その基本思想は,AがBから離れ,CがBに近づくと,AがCから離れ,明確な計算を必要としないことである.
(1)Brute force時間複雑度O(nd)
(2)BallTree時間複雑度O(dlogn)
(3)d<20の場合、KDTreeの時間的複雑度はO(dlogn)である.d>=20の場合,時間的複雑度はO(dn)である.
サンプル数が30未満の場合,Brute forceはBallTreeとKDDTreeよりも効率的であった.
(4)アルゴリズムの長所と短所の分析
利点:(1)異常値と騒音に対する許容度が高い.あるサンプルポイントのカテゴリはk個の隣接者によって共通に決定されるため、そのうちの1つがノイズまたは異常値であっても、そのサンプルポイントのカテゴリに影響を及ぼさない可能性がある.
欠点:(1)計算量が多く、メモリの需要が大きい.各サンプルポイントを予測するためには,他のすべてのサンプルポイントとの距離を算出する必要がある.
五、アルゴリズムの変種
KNNにはいくつかの変種があり、主にKの隣人に集中している.
(1)隣人の重みを増やす
デフォルトでは、k個の隣接者は同じ重みであり、同じように重要である.しかし、距離が近い隣人ほど顕著な影響が大きい場合があるため、隣人に距離の重みを与えることができ、距離が近いほど影響が大きくなり、重みが大きくなる.実際の状況に応じて、それぞれの隣人の重みを自分で指定することもできます.
(2)k個の隣接点を一定半径範囲の点で置換する
あるサンプル点Aへの影響は、必ずしも最近のk個の隣人ではなく、周囲xxの隣人がAに影響を及ぼす場合がある.したがって、Aを中心として、半径rが設定され、その半径範囲内の全ての点がAの隣同士となる.
サンプル点の分布が不均一な場合もある.あるサンプルポイントの周りは密集しており、k人の隣人が近い.サンプルポイントの周りはまばらで、隣人たちは遠く離れています.距離が近いから影響があると仮定すると、サンプルポイントがk個の隣接によって影響されるのではなく、サンプルポイントが一定範囲の隣接によって影響されるべきである.
このアルゴリズムはscikit−learnにおけるRadiusNeighborsClassifierにおいて実装されている.
六、sklearnにおけるKNNの実現
コア関数KNeighborsClassifier()
sklearnではKNNアルゴリズムが実装されており,そのモデル関数はKNeighborsClassifier()である.
パラメータの説明
最も近い隣人を見つける:kneighbors()
戻り値の説明
パラメータの説明
七、コードケース
単純な応用
八、応用分野
(1)分類問題
例えば、20万枚の猫の絵と20万枚の犬の絵を、コンピューターに入力して勉強させ、1枚1枚を繰り返さないようにします.訓練に成功すると、勝手に画像を選んで認識させることができ、40万枚の写真を保存し、保存した形状に最も近いものを判断することができます.
(2)回帰問題
KNNアルゴリズムは回帰も可能である.予測対象サンプル点のいくつかの近隣を探し出し、これらの近隣の平均値を求め、この平均値を予測対象サンプル点に付与することで、この予測対象サンプル点の属性値を知ることができる.
リファレンス
https://www.cnblogs.com/xiaotan-code/p/6680438.html scikit-learnパケットに基づいて機械学習を実現するKNN(K近隣)-完全な例
https://blog.csdn.net/loveliuzz/article/details/77943054 機械学習——最近接規則分類(K Nearest Neighbor)KNNアルゴリズム
https://blog.csdn.net/lovego123/article/details/67638789 最近隣接検索(Nearest Neighbor Search)の簡単な概要
https://blog.csdn.net/qq_36330643/article/details/77532161 KNN(k-nearest neighborの略)最近隣接アルゴリズムの原理の詳細
https://blog.csdn.net/skyline0623/article/details/8154911 【機械学習】K-meansクラスタリングアルゴリズムの初探査
https://www.jianshu.com/p/778d39132d66 scikit-learn–Nearest Neighbors(近隣)
KNNアルゴリズム総説洞小凡(吉林ハイテク区万信養成学校、吉林省吉林市132000)
https://blog.csdn.net/u010986080/article/details/78670378
テキストリンク:http://kakazai.cn/index.php/Kaka/Jqxx/query/id/8
文書ディレクトリ
「昔孟母、隣を選ぶ」——『三字経』
孟母三遷は子供にもっと良い成長環境を与えるためで、彼女は居住地の環境が子供の成長に深く影響していることを知っているからだ.また,KNNアルゴリズムは,1つのサンプルポイントのカテゴリが最も近いサンプルポイントから複数のカテゴリによって投票されて決定されると考えている.
KNNアルゴリズムを用いて孟母が移転したかどうかを記述することができる.ある居住地で10人の子供が孟母の息子と遊んでいて、最も親しいと仮定します.そのうち8人がいたずらっ子で、2人だけが礼儀をわきまえていると、孟母の息子はいたずらっ子の影響を受けやすく、いたずらっ子にもなりやすいので、引っ越します.逆に、2人だけがいたずらで、残りの8人が礼儀正しいなら、孟母の息子ももっと礼儀正しく、残ってもいいかもしれません.
朱に近づく者は赤く、墨に近づく者は黒く、一人で最も環境に親しむ最も主要な力がこの人を形作った.これもKNNが私たちに伝えたいことです.
二、別名
K近隣アルゴリズム
k-nearest neighbor classification
三、歴史
KNNは1968年にCoverとHartによって最初の近接アルゴリズムを提案した.
四、アルゴリズム
(1)核心思想
すべてのサンプルポイントにカテゴリがマークされているデータセットが与えられます.新しいサンプルポイントが来て、そのカテゴリを予測するために、それに最も近いkポイントを見つけて、このkポイントのカテゴリを統計して、カテゴリaがサンプルポイントの数が最も多い場合、新しいサンプルポイントを予測するカテゴリはaです.
KNNは、データセットにラベルがあるため、監視アルゴリズムに属している.未知のサンプルポイントのカテゴリを予測できる分類(classification)方法でもある.訓練セットを事前に処理せず、未知のサンプルポイントを予測するときにのみ分類されるため、怠惰学習(lazy learning)にも属します.
(2)アルゴリズム記述
S1
A，
S2
S1 ， k A
S3
k ， A
1)kの選択
kが小さすぎると、騒音点に影響されます.kが大きすぎると、隣人に他のカテゴリのサンプルポイントがたくさん含まれます.適切なkの選択はアルゴリズムの性能に大きな影響を及ぼす.
2)距離
距離のメトリックは、サンプルポイントの類似性を測定することができます.テキスト分類では,余弦距離はユークリッド距離よりも試料の類似性を測定できる.次元が高い場合、ユークリッド距離の計算が問題になります.
(3)時間複雑度分析
データセットのサンプルポイント個数はnであり,各サンプルポイントの次元はdであり,距離メトリックはユークリッド距離を用いると仮定する.他の距離メトリック方式を採用することもできます.
ステップ1:Aとn個のサンプル点の距離を計算するには、その複雑さはO(nd)である.
ステップ2:計算された距離をソートするには、少なくともO(nlogn)の複雑さです.
第3ステップ:k個の隣接するカテゴリを統計し、最大のカテゴリを探し出し、その複雑度は少なくともO(k)である.
全時間複雑度はO(nd)+O(nlogn)+O(k)であった.kはnに比べて非常に小さい可能性があり、無視できる.
したがって,1つのサンプル点のカテゴリを判断する時間的複雑さはO(nlogn)である.
以上の分析では、brute-force法を暴力的に検索してk人の隣人を見つけると仮定した.小型データセットではbrute−forceは競争力があるが,サンプル数が増加するにつれてbrute−forceは不可能になった.
brute‐force法の計算効率の低下を解決するために,BallTree,KDDTreeのような種々のツリーベースのデータ構造が発明された.これらの構造は、要約サンプル距離情報を効率的に符号化することによって、所望の距離計算量を低減する.その基本思想は,AがBから離れ,CがBに近づくと,AがCから離れ,明確な計算を必要としないことである.
(1)Brute force時間複雑度O(nd)
(2)BallTree時間複雑度O(dlogn)
(3)d<20の場合、KDTreeの時間的複雑度はO(dlogn)である.d>=20の場合,時間的複雑度はO(dn)である.
サンプル数が30未満の場合,Brute forceはBallTreeとKDDTreeよりも効率的であった.
(4)アルゴリズムの長所と短所の分析
利点:(1)異常値と騒音に対する許容度が高い.あるサンプルポイントのカテゴリはk個の隣接者によって共通に決定されるため、そのうちの1つがノイズまたは異常値であっても、そのサンプルポイントのカテゴリに影響を及ぼさない可能性がある.
欠点:(1)計算量が多く、メモリの需要が大きい.各サンプルポイントを予測するためには,他のすべてのサンプルポイントとの距離を算出する必要がある.
五、アルゴリズムの変種
KNNにはいくつかの変種があり、主にKの隣人に集中している.
(1)隣人の重みを増やす
デフォルトでは、k個の隣接者は同じ重みであり、同じように重要である.しかし、距離が近い隣人ほど顕著な影響が大きい場合があるため、隣人に距離の重みを与えることができ、距離が近いほど影響が大きくなり、重みが大きくなる.実際の状況に応じて、それぞれの隣人の重みを自分で指定することもできます.
(2)k個の隣接点を一定半径範囲の点で置換する
あるサンプル点Aへの影響は、必ずしも最近のk個の隣人ではなく、周囲xxの隣人がAに影響を及ぼす場合がある.したがって、Aを中心として、半径rが設定され、その半径範囲内の全ての点がAの隣同士となる.
サンプル点の分布が不均一な場合もある.あるサンプルポイントの周りは密集しており、k人の隣人が近い.サンプルポイントの周りはまばらで、隣人たちは遠く離れています.距離が近いから影響があると仮定すると、サンプルポイントがk個の隣接によって影響されるのではなく、サンプルポイントが一定範囲の隣接によって影響されるべきである.
このアルゴリズムはscikit−learnにおけるRadiusNeighborsClassifierにおいて実装されている.
六、sklearnにおけるKNNの実現
コア関数KNeighborsClassifier()
sklearnではKNNアルゴリズムが実装されており,そのモデル関数はKNeighborsClassifier()である.
#
sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, weights=’uniform’, algorithm=’auto’, leaf_size=30,p=2, metric=’minkowski’, metric_params=None, n_jobs=1, **kwargs)
パラメータの説明
（1）n_neighbors int ；knn 。
（2）weights str ； ，'uniform'
，'distance' ，[callable] ，
， 。
（3）algorithm='auto' str ； ，['auto', 'ball_tree', 'kd_tree', 'brute']。
'brute': ； 'auto': 。 kd_tree
， ball_tree 。 20 kd_tree ， ball_tree 。
（4）leaf_size int ； ， kd_tree ball_tree ，
， 。
（5）matric str ； 。 minkowski。
（6）p int ； ， 2， 。p=1
（7）metric_params ， ， None。
（8）n_jobs int ； ， 1 ， -1 CPU ， 。
最も近い隣人を見つける:kneighbors()
# A
kneighbors(X=None，n_neighbors=None，return_distance=True)
戻り値の説明
パラメータの説明
X A
n_neighbors A
return_distance ，True= ，False=
七、コードケース
単純な応用
#
from sklearn.datasets.samples_generator import make_blobs
import numpy as np
c = np.array([[-2,2],[2,2],[0,4]]) # 3 ， array
# 60 ， 2 ， 3 ， 0.6;
x, y = make_blobs(n_samples=60, n_features=2,centers = c, random_state=0, cluster_std=0.60)
#
import matplotlib.pyplot as plt
plt.scatter(x[:,0],x[:,1],c=y) #x 0 ，x 1 ， ，
plt.scatter(c[:,0],c[:,1],marker='^',c='red') # ， ，
plt.show() #
#
from sklearn.neighbors import KNeighborsClassifier
k=5
model = KNeighborsClassifier(n_neighbors=k) # 5
model.fit(x,y) # (x,y)
#
x_sample = np.array([[0,2]]) # [[0,2]]， array
y_sample = model.predict(x_sample) #
neighbors = model.kneighbors(x_sample, return_distance=False) # x_sample k ， x_sample
# k
plt.scatter(x[:,0],x[:,1],c=y,s=100) # ， 100
plt.scatter(c[:,0],c[:,1],marker='^',c='red',s=100) #
plt.scatter(x_sample[:,0],x_sample[:,1],marker='x',c=y_sample) #
# k
for i in neighbors[0]:
plt.plot([x[i][0],x_sample[0][0]],[x[i][1],x_sample[0][1]],'k--',linewidth=0.6)
plt.show()
八、応用分野
(1)分類問題
例えば、20万枚の猫の絵と20万枚の犬の絵を、コンピューターに入力して勉強させ、1枚1枚を繰り返さないようにします.訓練に成功すると、勝手に画像を選んで認識させることができ、40万枚の写真を保存し、保存した形状に最も近いものを判断することができます.
(2)回帰問題
KNNアルゴリズムは回帰も可能である.予測対象サンプル点のいくつかの近隣を探し出し、これらの近隣の平均値を求め、この平均値を予測対象サンプル点に付与することで、この予測対象サンプル点の属性値を知ることができる.
リファレンス
https://www.cnblogs.com/xiaotan-code/p/6680438.html scikit-learnパケットに基づいて機械学習を実現するKNN(K近隣)-完全な例
https://blog.csdn.net/loveliuzz/article/details/77943054 機械学習——最近接規則分類(K Nearest Neighbor)KNNアルゴリズム
https://blog.csdn.net/lovego123/article/details/67638789 最近隣接検索(Nearest Neighbor Search)の簡単な概要
https://blog.csdn.net/qq_36330643/article/details/77532161 KNN(k-nearest neighborの略)最近隣接アルゴリズムの原理の詳細
https://blog.csdn.net/skyline0623/article/details/8154911 【機械学習】K-meansクラスタリングアルゴリズムの初探査
https://www.jianshu.com/p/778d39132d66 scikit-learn–Nearest Neighbors(近隣)
KNNアルゴリズム総説洞小凡(吉林ハイテク区万信養成学校、吉林省吉林市132000)
https://blog.csdn.net/u010986080/article/details/78670378