首页 > 代码库 > Python/matlab实现KNN算法

Python/matlab实现KNN算法

Python
算法伪码:
对未知类别属性的数据集中的每个点依次执行以下操作:
1)计算已知类别数据集中的点与当前点之间的距离;
2)按照距离递增次序排序;
3)选取与当前点距离最小的k个点;
4)确定前k个点所在类别的出现频率;
5)返回前k个点出现频率最高的类别作为当前点的预测分类。
 
欧氏距离计算:
(1)二维平面上两点xA(x1,y1)与xB(x2,y2)间的欧氏距离:
(2)三维空间两点xA(x1,y1,z1)与xB(x2,y2,z2)间的欧氏距离:
(3)两个n维向量xA(x11,x12,…,x1n)与 xB(x21,x22,…,x2n)间的欧氏距离:
 
算法实现如下:
1、评价指标
def createDataSet():
    group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = [‘A‘,‘A‘,‘B‘,‘B‘]
    return group, labels
2、knn核心算法
#inX    要检测的数据
#dataSet  数据集
#labels    结果集
#k      要对比的长度
def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]                #计算有多少行
    # tile(inX, (dataSetSize,1))生成对应inX维度的矩阵,方便做差
    diffMat = tile(inX, (dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2                          #差求平方
    sqDistances = sqDiffMat.sum(axis=1)            # axis=0, 表示列 axis=1, 表示行。
    distances = sqDistances**0.5                  #开方
    sortedDistIndicies = distances.argsort()      #argsort()排序,求下标
    classCount={}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]  #通过下标索引分类
        # 通过构造字典,记录分类频数
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
        # 对字段按值排序(从大到小)
        sortedClassCount = sorted(classCount.items(),key=lambda classCount:classCount[1], reverse=True)
    return sortedClassCount[0][0]
 
3、测试类
#测试
if __name__ == "__main__" :
    dataset = array([[1.0, 1.1], [1.0, 1.0], [0.0, 0.0], [0.0, 0.1]])
    labels = [‘A‘, ‘A‘, ‘B‘, ‘B‘]
    X = [1.2, 1.1]
    Y = [0.1, 0.1]
    k = 3
    labelX =  classify0(X,dataset,labels,k)
    labelY =  classify0(Y,dataset,labels,k)
    print ("Your input is:", X, "and classified to class: ", labelX)
    print ("Your input is:", Y, "and classified to class: ", labelY )
结果:
Your input is: [1.2, 1.1] and classified to class:  A
Your input is: [0.1, 0.1] and classified to class:  B
4、注意
knn算法的开销很大,因为要计算每个样本点到其他所有点的距离.
knn算法的距离一般要根据实际样本点的情况来选取.
knn算法的距离阈值要根据样本的分散集中程度来选取.经验一般选取样本点集合的均方差.
 
matlab
5、任性matlab
没错,matlab就是这么任性只需要一行,其他都是读取数据
 
train_data=http://www.mamicode.com/load(‘sample_feature.txt‘);
train_label=load(‘train_label.txt‘);
test_data=http://www.mamicode.com/load(‘features.txt‘);
k=knnclassify(test_data,train_data,train_label,3,‘cosine‘,‘random‘);
 
train_data保存的是训练样本特征,要求是最能代表本类别的,不一定多,当然不能太少;
train_label保存的是样本标号,如0,1,2等等,随便设置,只有能区分就行,具体格式可以为:
test_data测试文件保存的是测试数据的特征;
 
关键函数介绍:
knnclassify是利用最近邻进行分类的分类器;
 
函数调用形式:
1.CLASS = KNNCLASSIFY(SAMPLE,TRAINING,GROUP) 
标号和训练数据必须有相同的行数;训练数据和测试数据必须有相同的列;函数对于无效值或者空值会作为丢失值或者忽略这一行。
2.CLASS = KNNCLASSIFY(SAMPLE,TRAINING,GROUP,K)
此函数允许你设置距离矩阵形式,如:
              ‘euclidean‘    欧氏距离,默认的
              ‘cityblock‘    绝对差的和
              ‘cosine‘     角度距离
              ‘correlation‘ 相关距离
              ‘Hamming‘      汉明距离
3.CLASS =KNNCLASSIFY(SAMPLE,TRAINING,GROUP,K,DISTANCE,RULE)
本函数允许你选择如何对样本进行分类,如你可以选择:
               ‘nearest‘  最近的K个的最多数
              ‘random‘    随机的最多数
              ‘consensus‘ 投票法,默认的
 
而我选择的函数形式是:
k=knnclassify(test_data,train_data,train_label,3,‘cosine‘,‘random‘);
 
技术分享

Python/matlab实现KNN算法