2017年2月10日 星期五

演算法(2)--使用Numpy.bincount來實作簡單的桶子排序法



        會注意到Numpy.bincount()這個函數,其實是在閱讀機器學習的程式碼裡常常出現。常用來
處理類別標籤的向量。它是內建在Python Numpy裡。原文的解釋其實有點難懂,故我把我的心得
記下來,發現它原始設計的概念就是類似桶子排序法的基本概念,是一個很有趣的函數,所以也
特別用它實作一簡單的桶子排序。

理解Numpy.bincount()
numpy.bincount(x, weights=None, minlength=None)

 1.假設輸入X=[0,1,2,2,3,4,4],那麼產生bins(桶子)的數量為該X最大值4
 再加1=5,於是我們產生了5個bins(桶子)的排序編號為indx0~indx4,
 可以視為一向量[indx0,indx1,indx2,indx3,indx4]

 2.接著來看如何放原本的資料到這5的桶子(bins,分別indx0~indx4)
 原本的輸入X=[0,1,2,2,3,4,4]裡有"一個"資料0,表示要放到indx0桶子的只有一個
 故indx0=1。
 接著,原本的輸入X=[0,1,2,2,3,4,4]裡有"一個"資料,表示要放到indx1桶子的只有
 一個,故indx1=1。
 接著,原本的輸入X=[0,1,2,2,3,4,4]裡有"兩個"資料,表示要放到indx2桶子的有
 兩個,故indx1=2。
    依序放完所以桶子,indx3及 indx4桶子,可以得到indx3=1,indx4=2
    故得到輸出結果為[1,1,2,1,2]即:[indx0=1,indx1=1,indx2=2,indx3=1,indx4=2]
 使用Python語言程式如下:
   EX1:
 import numpy as np
 X=[0,1,2,2,3,4,4]
 print(np.bincount(X))
   結果是:[1,1,2,1,2]

  EX2:
   import numpy as np
 X=[0,5,3,2,3,1,4,2,4]
 print(np.bincount(X))
 結果是:[1,1,2,2,2,1]

  注意:輸入的X數值不可以為負,否則報錯
 若有實數值,實際測試會被無條件捨去後當整數使用





minlength參數的使用

1.如上假設輸入X=[0,1,2,2,3,4,4],那麼產生bins(桶子)的數量原本為該最大值4
 再加1=5,但是如果有設定minlength並且大於5,如假定minlength=7,那麼bins(桶
子)的數量會變成7。新的(桶子)向量則為[indx0,indx1,indx2,indx3,indx4,indx5,indx6]

2.那麼再來計算原本數據X=[0,1,2,2,3,4,4],得到新的桶子(bins)向量應為:
[1 1 2 1 2 0 0],多出來的indx5,indx6 桶子在原本的數據X 尚未有放入資料,故為0。
使用Python語言程式如下:
EX1:
X=[0,1,2,2,3,4,4]
print(np.bincount(X,minlength=7))
結果是:[1 1 2 1 2 0 0]



weights參數的使用

 1.如上假設輸入X=[0,1,2,2,3,4,4],那麼產生bins(桶子)的數量原本為該最大值4
 再加1=5。5個bins(桶子)的排序編號為indx0~indx4,
 可以視為一向量[indx0,indx1,indx2,indx3,indx4]

 2.如果要給定weights參數,必需指定一向量如W,此W的長度必須等於輸入的X。
   例如輸入X=[0,1,2,2,3,4,4],長度為7個元素,那麼給定的W也必須是長度為7個元素的向
   量,如W=[0.1,0.2,0.5,0.1,0.8,0.3,0.4]。

 3.再來看將W放進bins(桶子)向量[indx0,indx1,indx2,indx3,indx4]的方法。
   首先來看桶子indx0 ,在X的資料裡為0(表示要放進indx0桶子)的有X[0],對應到的W[0]
   的資料為0.1,所以這時桶子indx0應放入0.1,而不是計算X資料裡0的個數。

    接著來看桶子indx1 ,在X的資料裡為1(表示要放進indx1桶子)的有X[1],對應到的W[1]
   的資料為0.2,所以這時桶子indx1應放入0.2,而不是計算X資料裡1的個數。

    接著看桶子indx2,在X的資料裡為2(表示要放進indx2桶子)的有兩個,X[2]及X[3], 對應到
   W資料為W[2]=0.5及W[3]=0.1,所以這時桶子indx2應放入W[2]+W[3]=0.5+0.1=0.6

   接著看桶子indx3,在X的資料裡為3(表示要放進indx3桶子)的有X[4], 對應到
   W資料為W[4]=0.3,所以這時桶子indx3應放入0.8

   最後看桶子indx4,在X的資料裡為4(表示要放進indx4桶子)的有兩個,X[5]及X[6], 對應到
  W資料為W[5]=0.3及W[6]=0.4,所以這時桶子indx4應放入W[5]+W[6]=0.3+0.4=0.7
  故可得到bins(桶子)向量為[0.1,0.2,0.6,0.8,0.7]

 使用Python語言程式如下:
EX1:
X=[0,1,2,2,3,4,4]
W=[0.1,0.2,0.5,0.1,0.8,0.3,0.4]
print(np.bincount(X,weights=W))
結果是:[0.1,0.2,0.6,0.8,0.7]

 EX2:
X=[1,1,2,2,3,4,5]
W=[0.1,0.2,0.5,0.1,0.8,0.3,0.4]
print(np.bincount(X,weights=W))

結果是:[0.0,0.3,0.6,0.8,0.3,0.4]

接著我們利用Numpy.bincount()來實作簡單的桶子排序法。
例如這次段考數學成績,A生96分,B生78分,C生55分,D生37分,E生88分,F生100分,
G生67分,H生92分,I生32分,J生76分,k生27分,J生92分。
先不考慮對應的學生名稱只將分數高至低排序,排序,
我們可以先手動建立一未排序的數列向量X=[96,78,55,37,88,100,67,92,32,76,27,92]
接著使用Xf=np.bincount(X)會產生101個桶子,因為X資料內最大值為100,故產生了0~100編號的桶子,其意義為分別對應到分數0~100分,並記錄該分數有幾人獲得。
例如100分有1人,則產生的桶子Xf[100]=1,例如92分有2人,那麼產生的桶子Xf[92]=2。
接著我們只要利用迴圈找出各個桶子Xf[i] 不等於0 ,即表示有得分者,再將其桶子index值(i)依序印出即可。記住,在這裡,桶子index值即代表分數。






<簡單的桶子排序範例程式>

import numpy as np

X=[96,78,55,37,88,100,67,92,32,76,27,92]
print("列印原始資料:",X)
Xf=np.bincount(X)
Xf2=Xf.copy()
print("產生的桶子數量=",len(Xf))
print("把分數放進對應0~100的桶子,並計算數量",Xf)

print("由大到小排序")
for i in range(len(Xf)-1,0,-1):
 while Xf[i]!=0:
  print(i)
  Xf[i]-=1
  
print("由小到大排序")
for j in range(len(Xf2)):
 while Xf2[j]!=0:
  print(j)
  Xf2[j]-=1




歡迎加入FB,AI人工智慧與機器人社團一起討論,
https://www.facebook.com/groups/1852135541678378/2068782386680358/?notif_t=like&notif_id=1477094593187641

加入阿布拉機的3D列印與機器人的FB專頁
https://www.facebook.com/arbu00/


<其他有關OPENCV 文章>

機器學習(2)--使用OPENCV SVM實作手寫辨識
機器學習(1)--使用OPENCV KNN實作手寫辨識
OPENCV(11)--contours and convex hull(輪廓與凸包)
OPENCV(10)--Canny Edge Detection(Canny邊緣檢測)
OPENCV(9)--Image Gradients(圖像梯度)
OPENCV(8)--Histogram & Histograms Equalization(長條圖與長條圖均衡化)
OPENCV(7)--2D Convolution ,Image Filtering and Blurring (旋積,濾波與模糊)
OPENCV(6)--Trackbar(軌道桿)
OPENCV(5)--Drawing
OPENCV(4)--Grayscale,Binarization,Threshole(灰階化,二值化,閥值)
OPENCV(3)--Matplotlib pyplot bassic function
OPENCV(2)--Capture Video from Camera
OPENCV(1 )--How to install OPENCV in Python

<其他文章>
人工神經網路(2)--使用Python實作後向傳遞神經網路演算法(Backprogation artificial neature network)
人工神經網路(1)--使用Python實作perceptron(感知器)
深度學習(1)-如何在windows安裝Theano +Keras +Tensorflow並使用GPU加速訓練神經網路
演算法(1)--蒙地卡羅法求圓周率及橢圓面積(Monte carlo)