Programming, Network, Office, Hardware, Software, Design, Photography.. I am just a GEEK
Kĩ thuật phân lớp được tiến hành bao gồm 2 bước : Xây dựng mô hình và sử dụng mô hình .
- Xây dựng mô hình : là mô tả một tập những lớp được định nghĩa trước trong đó : mỗi bộ hoặc mẫu được gán thuộc về một lớp được định nghĩa trước như là được xát định bởi thuộc tính nhãn lớp , tập hợp của những bộ được sử dụng trong việc sử dụng mô hình được gọi là tập huấn luyện . Mô hình được biểu diễn là những luật phân lớp , cây quyết định và những công thức toán học .
- Sử dụng mô hình : Việc sử dụng mô hình phục vụ cho mục đích phân lớp dữ liệu trong tương lai hoặc phân lớp cho những đối tượng chưa biết đến . Trước khi sử dụng mô hình người ta thường phải đánh giá tính chính xát của mô hình trong đó : nhãn được biết của mẫu kiểm tra được so sánh với kết quả phân lớp của mô hình , độ chính xác là phần trăm của tập hợp mẫu kiểm tra mà phân loại đúng bởi mô hình , tập kiểm tra là độc lập với tập huấn luyện .
Phân lớp là một hình thức học được giám sát tức là : tập dữ liệu huấn luyện ( quan sát , thẩm định .) đi đôi với những nhãn chỉ định lớp quan sát , những dữ liệu mới được phân lớp dựa trên tập huấn luyện .
Ngược lại với hình thức học được giám sát là hình thức học không được giám sát lúc đó nhãn lớp của tập dữ liệu huấn luyện là không được biết đến.
Các thuật toán phân lớp dữ liệu
Phân lớp với cây quyết định (decision tree)
Phân lớp với Naïve Bayesian
Phân lớp với k phần tử gần nhất (k-nearest neighbor)
Phân lớp với máy vector hỗ trợ (SVM)
Phân lớp với mạng neural (neural network)
Phân lớp dựa trên tiến hoá gen (genetic algorithms)
Phân lớp với lý thuyết tập thô, tập mờ (rough sets)
Phân lớp với lý thuyết tập mờ (fuzzy sets)
Phân lớp với cây quyết định (decision tree) – Thuật toán ID3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 |
import pandas as pd import numpy as np from scipy import stats from copy import deepcopy import argparse def status(message): print(message) def read_file(path): status("Reading file ...") try: df = pd.read_csv(args.input, sep=',') return df except: print("File not found!") def write_file(path, file, data): status("Writing " + file + " file ...") try: f = open(path, 'w') f.write(data) f.close() except: print("Cannot write a file!") # Function: Performs a Chi_Squared test or Fisher Exact test def chi_squared_test(label_df, feature_df): label_df.reset_index(drop=True, inplace=True) feature_df.reset_index(drop=True, inplace=True) data = pd.concat([pd.DataFrame(label_df.values.reshape((label_df.shape[0], 1))), feature_df], axis=1) data.columns = ["label", "feature"] contigency_table = pd.crosstab(data.iloc[:, 0], data.iloc[:, 1], margins=False) m = contigency_table.values.sum() if m <= 10000 and contigency_table.shape == (2, 2): p_value = stats.fisher_exact(contigency_table) else: p_value = stats.chi2_contingency(contigency_table, correction=False) # (No Yates' Correction) return p_value[1] # Function: Prediction def prediction_dt_id3(model, Xdata): Xdata = Xdata.reset_index(drop=True) ydata = pd.DataFrame(index=range(0, Xdata.shape[0]), columns=["Prediction"]) data = pd.concat([ydata, Xdata], axis=1) rule = [] # Preprocessing - Boolean Values for j in range(0, data.shape[1]): if data.iloc[:, j].dtype == "bool": data.iloc[:, j] = data.iloc[:, j].astype(str) # Preprocessing - Binary Values for j in range(1, data.shape[1]): if data.iloc[:, j].dropna().value_counts().index.isin([0, 1]).all(): for i in range(0, data.shape[0]): if data.iloc[i, j] == 0: data.iloc[i, j] = "0" else: data.iloc[i, j] = "1" data = data.applymap(str) dt_model = deepcopy(model) for i in range(0, len(dt_model)): dt_model[i] = dt_model[i].replace("{", "") dt_model[i] = dt_model[i].replace("}", "") dt_model[i] = dt_model[i].replace(".", "") dt_model[i] = dt_model[i].replace("IF ", "") dt_model[i] = dt_model[i].replace("AND", "") dt_model[i] = dt_model[i].replace("THEN", "") dt_model[i] = dt_model[i].replace("=", "") for i in range(0, len(dt_model) - 2): splited_rule = [x for x in dt_model[i].split(" ") if x] rule.append(splited_rule) for i in range(0, Xdata.shape[0]): for j in range(0, len(rule)): rule_confirmation = len(rule[j]) / 2 - 1 rule_count = 0 for k in range(0, len(rule[j]) - 2, 2): if (data[rule[j][k]][i] in rule[j][k + 1]): rule_count = rule_count + 1 if (rule_count == rule_confirmation): data.iloc[i, 0] = rule[j][len(rule[j]) - 1] else: k = len(rule[j]) for i in range(0, Xdata.shape[0]): if data.iloc[i, 0] == "nan": data.iloc[i, 0] = dt_model[len(dt_model) - 1] return data # Function: ID3 Algorithm def dt_id3(Xdata, ydata, pre_pruning="none", chi_lim=0.1): ################ Part 1 - Preprocessing ############################# # Preprocessing - Creating Dataframe status("ID3 Initializing decision tree ") name = ydata.name ydata = pd.DataFrame(ydata.values.reshape((ydata.shape[0], 1))) dataset = pd.concat([ydata, Xdata], axis=1) # Preprocessing - Boolean Values for j in range(0, dataset.shape[1]): if dataset.iloc[:, j].dtype == "bool": dataset.iloc[:, j] = dataset.iloc[:, j].astype(str) # Preprocessing - Binary Values for j in range(0, dataset.shape[1]): if dataset.iloc[:, j].dropna().value_counts().index.isin([0, 1]).all(): for i in range(0, dataset.shape[0]): if dataset.iloc[i, j] == 0: dataset.iloc[i, j] = "0" else: dataset.iloc[i, j] = "1" dataset = dataset.applymap(str) # Preprocessing - Unique Words List unique = [] uniqueWords = [] for j in range(0, dataset.shape[1]): for i in range(0, dataset.shape[0]): token = dataset.iloc[i, j] if not token in unique: unique.append(token) uniqueWords.append(unique) unique = [] # Preprocessing - Label Matrix label = np.array(uniqueWords[0]) label = label.reshape(1, len(uniqueWords[0])) ################ Part 2 - Initialization ############################# # ID3 - Initializing Variables i = 0 branch = [None] * 1 branch[0] = dataset gain = np.empty([1, branch[i].shape[1]]) rule = [None] * 1 rule[0] = "IF " root_index = 0 skip_update = False stop = 2 ################ Part 3 - id3 Algorithm ############################# # ID3 - Algorithm while (i < stop): entropy = 0 denominator_1 = branch[i].shape[0] for entp in range(0, label.shape[1]): numerator = (branch[i][(branch[i].iloc[:, 0] == label[0, entp])].count())[0] if numerator > 0: entropy = entropy - (numerator / denominator_1) * np.log2((numerator / denominator_1)) gain.fill(entropy) for element in range(1, branch[i].shape[1]): if len(branch[i]) == 0: skip_update = True break if len(np.unique(branch[i][0])) == 1 or len(branch[i]) == 1 or gain.sum(axis=1) == 0: rule[i] = rule[i] + " THEN : " + branch[i].iloc[0, 0] + "." rule[i] = rule[i].replace(" AND THEN ", " THEN ") skip_update = True break if i > 0 and pre_pruning == "chi_2" and chi_squared_test(branch[i].iloc[:, 0], branch[i].iloc[:, element]) > chi_lim: if "." not in rule[i]: rule[i] = rule[i] + " THEN : " + branch[i].agg(lambda x: x.value_counts().index[0])[ 0] + "." rule[i] = rule[i].replace(" AND THEN ", " THEN ") skip_update = True continue for word in range(0, len(uniqueWords[element])): denominator_2 = (branch[i][(branch[i].iloc[:, element] == uniqueWords[element][word])].count())[0] for lbl in range(0, label.shape[1]): numerator = (branch[i][(branch[i].iloc[:, 0] == label[0, lbl]) & ( branch[i].iloc[:, element] == uniqueWords[element][word])].count())[0] if numerator > 0: gain[0, element] = gain[0, element] + (denominator_2 / denominator_1) * ( numerator / denominator_2) * np.log2((numerator / denominator_2)) if skip_update == False: gain[0, 0] = -gain[0, 0] root_index = np.argmax(gain) gain[0, 0] = -gain[0, 0] rule[i] = rule[i] + list(branch[i])[root_index] for word in range(0, len(uniqueWords[root_index])): branch.append(branch[i][branch[i].iloc[:, root_index] == uniqueWords[root_index][word]]) rule.append(rule[i] + " = " + "{" + uniqueWords[root_index][word] + "}") for logic_connection in range(1, len(rule)): if len(np.unique(branch[i][0])) != 1 and rule[logic_connection].endswith(" AND ") == False and rule[ logic_connection].endswith("}") == True: rule[logic_connection] = rule[logic_connection] + " AND " skip_update = False i = i + 1 # print("iteration: ", i) stop = len(rule) for i in range(len(rule) - 1, -1, -1): if rule[i].endswith(".") == False: del rule[i] # rule.append("Total Number of Rules: " + str(len(rule))) # rule.append(dataset.agg(lambda x: x.value_counts().index[0])[0]) # print("End of Iterations") return rule def switch(best): switcher = { 0: 'Entropy', 1: 'Information Gain', 2: 'Information Gain Ratio', 3: 'Gini Index' } return switcher.get(best, "Invalid") ############### End of Function ############## def main(args): df = read_file(args.input) X = df.iloc[:, :-1] y = df.iloc[:, -1] dt_model = dt_id3(Xdata=X, ydata=y, pre_pruning="none", chi_lim=0.1) test = df.iloc[0:2, 0:4] prediction_dt_id3(dt_model, test) temp = [] dataStr = '' dataStr += "=== Classifier model( full training set)=== \n" for i in range(0, len(dt_model)): dt_model[i] = dt_model[i].replace("{", "") dt_model[i] = dt_model[i].replace("}", "") dt_model[i] = dt_model[i].replace(".", "") dt_model[i] = dt_model[i].replace("IF ", "") dt_model[i] = dt_model[i].replace("AND", "|") dt_model[i] = dt_model[i].replace("THEN", "") arr = dt_model[i].split("|") for i in range(0, len(arr)): if arr[i] not in temp: dataStr += arr[i] + '\n' temp.append(arr[0]) dataStr += "=== Best attribute criteria=== \n" dataStr += switch(int(args.best_att)) write_file(args.output, '', dataStr) status("Finish!") if __name__ == "__main__": parser = argparse.ArgumentParser(description='Classification') parser.add_argument('input', help='input file path') parser.add_argument('output', help='output file path') parser.add_argument('folds', help='folds number of cross validation ') parser.add_argument('best_att', default=[0, 1, 2, 3], help='best attribute 0: Entropy, 1: Information Gain 2: Information Gain Ratio, và 3: Gini Index') args = parser.parse_args() main(args) |
Buy me a coffee
Leave a Reply