# read in data and mapping
import pandas as pd
import numpy as np

file = pd.read_csv('fashion-mnist_train.csv', header = None)
X_train = file.iloc[1:, 1:785].astype(np.int)
y_train = file.iloc[1:, 0].astype(np.int)

file = pd.read_csv('fashion-mnist_test.csv', header = None)
X_test = file.iloc[1:, 1:785].astype(np.int)
y_test = file.iloc[1:, 0].astype(np.int)

read in data

• 分別讀進training、testing set
  • X取第1到第784行的資料(784個feature)
  • y取第0行(class label)
• 最後將讀進來的資料由string轉成int。
• 網站已經事先將處理過dataset:
  • 分為'well-defined train and test dataset'，所以直接取用。
  • class label也已經從0編到9，不用另外做label encoding。

from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import validation_curve

param_range = [10, 20, 30, 50, 80, 100]
train_scores, test_scores = validation_curve(estimator=RandomForestClassifier(criterion='gini', random_state=1, n_jobs=3),
                                             X=X_train,
                                             y=y_train,
                                             param_range=param_range,
                                             param_name='n_estimators',
                                             cv=5)
train_mean = np.mean(train_scores, axis=1)
test_mean = np.mean(test_scores, axis=1)
plt.plot(param_range, train_mean, color='blue', marker='o', markersize=5, label='training accuracy')
plt.plot(param_range, test_mean, color='green', linestyle='--', marker='s', markersize=5, label='validation accuracy')
plt.legend(loc='lower right')
plt.grid()
plt.ylim([0.7, 1.025])
plt.tight_layout()
plt.show()

Validation Curve of Random Forest

• 直接使用原始資料
• 圖中50棵樹之後的點，training和validation score的差距大概相同

import time

forest_orig_data = RandomForestClassifier(criterion='gini', n_estimators=50, random_state=1, n_jobs=3)
start = time.time()
forest_orig_data.fit(X_train, y_train)
score_fod = forest_orig_data.score(X_test, y_test)
stop = time.time()
print('Test Accuracy: %.4f.\n\nProcessing Time: %.2fs.' % (score_fod, (stop-start)))

Test Accuracy: 0.8788.

Processing Time: 23.26s.

# standardization
from sklearn.preprocessing import StandardScaler

sc=StandardScaler()
sc.fit(X_train)
X_train_std=sc.transform(X_train)
X_test_std=sc.transform(X_test)

data preprocessing: standardization

將X_train標準化，並同時transform X_test

# data compression: LDA
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis as LDA

lda = LDA(n_components=8)
X_train_lda = lda.fit_transform(X_train_std, y_train)
X_test_lda = lda.transform(X_test_std)

data compression: LDA

• lda & pca的選擇
  • lda是supervised的方法，比pca能夠維持accuracy。
  • lda直接限制最終的feature數量必須$\leq$class的數量減一(10-1=9)，可以有效減少feature的數量、降低之後的運算量。
• n_components
  • 選擇n_components=8是因為想讓運算跑得再快一點，而accuracy差不多。

from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import GridSearchCV
from sklearn.model_selection import cross_val_score

param_C = [0.01, 0.1, 1.0, 10.0, 100.0]
lr_solver = ['newton-cg', 'sag', 'saga', 'lbfgs']
param_grid = {'C': param_C,
              'solver': lr_solver}

gs = GridSearchCV(estimator=LogisticRegression(penalty='l2', multi_class='auto', max_iter=200, random_state=1),
                  param_grid=param_grid,
                  scoring='accuracy',
                  cv=10,
                  n_jobs=-1)
gs = gs.fit(X_train_lda, y_train)
print('Best validation score: %.4f' % gs.best_score_, '\nBest parameter combination:', gs.best_params_)
lr = gs.best_estimator_
lr.fit(X_train_lda, y_train)
print('Test accuracy:', lr.score(X_test_lda, y_test))

Best validation score: 0.8287 
Best parameter combination: {'C': 1.0, 'solver': 'newton-cg'}
Test accuracy: 0.8247

Logistic Regression

• penalty選擇l2、max_iter設定200，以避免沒有收斂的情況
• Grid Search調整參數，得到最佳的參數組合是C=1.0，solver=newton-cg。
  • param_grid中，C給的範圍以10為級距主要想法是看C要大還是小，而不是太細的去挑確切哪個數值最好
  • solver選擇比較適合處理multiclass的方法。
• 最後選擇C比較小($\lambda$比較大)，所以會造成比較強的regularization，比較不會underfit。
• validation的結果(0.8287)跟testing的結果(0.8247)準確度差不多，表示沒有overfit/underfit。

import time

start = time.time()
lr.fit(X_train_lda, y_train)
lr.score(X_test_lda, y_test)
stop = time.time()
print('Process Time: %.2fs.' % (stop-start))

Process Time: 7.04s.

Time Complexity of Logistic Regression:

• predictions for many samples: O((f+1)cs)
  1. 每個feature分別乘上weight、加上bias、最後加總$\Rightarrow$f+1
  2. 每個class都要判斷一遍，所以乘上class數量c$\Rightarrow$O((f+1)*c) (predictions for one sample)
  3. 每一筆資料都要計算前面兩個步驟，所以再乘上sample數s$\Rightarrow$O((f+1)*c*s)
• 實際執行時間: 7.04秒
  • 在這次用到的所有algorithm中算速度較快的，表示其Time Complexity較低

%matplotlib inline
import matplotlib.pyplot as plt
from sklearn.model_selection import learning_curve


train_sizes, train_scores, test_scores = learning_curve(estimator=lr,
                                                        X=X_train_lda,
                                                        y=y_train,
                                                        train_sizes=np.linspace(0.1,1.0,10),
                                                        cv=5,
                                                        n_jobs=1)
train_mean = np.mean(train_scores, axis=1)
test_mean = np.mean(test_scores, axis=1)
plt.plot(train_sizes, train_mean, color='blue', marker='o', markersize=5, label='training accuracy')
plt.plot(train_sizes, test_mean, color='green', linestyle='--', marker='s', markersize=5, label='validation accuracy')
plt.legend(loc='lower right')
plt.tight_layout()
plt.show()

Learning Curve: Logistic Regression

• 用learning觀察可以看到traing和validation accuracy隨著sample增加，慢慢趨近於一個很接近的數值，形成一個好的bias-variance trade-off

from sklearn.svm import SVC

param_gamma = [0.1, 1.0, 10.0, 'scale']    # scale uses 1 / (n_features * X.var()) as value of gamma
param_C = [0.1, 1.0, 10.0]

param_grid_svc = [{'gamma': param_gamma,
                   'C': param_C,
                   'kernel': ['rbf']}]

gs_svc = GridSearchCV(estimator=SVC(random_state=1),
                      param_grid=param_grid_svc,
                      scoring='accuracy',
                      cv=5,
                      n_jobs=-1)

gs_svc = gs_svc.fit(X_train_lda, y_train)
print('Best validation score: %.4f' % gs_svc.best_score_)
print('Best parameter combination:', gs_svc.best_params_,)

Best validation score: 0.8418
Best parameter combination: {'C': 1.0, 'gamma': 0.1, 'kernel': 'rbf'}

svm = SVC(C=1.0, gamma=0.1, kernel='rbf', random_state=1)
start = time.time()
svm.fit(X_train_lda, y_train)
score_svm = svm.score(X_test_lda, y_test)
stop = time.time()
print('Test Accuracy: %.4f' % score_svm)
print('Process Time: %.2fs.' % (stop-start))

Test Accuracy: 0.8385
Process Time: 39.75s.

Kernel SVM

• 能夠比liniear更準確分類linearly non-separable的資料
• kernel選擇rbf，做GridSearch，調整參數gamma和C，結果得到最佳的組合是C=1.0，gamma=0.1
  • C和gamma給的範圍都是以10為級距，看適合較大值或較小值
• gamma選擇0.1，相對較小，讓計算similarity時不會隨資料點之間距離增加而decay太快，減少overfit的可能。
• validation在最佳組合的accuracy有0.8418，與test score的0.8385差不多，沒有overfit/underfit。

Time Complexity of Kernel SVM(rbf):

• training:
  • 必須選擇support vectors: 計算Radial Basis Function、兩兩資料點的距離向量
• testing:
  • complexity跟support vector數量呈線性關係，$\Omega$(training set大小 * training set錯誤率)
  • 也跟features數量呈線性關係
• 實際執行時間: 39.75秒
  • 比起其他演算法，kernel svm每筆資料都要計算kernel function=$exp(-\gamma \Vert x^{(i)}-x^{(j)}\Vert ^2)$，複雜得多，要花的時間因此比其他的演算法要多上很多

from sklearn.ensemble import RandomForestClassifier

param_n = [50, 100, 150, 200, 300, 500]
param_grid_forest = {'n_estimators': param_n}

gs_forest = GridSearchCV(estimator=RandomForestClassifier(criterion='gini', random_state=1),
                         param_grid=param_grid_forest,
                         scoring='accuracy',
                         cv=5,
                         n_jobs=-1)
gs_forest = gs_forest.fit(X_train_lda, y_train)
print('Best n:', gs_forest.best_params_['n_estimators'])
print('Best validation score: %.4f' % gs_forest.best_score_)

Best n: 500
Best validation score: 0.8407

forest = RandomForestClassifier(criterion='gini', n_estimators=200, random_state=1, n_jobs=2)
start = time.time()
forest.fit(X_train_lda, y_train)
score_forest = forest.score(X_test_lda, y_test)
stop = time.time()
print('Test Accuracy: %.4f' % score_forest)
print('\nProcess Time: %.2fs.' % (stop-start))

Test Accuracy: 0.8406

Process Time: 22.79s.

Random Forest

• 使用Grid Search測試不同的n_estimator:
  • 起初猜測大概理想數值在一兩百左右，所以給定範圍從30棵到200棵，結果最好的是200棵(validation score=0.8403)。
  • 考慮200是給定範圍中的最大值，於是把範圍上限調整成500，得到的結果是在500棵樹有最佳validation score=0.8407
  • 因為兩種結果非常接近，所以基於效率考量，選擇n_estimators=200。
• Test Accuracy=0.8406，與validation score非常接近，表示沒有甚麼bias。

Time Complexity of Random Forest

• building a tree:
  • n個sample要分枝的complexity大約是nlog(n)(binary tree，log以2為底)
  • f個feature，則每個分枝測試f種分法$\Rightarrow$O(f*nlog(n))
• random forest:
  • t棵樹$\Rightarrow$O(t*f*nlog(n))
• 實際執行時間:22.79秒
  • Decision Tree主要是用greedy search去找最佳的分法、計算每種分法的純度，複雜度不算太高，但因為forest一次重兩百棵，complexity增加，時間就跟著拉長。

train_sizes, train_scores, test_scores = learning_curve(estimator=forest,
                                                        X=X_train_lda,
                                                        y=y_train,
                                                        train_sizes=np.linspace(0.1,1.0,10),
                                                        cv=5,
                                                        n_jobs=-1)
train_mean = np.mean(train_scores, axis=1)
test_mean = np.mean(test_scores, axis=1)
plt.plot(train_sizes, train_mean, color='blue', marker='o', markersize=5, label='training accuracy')
plt.plot(train_sizes, test_mean, color='green', linestyle='--', marker='s', markersize=5, label='validation accuracy')
plt.legend(loc='lower right')
plt.ylim([0.7, 1.025])
plt.grid()
plt.tight_layout()
plt.show()

forest2 = RandomForestClassifier(criterion='gini', n_estimators=200, max_features=None, random_state=1, n_jobs=2)
train_sizes, train_scores, test_scores = learning_curve(estimator=forest,
                                                        X=X_train_lda,
                                                        y=y_train,
                                                        train_sizes=np.linspace(0.1,1.0,10),
                                                        cv=5,
                                                        n_jobs=-1)
train_mean = np.mean(train_scores, axis=1)
test_mean = np.mean(test_scores, axis=1)
plt.plot(train_sizes, train_mean, color='blue', marker='o', markersize=5, label='training accuracy')
plt.plot(train_sizes, test_mean, color='green', linestyle='--', marker='s', markersize=5, label='validation accuracy')
plt.legend(loc='lower right')
plt.ylim([0.7, 1.025])
plt.grid()
plt.tight_layout()
plt.show()

Learning Curve: Random Forest

• 從第一張圖看起來傾向是high variance，algorithm可以很好的fit training set，但對於validation set比較沒辦法well fit
• high variance可以透過增加regularization 或 feature來解決，所以我嘗試將max_features設為None，不限制feature的數量(預設為auto，取總feature的開根號)，但結果依然差不多，可能regularization不足的問題。

from sklearn.neighbors import KNeighborsClassifier

param_k = [10, 20, 30, 50, 70, 90]
param_grid_knn = {'n_neighbors': param_k}

gs_knn = GridSearchCV(estimator=KNeighborsClassifier(p=2, metric='minkowski'),
                         param_grid=param_grid_knn,
                         scoring='accuracy',
                         cv=5,
                         n_jobs=-1)
gs_knn = gs_knn.fit(X_train_lda, y_train)
print('Best n:', gs_knn.best_params_['n_neighbors'])
print('Best validation score: %.4f' % gs_knn.best_score_)

Best n: 50
Best validation score: 0.8378

knn = KNeighborsClassifier(n_neighbors=50, p=2, metric='minkowski') # choose k = 12
start = time.time()
knn.fit(X_train_lda, y_train)
score_knn = knn.score(X_test_lda, y_test)
stop = time.time()
print('Test Accuracy: %.4f' % score_knn)
print('\nProcess Time: %.2fs.' % (stop-start))

Test Accuracy: 0.8375

Process Time: 2.02s.

KNN

• 使用 Grid Search 找最佳n_neighbors:
  • 原本給定範圍在5到50，結果是50有最佳結果
  • 後來改測試10到90，結果依然是50有最好的validation score(0.8378)
• KNN的n_neighbors和forest的n_estimators的性質不太一樣，n_estimators上升，準確度會跟著上升，直到某個數值就會大概維持在固定的準確度；n_neighbors則是數值上升可能會有較好的準確度，但太高反而會下降、判斷不出來
• Test Accuracy=0.8375，一樣和validation score非常接近。

Time Complexity of KNN

• KNN只需要選擇與測試資料點最近的數個(50個)training資料點，並比較哪種class最多就好，不需要有更新weight、計算kernel或impurity等等，complexity較低。
• 實際執行時間:2.02秒，是所有嘗試過的演算法中最快的，複雜度明顯比較低。

train_sizes, train_scores, test_scores = learning_curve(estimator=knn,
                                                        X=X_train_lda,
                                                        y=y_train,
                                                        train_sizes=np.linspace(0.1,1.0,10),
                                                        cv=5,
                                                        n_jobs=-1)
train_mean = np.mean(train_scores, axis=1)
test_mean = np.mean(test_scores, axis=1)
plt.plot(train_sizes, train_mean, color='blue', marker='o', markersize=5, label='training accuracy')
plt.plot(train_sizes, test_mean, color='green', linestyle='--', marker='s', markersize=5, label='validation accuracy')
plt.legend(loc='lower right')
plt.ylim([0.7, 0.9])
plt.grid()
plt.tight_layout()
plt.show()

Learning Curve: KNN

• test accuracy和validation accuracy很接近，且可以達到84%左右，表示此model有好的 bias-variance trade-off

from sklearn.ensemble import VotingClassifier

weights = [0.8, 1.0, 1.2, 1.0]
ens_clf = VotingClassifier(estimators=[('lr', lr), ('svm', svm), ('forest', forest), ('knn', knn)], voting='hard', weights=weights)
start = time.time()
ens_clf.fit(X_train_lda, y_train)
score_ens = ens_clf.score(X_test_lda, y_test)
stop = time.time()
print('Accuracy: %.4f\n\nProcess Time %.2fs.' % (score_ens, (stop-start)))

Accuracy: 0.8394

Process Time 79.60s.

Ensemble Learning

• 前面嘗試了不同的演算法，分別找出各自中表現較好的model，只不過結果差不多都維持在0.82、0.83左右
• 我很想知道究竟不同的model透過多數決的預測方法，是否能得到一個更佳的準確率，所以用Ensemble的voting classifier建立ens_clf。
  • 總共合併前面四個model，logistic、kernel svm、random forest、knn
  • 在沒有調整權重的情況下執行結果接近0.83
  • 依據原本各model的準確率分配權重(較準確的權重提高)，則結果比較接近0.84
• 結果看到多數決的表現與各自分別的準確度差不多，甚至比比較好的model稍微低一些
  • 可能是因為對各個model來說，容易預測錯誤的資料都差不多，所以並沒有造成互補的效果
  • 投票的model數量比較少，也許增加model數量，或者使用"屬於某個class的機率"(voting='soft')來投票會更準一些

Time Complexity of Ensemble Learning

• 實際執行時間: 79.6秒，基本上就是把四個model都跑過一遍，最後從四個結果中選擇一個，複雜度大致上應該是線性關係上升。

Conclusion

Data Preprocessing

• 因為這次的資料量龐大，希望能有效減少資料量加快運算以及執行的時間，但同時也希望不要對accuracy有太大的影響，所以選擇Linear Discriminant Analysis來做data compression。
• data compression 對 data scaling比較敏感，必須先做standardization，之後才做LDA，因此之後的演算法都是使用標準化過的資料(儘管random forest不需要資料標準化，可能在準確度上有些影響，但應該不大，不是主要影響原因)

Model Evaluation

• 評分方式:accuracy
  • 會選擇accuracy是因為這次判斷的資料是服飾，其實並不會特別在意"涼鞋圖片中能猜出多少是涼鞋(TPR)"，或者是"認出運動鞋的機率是否比錯認成運動鞋的機率高"等等細節的資訊，也不像判診一樣需要盡量加強precision，避免False Negative，主要還是看overall的準確度就可以了。
• Logistic Regression
  • lr在majority vote的四種model中準確度相對較低
  • 這可能跟演算法本身更新weight的計算模式有關，不太適合分析pixel資料，也可能因為regularization稍微大了一點造成error
• Kernel SVM
  • svm的準確度是相對較佳的
  • svm的複雜度是四個model中最高，導致在參數測試上有許多限制，給太多數值或是測試多種不同變數都會使電腦負荷不了，而且也會導致整體預測的效率不佳(理論上希望一個程式在執行預測時效率能夠越高越好)，所以我想準確度應該還有更進步的空間
• Random Forest
  • 有最好的accuracy(雖然說最好，但其實與其他演算法都差不多)
  • 在做forest的時候有觀察到他的variance有點高，即使調整了max_features來調整，還是沒什麼改變，但也不影響bias，所以主要問題可能不是來自於參數，也許跟資料性質有關
• KNN
  • knn的準確度也很接近84%，相對比較高
  • knn的計算方法跟前面幾種很不一樣(畢竟並不算真正的"learning")，只透過鄰近的training data point來預測結果，而我原本猜測這樣的方法說不定會比其他演算法要好一些，可能更適合判斷pixel這種資料，而結果的確是有比較好，但並沒有特別適合。
• Ensemble
  • 一開始就有打算做ensemble，希望能用多數決來拉高準確度，所以其實在選擇前面的model時，"哪個演算法比較適合這次的作業"比較不是選擇的重點，而是盡量尋找能夠有較好表現的參數組合，希望當各自model都有最好的表現下，再用ensemble近一步加強
  • Ensemble的結果讓我有點意外，準確度與原本分別的model差不多，甚至不是表現最好的，這表示對於容易錯誤的資料，每個model都會判斷錯誤，要解決這樣的結果可能會需要多找幾個model，或使用weak learner的方法加重易錯資料的權重之後再進行多數決。
• Random Forest with Original Data
  • 最後我嘗試了使用未處理過的資料來跑random forest，結果可以達到87%的準確度，比其他的model都高
  • 準確度較高，但在調整參數時確實比較花時間，但單就train單次model來說，只比前面用處理過的資料的random forest執行時間多1秒(23.26)，甚至比svm要快得多，從這個結論來講，或許直接做random forest會是最好的方法
  • 選擇參數時沒有用grid search，而是直接用validation curve找適合的參數，兩種方法效果其實差不多，但畫出曲線，由人為選擇在視覺上比較直觀

Computational Complexity

• 詳細的分析都在各個model training底下
• 簡單總結:
  1. knn因為只是單純的比較相鄰的點，複雜度最低，執行時間最短
  2. logistic regression的執行時間是第二低的，他的計算量比較少(主要在計算誤差、更新weight)，比較單純
  3. random forest的執行時間比較高，有一部份是種的樹較多的原因
  4. svm的複雜度最高，需時39秒，計算kernel function使得他的計算量比較大
  5. ensemble執行時間大致上是前面幾個的總和再高一點點