0%

分类算法概述

第一章 KNN算法

1.1 问题定义:

给定m个已被分为Cn类个样本[监督算法],对未标记类别的测试数据data求其所属类别?

1.2 算法描述:

1)计算测试数据与各个训练数据之间的距离;

2)按照距离的递增关系进行排序;

3)选取距离最小的K个点;

4)确定前K个点所在类别的出现频率;

5)返回前K个点中出现频率最高的类别作为测试数据的预测分类。

由算法思想可得,影响KNN算法效果有:
距离和相似度度量方法的选择在具体问题中,度量距离和相似度时,可能也需要特征归一化处理。

自定义K值的大小两个因素

另一方面,KNN算法在执行过程中 对训练数据进行k邻近搜索,所以训练集的存储数据结构,对KNN算法的时间复杂度具有重大影响,故,我们在实际应用中需要给训练集一个便于搜索的数据结构。

1.3 基于KNN的手写数字识别

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
#-*-coding:utf-8-*-
from numpy import *
import operator
from os import listdir

def classify0(inX, dataSet, labels, k):
'''
KNN算法分类
'''
dataSetSize = dataSet.shape[0]
diffMat = tile(inX, (dataSetSize,1)) - dataSet

# 求测试数据与每一个训练集样本的欧式距离
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances**0.5

#欧氏距离,从小到大的索引
sortedDistIndicies = distances.argsort()

classCount={}
## 统计K个统计量中存在的各个数字的个数
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]

classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1

sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)

return sortedClassCount[0][0]


def img2vector(filename):
'''
将一个txt文件转为1*1024个narray
'''

returnVect = zeros((1,1024))
fr = open(filename) #打开每个存数字的txt文件
for i in range(32):
lineStr = fr.readline() #readline()每次对txt文件读一行
for j in range(32):
returnVect[0,32*i+j] = int(lineStr[j])
return returnVect

def handwritingClassTest():

hwLabels = []
trainingFileList = listdir(r'C:\Users\chend\PycharmProjects\MNIST\trainingDigits')
print(trainingFileList )

m = len(trainingFileList)
print(m,'张手写图片')
trainingMat = zeros((m,1024)) #m*1024大矩阵

for i in range(m):
fileNameStr = trainingFileList[i] #trainingDigits文件夹下的每个txt文件名
fileStr = fileNameStr.split('.')[0] #0_0...0_102/.....9_203
classNumStr = int(fileStr.split('_')[0]) #获取到每个文件对应的数字值
hwLabels.append(classNumStr) #hwLabels列表中存放所有文本对应的数字
#trainingMat每一行(1024列)存放一个txt文件中的数字、
##训练集中的数字全部读完,并存入m*1024的大矩阵中
trainingMat[i,:] = img2vector(r'C:\Users\chend\PycharmProjects\MNIST\trainingDigits/%s' % fileNameStr)
# print(trainingMat.shape)
# set_printoptions(threshold=inf)
# print(trainingMat)

#读取测试集中的的所有txt文件
testFileList = listdir(r'C:\Users\chend\PycharmProjects\MNIST\testDigits')
errorCount = 0.0 #错误率
mTest = len(testFileList)
print(mTest,'张测试手写图片')
for i in range(mTest):
fileNameStr = testFileList[i]
fileStr = fileNameStr.split('.')[0]
classNumStr = int(fileStr.split('_')[0]) # 测试数据真实值
vectorUnderTest = img2vector(r'C:\Users\chend\PycharmProjects\MNIST\testDigits/%s' % fileNameStr)


#对每个测试集中的txt文件分类
classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)

print ("the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr))

if classifierResult != classNumStr:
print('这里识别错了')
errorCount += 1.0


print("\n the total number of errors is: %d" % errorCount)
print("\n the total error rate is: %f" % (errorCount/float(mTest)))


if __name__=="__main__":
handwritingClassTest()

实验结果:
K=3时:

k=3

K=5时:

k=5

K=7时:

k=7

K=9时:

k=9

1.4 参考资料:

https://wizardforcel.gitbooks.io/dm-algo-top10/content/knn.html

https://www.cnblogs.com/ybjourney/p/4702562.html

李航 著 《统计学习方法》北京:清华大学出版社 2012

https://zhuanlan.zhihu.com/p/25994179

第二章 KMeans算法

2.1 算法描述:

1、用中心向量c1, c2, …, ck初始化k个聚类中心

2、分组:
(1)将样本分配给距离其最近的中心向量

(2)由这些样本构造不相交( non-overlapping )的聚类

3、确定中心:
用各个聚类的中心向量作为新的中心

4、重复分组和确定中心的步骤,直至算法收敛。
收敛的标志可以简单认为:连续两轮聚类结果相同。

2.2 算法评估:

  1. 算法收敛速度和初始化K个聚类中心相关;
  2. K值的选择影响聚类的效果;
  3. 特别低,Kmeans只适合类的中心是可以被计算的才适用,(如:均值表示中心,当无法用数学符号表示时,Kmeans算法就无用武之地)
  4. Kmeans 对于“躁声”和孤立点数据是敏感的,少量的该类数据能够对平均值产生极大的影响。

2.3 KMeans例子

给n个随机点分类

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
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

# G1 = np.random.randn(300, 2) + 10
# G2 = np.random.randn(300, 2)
# G3 = np.random.randn(3000, 2) - 10
# data = np.row_stack((G1, G2, G3))
data=np.random.randint(1000,size=(1000,2))


#计算欧式距离
def dist(source,dest):
#K表聚类数目
K=dest.shape[0]

# result存放每个样本到簇中心的欧式距离,result[i,j]表示第i个样本点与第j个簇中心点之间的欧氏距离
result = np.zeros((source.shape[0],K))

for i in range(K):
result[:,i] = np.sqrt(np.sum(np.square(source-dest[i]),axis=1))

return result



# 分组
def group(distmat,K):

'''

:param distmat:
:param K:
:return: Series
'''
distindex=np.argsort(distmat,axis=1)

# 找出所有数据离哪个簇中心的距离最短
mindist=distindex[:,0]
# print('找出所有数据离哪个簇中心的距离最短:')
# print(mindist)

clusters=pd.Series(np.arange(distmat.shape[0]),index=mindist)

# print(clusters)

return clusters


def initCluster(data,K):
#随机选出K个簇中心点的下表
centClusterindexs = np.random.choice(data.shape[0] - 1, K,replace=False)
# print('选得簇中心点下标:',centClusterindexs)
# 选出的K个簇中心点
centCluster = data[centClusterindexs]
# print('选得簇邻近点坐标:')
# print(centCluster)
#所有样本到K个簇中心点的欧式距离,distmat=result
distmat = dist(data, centCluster)
# print('所有样本到K个簇中心点的欧式距离:')
# print(distmat)
# 得到距离后,进行分组(形参为:距离矩阵,聚类数目)
clustermat = group(distmat, K)

return clustermat


def getcentCluster(preCluster,K):

centCluster=np.zeros((K,2))

cls=preCluster.groupby(by=preCluster.index)
for i in range(K):
centCluster[i]=np.sum(data[cls.get_group(i).values],axis=0)/len(cls.get_group(i))
#centCluster 为坐标矩阵
return centCluster



def kmeansClassfier(input,K):
'''
1. 随机选择k个簇中心点
2. 分组:通过欧式距离来分组
3. 重新计算簇中心
4. 重复步骤2,3 直到收敛(收敛的充分必要条件为:分组连续两次不再改变。必要条件为:聚类中心连续两次不在改变)
'''
# 初始化,先分组
initmat=initCluster(data,K)
# print(len(initmat))
print('初始化分组的结果为:')
#Seriez 的 索引表示该样本所属的类别(0,1,2,...K类),对应的表示样本的索引
print(initmat)


changeCluster=True
clustermat = initmat.copy()
countCluster=1
while changeCluster:
preCluster = clustermat
# 重新计算聚类中心 坐标)
centCluster=getcentCluster(preCluster,K)

distmat=dist(data,centCluster)

clustermat= group(distmat,K)

countCluster+=1

# print('clustermat')
# print(type(clustermat))
# print(clustermat)
# print('preCluster')
# print(type(preCluster))
# print(preCluster)

# 这里有个大问题:我认为分组不再改变,便是收敛。其实是错误的。
if (clustermat.index == preCluster.index ).all() and (clustermat.values == preCluster.values ).all():
changeCluster=False
else:
changeCluster=True

print('聚类次数:' ,countCluster)
print(countCluster)
# print(countCluster)

# 聚类后的结果显示(不同的聚类用不同的颜色表示):
classes=clustermat.groupby(by=clustermat.index)
plt.figure()
for i in range (K):
plt.scatter(data[classes.get_group(i).values][:,0],data[classes.get_group(i).values][:,1],edgecolors='red')
plt.show()



if __name__=="__main__":

## plt.scatter 散点图
plt.figure(figsize=(8,8))
plt.scatter(data[:,0],data[:,1],label='scatter')
plt.legend(loc='best')

# plt.xlim((-15,15))
# plt.ylim((-15,15))
# plt.xlabel('x axis')
# plt.ylabel('y axis')
# plt.xticks(np.linspace(-15,15,31))
# plt.yticks(np.linspace(-15,15,31))
# ax=plt.gca()
# ax.spines['right'].set_color('none')
# ax.spines['top'].set_color('none')
# ax.xaxis.set_ticks_position('bottom')
# ax.yaxis.set_ticks_position('left')
# ax.spines['bottom'].set_position(('data',0))
# ax.spines['left'].set_position(('data',0))
#显示聚类前的图
plt.show()
# print(data)
# print(data.shape)
#
K=3
kmeansClassfier(data,K)

实验结果分析:
聚类前数据分布:
聚类前数据分布

正确的聚类结果:
正确的聚类结果

通过做实验我们发现 当我们的样本 实际上 聚类结果是 显然的,如我们产生如下数据集:

1
2
3
4
G1 = np.random.randn(300, 2) + 10
G2 = np.random.randn(300, 2)
G3 = np.random.randn(3000, 2) - 10
data = np.row_stack((G1, G2, G3))

显然 G1 G2 G3 各为一类,但是当我初始化簇中心都选在G1上,这样就会导致 G1被分为两类,G2 G3 被划分到一类。 这显然错误了。所以我们需要一个好的选择初始簇中心的方法。所以产生如下错误聚类结果:

不理想(错误)的聚类结果:
不理想(错误)的结果

Kmeans的评价指标:

其中表示簇中心点

由上述可知,初始化随机选择的簇中心点对我们的算法影响效果巨大,所以我们加入Kmeans的评价指标,经过多轮迭代,找出最好的一组聚类结果。参考代码如下:

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
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

# G1 = np.random.randn(300, 2) + 10
# G2 = np.random.randn(300, 2)
# G3 = np.random.randn(300, 2) - 10
# G4 = np.random.randn(300,2)-np.array([10,-10])
# data = np.row_stack((G1, G2, G3))
data=np.random.randint(1000,size=(1000,2))


#计算欧式距离
def dist(source,dest):
#K表聚类数目
K=dest.shape[0]

# result存放每个样本到簇中心的欧式距离,result[i,j]表示第i个样本点与第j个簇中心点之间的欧氏距离
result = np.zeros((source.shape[0],K))

for i in range(K):
result[:,i] = np.sqrt(np.sum(np.square(source-dest[i]),axis=1))

return result



# 分组
def group(distmat,K):
distindex=np.argsort(distmat,axis=1)
# 找出所有数据离哪个簇中心的距离最短
mindist=distindex[:,0]
# print('找出所有数据离哪个簇中心的距离最短:')
# print(mindist)
clusters=pd.Series(np.arange(distmat.shape[0]),index=mindist)
# print(clusters)
return clusters

def initCluster(data,K):
#随机选出K个簇中心点的下表
centClusterindexs = np.random.choice(data.shape[0] - 1, K,replace=False)
# print('选得簇中心点下标:',centClusterindexs)
# 选出的K个簇中心点
centCluster = data[centClusterindexs]
# print('选得簇邻近点坐标:')
# print(centCluster)
#所有样本到K个簇中心点的欧式距离,distmat=result
distmat = dist(data, centCluster)
# print('所有样本到K个簇中心点的欧式距离:')
# print(distmat)
# 得到距离后,进行分组(形参为:距离矩阵,聚类数目)
clustermat = group(distmat, K)
return clustermat


def getcentCluster(preCluster,K):

centCluster=np.zeros((K,2))
cls=preCluster.groupby(by=preCluster.index)
for i in range(K):
centCluster[i]=np.sum(data[cls.get_group(i).values],axis=0)/len(cls.get_group(i))
#centCluster 为坐标矩阵
return centCluster

def kmeansClassfier(input,K):
'''
1. 随机选择k个簇中心点
2. 分组:通过欧式距离来分组
3. 重新计算簇中心
4. 重复步骤2,3 直到收敛
'''

# 初始化,先分组
initmat=initCluster(data,K)
changeCluster=True
clustermat = initmat.copy()
countCluster=1
while changeCluster:
preCluster = clustermat
# 重新计算聚类中心 坐标)
centCluster = getcentCluster(preCluster,K)

distmat = dist(data,centCluster)

clustermat = group(distmat,K)

countCluster+=1

### 算法核心,收敛判断 :连续两次分组不在改变

if (clustermat.index == preCluster.index ).all() and (clustermat.values == preCluster.values ).all():
# lossKmeans()
changeCluster=False

else:
changeCluster=True

# # 聚类后的结果显示(不同的聚类用不同的颜色表示):
# classes=clustermat.groupby(by=clustermat.index)
# plt.figure()
# for i in range (K):
# plt.scatter(data[classes.get_group(i).values][:,0],data[classes.get_group(i).values][:,1])
# plt.show()
return clustermat,centCluster


def lossKmeans(clustermat,centCluster):
#计算各个簇内的所有欧拉距离,我们希望簇内欧拉距离尽可能小
K=centCluster.shape[0]
grops=clustermat.groupby(by=clustermat.index)
sumloss=0
for i in range(K):
sumloss+=np.sum(np.square(np.sum(np.square(data[grops.get_group(i).values]-centCluster[i]),axis=1)),axis=0)
return sumloss

#还可以计算不同簇内的相关度,我们希望不同的簇相关度尽可能低


if __name__=="__main__":

## plt.scatter 散点图
plt.figure(figsize=(8,8))
plt.scatter(data[:,0],data[:,1],label='scatter')
plt.legend(loc='best')

#显示聚类前的图
plt.show()
K=3
lossrecord=[]
#改进:进行n轮迭代(这里我们设为100轮),找出其中评价最好的一轮作为最终结果
for i in range(100):

clusterResult=kmeansClassfier(data,K)
clustermat,centCluster=clusterResult
loss=lossKmeans(clustermat,centCluster)
lossrecord.append([loss,clustermat,centCluster])
minloss=lossrecord[0][0]
index=0
for i in range(1,len(lossrecord)):
print(lossrecord[i][0])
if(lossrecord[i][0]<minloss):
minloss=lossrecord[i][0]
index=i

print('loss最小值为:', index)
clustermat=lossrecord[index][1]
classes = clustermat.groupby(by=clustermat.index)
plt.figure(figsize=(8,8))
for i in range(K):
plt.scatter(data[classes.get_group(i).values][:, 0], data[classes.get_group(i).values][:, 1])
plt.show()

经过改进,我们的粗糙的算法实验效果基本达标。不会出现上述的错误聚类情况了。

参考资料:
https://wizardforcel.gitbooks.io/dm-algo-top10/content/k-means.html

https://blog.csdn.net/u013719780/article/details/51755124

第三章 决策树

ID3

C4.5

CART

第四章 SVM算法

第五章 贝叶斯分类器

第六章 基于浅层神经网络的分类器