<jupyter_start><jupyter_text>**Final Project: Linear Regression and K-NN comparison**---<NAME> (206760274) & <NAME> (208774026)<jupyter_code>import numpy as np
import pandas as pd
import time
import seaborn as sns
import matplotlib.pyplot as plt
from sklearn.feature_selection import RFE
from sklearn import metrics
from google.colab import drive
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsRegressor
from sklearn.linear_model import LinearRegression
from sklearn.metrics import mean_absolute_error, mean_squared_error
from math import sqrt 
from sklearn.pipeline import Pipeline

# Stop condition variable:
epsilon = 0.001  # 10 ^ -3<jupyter_output><empty_output><jupyter_text>**Initialize:** Load data file and initialize matrix X and vector y<jupyter_code>drive.mount('/content/drive', force_remount=True)
data_path = "/content/drive/MyDrive/ML/final_ex/students-grades.csv"
df = pd.read_csv(data_path)
df.corr()<jupyter_output><empty_output><jupyter_text>**Section A:** Normalize the data<jupyter_code>def normalize(df):
  """
  Return normalized data
  """
  result = df.copy()
  for feature_name in df.columns:
      if feature_name == "final grade":
        break
      max_value = df[feature_name].max()
      min_value = df[feature_name].min()
      result[feature_name] = (df[feature_name] - min_value) / (max_value - min_value)
  return result

df = normalize(df)<jupyter_output><empty_output><jupyter_text>**Section B:** Devide into train and test groups<jupyter_code>x = df[['school', 'male', 'age', 'urban', 'family size - GT3',
       'parents live together', "Mother's edu.", "Father's edu.",
       'travel time (home to school)', 'weekly study time',
       'past classes failures', 'school support', 'family edu. support',
       'private lessons', 'activities', 'nursery', 'want higher edu.',
       'internet', 'romantic rel.', 'family rel.', 'free time',
       'go out w/ friends', 'workday alcohol consumption',
       'weekend alcohol consumption', 'health status', 'absences',
       'first period grade', 'second period grade']]

y = df['final grade']
m = len(y) # num of samples
n = x.shape[1] 

# Separate the data into random groups: x_train, x_test, y_train, y_test
x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.33,random_state=101)<jupyter_output><empty_output><jupyter_text>**Section C:** Most important features- algorithms comparison Greedy algorithm: find the most important features<jupyter_code>def greedy_algorithm(x_train, y_train, x_test, y_test, k):
    f = []
    while len(f) < k:  # run until we have k features
        max_score = 0  # keeps the highest score
        feature_max_score = None  # keeps the feature with the highest score
        for i in range(n):  # for each feature
            if i in f:  # if we choose it already to f skip
                continue
            temp = f.copy()
            temp.append(i)
            object_lr = LinearRegression().fit(x_train.iloc[:, temp], y_train)
            y_test = y_test.astype('int')
            score = object_lr.score(x_test.iloc[:, temp], y_test)  # calculate score= = mean accuracy on the given test
            if max_score < score:  # if it's higher than max score update max score
                max_score = score
                feature_max_score = i
        f.append(feature_max_score)  # add the feature the got the highest score

    object_lr = LinearRegression().fit(x_train.iloc[:, f], y_train)
    prediction = object_lr.predict(x_test.iloc[:, f])
    return f, prediction<jupyter_output><empty_output><jupyter_text>RFE algorithm: find the most important features<jupyter_code>def rfe(x_train, x_test, y_train, k):  
  """
  Recursive Feature Elimination
  """
  # create the RFE model and select attributes
  rfe = RFE(LinearRegression(), n_features_to_select=k)
  rfe = rfe.fit(x_train, y_train)
  f = [] # features
  for i in range(len(rfe.support_)):
    if rfe.support_[i]:
      f.append(i)

  object_lr = LinearRegression().fit(x_train.iloc[:, f], y_train)
  prediction = object_lr.predict(x_test.iloc[:, f])  # predict with the two features we found
  return f, prediction<jupyter_output><empty_output><jupyter_text>Highest Thetas algorithm: find the most important features<jupyter_code>def highest_theta(x_train, x_test, y_train, k):
    object_lr = LinearRegression().fit(x_train, y_train)
    theta = object_lr.coef_  # get thetas
    theta = np.abs(theta)
    f = []
    for i in range(k):
        index = np.where(theta == np.max(theta))[0][0]  # get index of highest theta
        f.append(index)
        theta[index] = 0  # update it to minimum to get the second highest theta

    object_lr = LinearRegression().fit(x_train.iloc[:, f], y_train)
    prediction = object_lr.predict(x_test.iloc[:, f])  # predict with the two features we found
    return f, prediction<jupyter_output><empty_output><jupyter_text>Find out what is the idial number of important features for each algorithm + Find the k most important features<jupyter_code>def get_k(x_ts, y_ts, x_tr, y_tr):
    acc_greedy = [0]
    acc_rfe = [0]
    acc_highest_theta = [0]

    for i in range(1, n):
        f_greedy, y_pred_greedy = greedy_algorithm(x_tr, y_tr, x_ts, y_ts, i)
        acc_greedy.append(metrics.r2_score(y_ts, y_pred_greedy))
      
        f_rfe, y_pred_rfe = rfe(x_tr, x_ts, y_tr, i)
        acc_rfe.append(metrics.r2_score(y_ts, y_pred_rfe))

        f_highest_t, y_pred_higest_t = highest_theta(x_tr, x_ts, y_tr, i)
        acc_highest_theta.append(metrics.r2_score(y_ts, y_pred_higest_t))
   
    # draw greedy accuracy
    fig = plt.figure()
    plt.title("Greedy Algorithm accuracy when \n given the K most important features", size=14)
    plt.plot(acc_greedy, label="Greedy Algorithm")
    plt.xlabel("K")
    plt.ylabel("Accuracy")
    plt.xticks(range(1, 28))
    plt.ylim([0.8, 0.9])
    plt.legend()
    plt.show()
    print("\n")

    # draw RFE accuracy
    fig = plt.figure()
    plt.title("RFE Algorithm accuracy when \n given the K most important features", size=14)
    plt.plot(acc_rfe, label="RFE algorithm")
    plt.xlabel("K")
    plt.ylabel("Accuracy")
    plt.xticks(range(1, 28))
    plt.ylim([0.8, 0.9])
    plt.legend()
    plt.show()
    print("\n")

    # draw Highest Theta accuracy
    fig = plt.figure()
    plt.title("Highest Theta Algorithm accuracy when \n given the K most important features", size=14)
    plt.plot(acc_highest_theta, label="Highest theta algorithm")
    plt.xlabel("K")
    plt.ylabel("Accuracy")
    plt.xticks(range(1, 28))
    plt.ylim([0.8, 0.9])
    plt.legend()
    plt.show()
    print("\n")


    k = []

    for i in range(len(acc_greedy)-1):
        if acc_greedy[i+1] - acc_greedy[i] < epsilon:
            k.append(i)
            break
    if len(k) == 0:
      k.append(len(acc_greedy)-1)

    for i in range(len(acc_rfe)-1):
        if acc_rfe[i+1] - acc_rfe[i] < epsilon:
            k.append(i)
            break
    if len(k) == 1:
      k.append(len(acc_rfe)-1)

    for i in range(len(acc_highest_theta)-1):
        if acc_highest_theta[i+1] - acc_highest_theta[i] < epsilon:
            k.append(i)
            break
    if len(k) == 2:
      k.append(len(acc_highest_theta)-1)
    
    return k

# Get k
k = get_k(x_test, y_test, x_train, y_train)

# Get most important features
f_greedy, y_pred_greedy = greedy_algorithm(x_train, y_train, x_test, y_test, k[0])
print("Greedy Algorithm: \n There are {} important features".format(k[0]), "\n features: {}\n".format(f_greedy))

f_rfe, y_pred_rfe = rfe(x_train, x_test, y_train, k[1])
print("RFE Algorithm: \n There are {} important features".format(k[1]), "\n features: {}\n".format(f_rfe))

f_highest_t, y_pred_higest_t = highest_theta(x_train, x_test, y_train, k[2])
print("Highest Theta Algorithm: \n There are {} important features".format(k[2]), " \n features: {}\n".format(f_highest_t))<jupyter_output><empty_output><jupyter_text>**Section E:** Interesting correlation information from the data.<jupyter_code># We could observe that as absences decreases, the Grade mark increases.
# So the students who are absent for most of the classes will get their grade low.
data = pd.read_csv(data_path)
sns.barplot(data['final grade'], data['absences'], errwidth=0).set(title='The effect of the absences on the grades')
plt.show()
"""
From this we could see that Father's education does not affects student's 
grade but for the mothers who are educated their student's grade level got increased
.It is because mothers teach their children.May be...
"""
fig,(ax1,ax2)=plt.subplots(nrows=1,ncols=2,figsize=(12,5))
ax1.bar(data["Father's edu."], data['final grade'], color='blue')
ax1.set_xlabel('Father education')
ax1.set_ylabel('Grade')
ax1.set_title("Father's education vs. final grade", size=14)

ax2.bar(data["Mother's edu."], data['final grade'], color='red')
ax2.set_xlabel('Mother education')
ax2.set_ylabel('Grade')
ax2.set_title("Mother's education vs. final grade", size=14)

for txt in fig.texts:
    txt.set_visible(False)
fig,(ax1,ax2)=plt.subplots(nrows=1,ncols=2,figsize=(12,5))

ax1.bar(data['workday alcohol consumption'],data['final grade'],color='green')
ax1.set_xlabel('Workday alcohol consumption') #(numeric: from 1 - very low to 5 - very high)
ax1.set_ylabel('Grade')
ax1.set_title("Alcohol consumption on workdays \n effect on the final grade", size=14)

ax2.bar(data['weekend alcohol consumption'], data['final grade'],color='purple')
ax2.set_xlabel('Weekend alcohol consumption') #(numeric: from 1 - very low to 5 - very high)
ax2.set_ylabel('Grade')
ax2.set_title("Alcohol consumption on weekends \n effect on the final grade", size=14)

for txt in fig.texts:
    txt.set_visible(False)<jupyter_output><empty_output><jupyter_text>**Section D:** Correcting the data according to the most important features Update the x matrix according to the ideal number of the most important features:There are 2 features that had been chosen repeatedly for each of the algoithms above. These features are:"absences" and "second period grade" (25, 27 Respectively)<jupyter_code>new_x = df[['absences', 'second period grade']]
y = df['final grade']
n = new_x.shape[1]

# Separate the data into random groups: x_train, x_test, y_train, y_test
x_train, x_test, y_train, y_test = train_test_split(new_x, y, test_size=0.33,random_state=101)<jupyter_output><empty_output><jupyter_text>**Section E:** K-NN algorithm and Linear Regression comparison<jupyter_code>def knn():
  rmse_val = [] # to store rmse values for different k
  rmse_val.append(100)
  for K in range(1, 20):
      # K = K+1
      model = KNeighborsRegressor(n_neighbors = K)

      model.fit(x_train, y_train)  #fit the model
      y_pred_knn=model.predict(x_test) #make prediction on test set
      error = sqrt(mean_squared_error(y_test, y_pred_knn)) #calculate rmse
      rmse_val.append(error) #store rmse values
      print('RMSE value for k = ' , K , 'is:', error)

  # draw Highest Theta accuracy
  fig = plt.figure()
  plt.title("K-Nearest Neighbors: Find the best K \n (elbow method)", size=14)
  plt.plot(rmse_val)
  plt.xlabel("K")
  plt.ylabel("Error")
  plt.xticks(range(1, 20))
  plt.ylim([1, 3])
  plt.show()
  print("\n")

  # Chosen K
  K = 4

  model = KNeighborsRegressor(n_neighbors = K)
  model.fit(x_train, y_train)  # fit the model
  y_pred_knn = model.predict(x_test) # make prediction on test set
  error = sqrt(mean_squared_error(y_test, y_pred_knn)) # calculate rmse
  print('RMSE value for k = ' , K , 'is:', error)
  sns.distplot(y_test-y_pred_knn)
  plt.title('The difference between y-test to y-predicted:\nK-NN Algorithm', size=14) 
  for txt in fig.texts:
      txt.set_visible(False)
  plt.show()

  print("\nAccuracy of training dataset: ", model.score(x_train, y_train))
  print("Accuracy of test dataset:     ", model.score(x_test, y_test))
  print('Mean squared error: %.2f' % mean_squared_error(y_test, y_pred_knn)) # The mean squared error

  return y_pred_knn

y_pred_knn = knn()
def linearRegression():
  linear_regressor = LinearRegression()  # Create linear regression object
  linear_regressor.fit(x_train, y_train) # Train the model using the training sets
  y_pred_lr = linear_regressor.predict(x_test)    # Make predictions using the testing set
  print('\nCoefficients: \n', linear_regressor.coef_) # The coefficients

  print("\nAccuracy of training dataset: ", linear_regressor.score(x_train, y_train))
  print("Accuracy of test dataset:     ", linear_regressor.score(x_test, y_test))
  print('Mean squared error: %.2f\n' % mean_squared_error(y_test, y_pred_lr)) # The mean squared error

  sns.distplot(y_test - y_pred_lr)
  plt.title('The difference between y-test to y-predicted:\nLinear Regression Algorithm', size=14) 
  for txt in fig.texts:
      txt.set_visible(False)
  plt.show()



  return y_pred_lr

# Add a coef table:
y_pred_lr = linearRegression()
linear_regressor = LinearRegression()  # Create linear regression object
linear_regressor.fit(x_train, y_train) # Train the model using the training sets
linear_regressor_summary = pd.DataFrame(new_x.columns.values, columns=['Features'])
linear_regressor_summary['Theta'] = linear_regressor.coef_
linear_regressor_summary<jupyter_output>Coefficients: 
 [ 2.95777388 20.76222569]

Accuracy of training dataset:  0.8021289650444712
Accuracy of test dataset:      0.865639852454235
Mean squared error: 2.42<jupyter_text>**Section F:** Analyse accuracy and run-time<jupyter_code>fig = plt.figure()
plt.title("Comparing rael y-values to predicted\ny-values by K-NN", size=14)
plt.plot(range(y_test.shape[0]), y_test, color='r', label="Test")
plt.plot(range(len(y_pred_knn)), y_pred_knn, color='b', label="K-NN")
plt.ylabel("y-values")
plt.xlabel("index of y test")
plt.show()
print("\n")

fig = plt.figure()
plt.title("Comparing rael y-values to predicted\ny-values by Linear Regression", size=14)
plt.plot(range(y_test.shape[0]), y_test, color='r', label="Test")
plt.plot(range(len(y_pred_lr)), y_pred_lr, color='b', label="LR")
plt.ylabel("y-values")
plt.xlabel("index of y test")
plt.show()
def time_function(f, *args):
  """
  Call a function f with args and return the time (in seconds) that it took to execute.
  """
  tic = time.time()
  f(*args)
  toc = time.time()
  return toc - tic

s_time = time_function(knn,)
m_b_time = time_function(linearRegression,)

print('\nK-Nearest Neighbors algorithm took %f seconds' % s_time)
print('Linear Regression algorithm took %f seconds' % m_b_time)<jupyter_output>RMSE value for k =  1 is: 2.24458636254685
RMSE value for k =  2 is: 1.5352101579287551
RMSE value for k =  3 is: 1.4279412156499978
RMSE value for k =  4 is: 1.3533602511769174
RMSE value for k =  5 is: 1.3630903371294114
RMSE value for k =  6 is: 1.3762957500182276
RMSE value for k =  7 is: 1.4368354211316623
RMSE value for k =  8 is: 1.5832872967728053
RMSE value for k =  9 is: 1.5418638932749473
RMSE value for k =  10 is: 1.5434174433963588
RMSE value for k =  11 is: 1.602313638548283
RMSE value for k =  12 is: 1.6193833578592869
RMSE value for k =  13 is: 1.6467606895900442
RMSE value for k =  14 is: 1.6360510479886818
RMSE value for k =  15 is: 1.6762270327463353
RMSE value for k =  16 is: 1.655802096284779
RMSE value for k =  17 is: 1.649886917052416
RMSE value for k =  18 is: 1.6618179398864465
RMSE value for k =  19 is: 1.6649028891594104<jupyter_text>**Section G:** Overfitting calculation<jupyter_code>train_scores, test_scores = list(), list() # define lists to collect scores
values = [i for i in range(1, 30)] # define the tree depths to evaluate
for i in values:  # evaluate a decision tree for each depth
	# configure the model
	model = KNeighborsRegressor(n_neighbors=i)
	# fit model on the training dataset
	model.fit(x_train, y_train)
	# evaluate on the train dataset
	train_yhat = model.predict(x_train)
	train_acc = metrics.r2_score(y_train, train_yhat)
	train_scores.append(train_acc)
	# evaluate on the test dataset
	test_yhat = model.predict(x_test)
	test_acc = metrics.r2_score(y_test, test_yhat)
	test_scores.append(test_acc)
	# summarize progress
	print('>%d, train: %.3f, test: %.3f' % (i, train_acc, test_acc))
# plot of train and test scores vs number of neighbors
plt.plot(values, train_scores, '-o', label='Train')
plt.plot(values, test_scores, '-o', label='Test')
plt.title("The accuracy level when\nperforming K-NN algorithm", size=14)
plt.xlabel("Number of neighbors")
plt.ylabel("Accuracy")
plt.ylim([0.8, 0.9])
plt.legend()
plt.show()
linear_regressor = LinearRegression()  # Create linear regression object
linear_regressor.fit(x_train, y_train) # Train the model using the training sets
y_pred_lr = linear_regressor.predict(x_test)    # Make predictions using the testing set
y_train_pred_lr = linear_regressor.predict(x_train)    # Make predictions using the train set

acc_train = linear_regressor.score(x_train, y_train)
acc_test = linear_regressor.score(x_test, y_test)
print("\nAccuracy of training dataset: ", acc_train)
print("Accuracy of test dataset:     ", acc_test)
print('Difference: ', acc_test - acc_train)<jupyter_output>Accuracy of training dataset:  0.8021289650444712
Accuracy of test dataset:      0.865639852454235
Difference:  0.06351088740976385
{'fraction_non_alphanumeric': 0.12043647338789251, 'fraction_numerical': 0.03697254628823495, 'mean_word_length': 4.3343653250774, 'pattern_counts': {'":': 1, '<': 57, '<?xml version=': 0, '>': 53, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '13', 'dir': 'jupyter-structured-clean-dedup', 'id': '250746', 'license': 'MIT', 'n_tokens_mistral': 6587, 'n_tokens_neox': 6019, 'n_words': 1628, 'path': 'KNN & Linear Regression Comparison/KNN & Linear Regression Comparison.ipynb', 'repo_name': 'EladDavid-SW/Machine-Learning', 'size': '17239'}