KNN算法的Python实现

659441806

# Author :CWX　　
# Date :2015/9/1
　　
# Function: A classifier which using KNN algorithm
　　

　　
import math
　　

　　
attributes = {"age":0,"workclass":1,"fnlwg":2,"education":3,"education-num":4,
　　"marital-status":5,"occupation":6,"relationship":7,"race":8,
　　"sex":9,"capital-gain":10,"capital-loss":11,"hours-per-week":12,
　　"native-country":13,"salary":14
　　}
　　

　　
def read_txt(filename):
　　
#read data and convert it into list
　　items = []
　　fp = open(filename,'r')
　　lines = fp.readlines()
　　for line in lines:
　　line = line.strip('\n')
　　items.append(line)
　　fp.close()
　　

　　i = 0
　　b = []
　　for i in range(len(items)):
　　b.append(items.split(','))
　　return b
　　

　　
def computeNa(items):
　　
# detect missing value in list and handle it
　　
# items - an whole list
　　for item in items[:]:
　　if item.count(' ?') > 0:
　　items.remove(item)
　　# if item.count(' ?') >= -1:
　　# items.remove(item)
　　return items
　　

　　
def disCal(lst1,lst2,type):
　　
# calculting distance between lst1 and lst2
　　distance = 0;
　　if type == "Manhattan" or type == "manhattan":
　　for i in range(len(lst2) - 1):
　　distance += abs(lst1 - lst2)
　　elif type == "Elucildean" or type == "elucildean":
　　for i in range(len(lst2) - 1):
　　distance += math.sqrt((lst1 - lst2)**2)
　　else:
　　print "Error in type name"
　　distance = -1
　　return distance
　　

　　
def computeContinous(datalist,attribute):
　　
# compute continous attributes in list
　　min_val = int(datalist[0][attribute])
　　max_val = int(datalist[0][attribute])
　　for items in datalist:
　　if int(items[attribute]) < min_val:
　　min_val = int(items[attribute])
　　elif int(items[attribute]) > max_val:
　　max_val = int(items[attribute])
　　for items in datalist[:]:
　　items[attribute] = (int(items[attribute]) - min_val) / float(max_val - min_val)
　　return datalist
　　

　　
def computeOrdinal(datalist,attribute,level):
　　
# compute ordinal attribute in datalist
　　level_dict = {}
　　for i in range(len(level)):
　　level_dict[level] = float(i) / (len(level) - 1)
　　
#level_dict[level] = i
　　for items in datalist[:]:
　　items[attribute] = level_dict[items[attribute]]
　　return datalist
　　

　　
def KnnAlgorithm(dataTrain,sample,attribute,k):
　　mergeData = dataTrain
　　mergeData.append(sample)
　　data = preProcessing(mergeData)
　　distance = []
　　for i in range(len(data)-2):
　　distance.append(disCal(data,data[len(data)-1],"Elucildean"))
　　copy_dis = distance[:] # notice : not copy_dis = distance ,if it will be wrong
　　distance.sort()
　　

　　class_dict = {"Yes":0,"No":0}
　　for i in range(k):
　　index = copy_dis.index(distance)
　　if data[index][attribute] == " >50K":
　　class_dict["Yes"] += 1
　　else:
　　class_dict["No"] += 1
　　if  class_dict["Yes"] > class_dict["No"]:
　　print "sample's salary >50K"
　　else:
　　print "sample's salary <=50K"
　　

　　
def preProcessing(datalist):
　　b = computeNa(datalist)
　　

　　b = computeContinous(b,attributes["age"])
　　

　　workclass_level = [" Private"," Self-emp-not-inc"," Self-emp-inc"," Federal-gov"," Local-gov"," State-gov"," Without-pay"," Never-worked"]
　　b = computeOrdinal(b,attributes["workclass"],workclass_level)
　　

　　b = computeContinous(b,attributes["fnlwg"])
　　

　　education_level =[" Bachelors"," Some-college"," 11th"," HS-grad"," Prof-school",
　　" Assoc-acdm"," Assoc-voc"," 9th"," 7th-8th"," 12th"," Masters"," 1st-4th"," 10th"," Doctorate"," 5th-6th"," Preschool"]
　　b = computeOrdinal(b,attributes["education"],education_level)
　　

　　b = computeContinous(b,attributes["education-num"])
　　

　　marital_status_level = [" Married-civ-spouse"," Divorced"," Never-married"," Separated"," Widowed"," Married-spouse-absent"," Married-AF-spouse"]
　　b = computeOrdinal(b,attributes["marital-status"],marital_status_level)
　　

　　occupation_level  = [" Tech-support"," Craft-repair"," Other-service"," Sales"," Exec-managerial"," Prof-specialty"," Handlers-cleaners",
　　" Machine-op-inspct"," Adm-clerical"," Farming-fishing"," Transport-moving"," Priv-house-serv"," Protective-serv"," Armed-Forces"]
　　b = computeOrdinal(b,attributes["occupation"],occupation_level)
　　

　　relationship_level = [" Wife"," Own-child"," Husband"," Not-in-family"," Other-relative"," Unmarried"]
　　b = computeOrdinal(b,attributes["relationship"],relationship_level)
　　

　　race_level = [" White"," Asian-Pac-Islander"," Amer-Indian-Eskimo"," Other"," Black"]
　　b = computeOrdinal(b,attributes["race"],race_level)
　　

　　sex_level = [" Female", " Male"]
　　b = computeOrdinal(b,attributes["sex"],sex_level)
　　

　　b = computeContinous(b,attributes["capital-gain"])
　　

　　b = computeContinous(b,attributes["capital-loss"])
　　

　　b = computeContinous(b,attributes["hours-per-week"])
　　

　　native_country_level = [" United-States"," Cambodia"," England"," Puerto-Rico"," Canada"," Germany"," Outlying-US(Guam-USVI-etc)"," India",
　　" Japan"," Greece"," South"," China"," Cuba"," Iran"," Honduras"," Philippines"," Italy"," Poland"," Jamaica"," Vietnam"," Mexico"," Portugal",
　　" Ireland"," France"," Dominican-Republic"," Laos"," Ecuador"," Taiwan"," Haiti"," Columbia"," Hungary"," Guatemala"," Nicaragua"," Scotland",
　　" Thailand"," Yugoslavia"," El-Salvador"," Trinadad&Tobago"," Peru"," Hong"," Holand-Netherlands"]
　　b = computeOrdinal(b,attributes["native-country"],native_country_level)
　　return b
　　

　　
def assessment(dataTrain,dataTest,atrribute,k):
　　mergeData = computeNa(dataTrain)
　　len_train = len(mergeData)
　　mergeData.extend(computeNa(dataTest))
　　data = preProcessing(mergeData)
　　len_test = len(data) - len_train
　　res_dict = {"correct":0,"wrong":0}
　　for i in range(len_test):
　　distance = []
　　class_dict = {"Yes":0,"No":0}
　　for j in range(len_train):
　　distance.append(disCal(data[j],data[i+len_train],"Elucildean"))
　　copy_dis = distance[:]
　　distance.sort()
　　for m in range(k):
　　index = copy_dis.index(distance[m])
　　if data[index][atrribute] == " >50K":
　　class_dict["Yes"] += 1
　　else:
　　class_dict["No"] += 1
　　if class_dict["Yes"] > class_dict["No"] and mergeData[i+len_train][atrribute] == " >50K.": #Attention : in train data in the end of lines there is a "."
　　res_dict["correct"]  += 1
　　elif mergeData[i+len_train][atrribute] == " <=50K." and class_dict["Yes"] < class_dict["No"]:
　　res_dict["correct"]  += 1
　　else:
　　res_dict["wrong"] += 1
　　correct_ratio = float(res_dict["correct"]) / (res_dict["correct"] + res_dict["wrong"])
　　print "correct_ratio = ",correct_ratio
　　
filename = "H:\BaiduYunDownload\AdultDatasets\Adult_data.txt"
　　
#sample = [" 80"," Private"," 226802"," 11th"," 7"," Never-married"," Machine-op-inspct"," Own-child"," Black"," Male"," 0"," 0"," 40"," United-States"," <=50K"]
　　
sample = [" 65"," Private"," 184454"," HS-grad"," 9"," Married-civ-spouse"," Machine-op-inspct"," Husband"," White"," Male"," 6418"," 0"," 40"," United-States"," >50K"]
　　
# this samples salary <=50K#
　　
# filename = "D:\MyDesktop-HnH\data.txt"
　　
a = read_txt(filename)
　　
print len(a)
　　

　　
k = 3
　　
#KnnAlgorithm(a,sample,attributes["salary"],k)
　　

　　
trainName = "H:\BaiduYunDownload\AdultDatasets\Adult_test.txt"
　　
trainData = read_txt(trainName)
　　
#preProcessing(trainData)
　　
assessment(a,trainData,attributes["salary"],k)