阅读 39

关于kNN、kMeans、Apriori算法小结

趁着准备即将到来的笔试,也为了回顾一下这一星期来所学的三个机器学习算法,觉得还是重新理一下思路,好理解一下这几个算法。
复制代码

kNN算法

即k-近邻算法,属监督学习。

概述

  • 优点:精度高,对异常值不敏感,无数据输入假定(其实还是没有很理解优点体现在什么方面
  • 缺点:复杂度高(时间复杂度、空间复杂度)
  • 适用数据范围:数值型和标称型
  • 原理:
    • 对给定的数据集,提取出特征值和标签分别存放
    • 输入新数据
    • 计算与给定数据集的距离
    • 排序
    • 选取距离最近(即最相似)的前k个数据的标签
    • 统计所有出现的标签被提取次数
    • 选取提取次数最多的标签分类作为新数据的分类

详细步骤

导入数据

即处理输出格式


import numpy as np

def getDataSet(filename):
    dataSet = np.loadtxt(filename,delimiter=',',usecols=(0,1,2,3))
    #获取特征值
    #delimiter为分割符,需要查看所有获取的数据集里面的内容
    #usecols为指定获取的列
    #np.loadtxt()得到的矩阵为float类型
    #以下获取数据集中的分类标签
    arrayLines = open(filename).readlines()#打开文件并获取所有行
    labelsVector = [] #空列表用以存储标签
    for line in arrayLines:
        line = line.strip().split(',')  #strip用以消除回车,split(',')用以分割行
        labelsVector.append(line[-1])   #标签存在于最后一列,改语句将最后一列输入到列表
        
    return dataSet,labelsVector
复制代码
分类器(kNN主算法)

#辅助函数:欧式距离
def distEuro(vecA,vecB):
    return np.power(np.sum(np.power(vecA-vecB),2),0.5)

#kNN主算法函数
def classify(inX,labels,dataSet,k):
    #参数分别为:
    #inX:输入向量
    #labels:标签向量:所有数据的分类
    #dataSet:数据集
    #k:指定获取距离最近的数据的标签的数量
    
    m = dataSet.shape[0] #获取数据集的行数
    diffMat = distEuro(np.tile(inX,(m,1)),dataSet) #距离矩阵
    #排序并获得索引
    sortedDist = diffMat.argsort()  #得到diffMat中从小到大排好序的索引值
    labelCount = {} # 以键值对形式存储所提取标签及其出现次数
    for i in range(k):
        label = labels[sortedDist[i]]  #提取标签
        labelCount[label] = labelCount.get(label,0) + 1
        #也可:labelCount[label] = labelCount.setdefault(label,0) + 1
        #表示标签已存在是加一,不存在时将标签存入字典设置初始值为0再加一
    sortedCount = sorted(labelCount.item(),key=operator.itemgetter(1),reverse=True)
    #reverse=True表示降序排序
    #key=operator.itemgetter(0)表示按键排序
    #key=operator.itemgetter(1)表示按值排序
    
    return sotedCount[0][0] #返回标签
    
复制代码
归一化

数据差值大的数据严重影响计算结果,将数值归一化(即取值范围在0-1之间),可以有效减小影响


def autoNorm(dataSet):
    dmin = dataSet.min(0)
    dmax = dataSet.max(0)
    ranges = dmax-dmin
    m = dataSet.shape[0] #获取行数
    minMat = np.tile(dmin,(m,1))  #将dmin扩充为于数据集相同行数的矩阵
    rangeMat = np.tile(ranges,(m,1)) #将取值向量扩充为与数据集相同行数的矩阵
    normSet = (dataSet-minMat)/ranges #减去最小值,除以取值范围可得到归一化数组
    
    return normSet,ranges,dmin #返回归一化矩阵,范围,最小值
复制代码

测试和预测函数先略过。注意点位,对于处理过的数据集,采用随机分配测试集和训练集,对于未处理可以采用前百分之十作为测试集

kMeans

无监督学习,将相似的对象归到一个簇中

概述

  • 优点
  • 缺点
  • 适用数据范围
  • 原理:
    • 随机选取k个簇质心
    • 当标签变量为真(改变簇分配):
      • 遍历所有点
        • 遍历所有簇 -计算与簇质心的距离 将点分配到距离最近的簇质心

详细步骤

获取数据集(iris.data为例)

def getDataSet(filename):
    dataSet = np.loadtxt(filename,delimiter=',',usecols=(0,1,2,3))
    return dataSet
复制代码
获取簇质心

def randCent(dataSet,k):
    m = np.shape(dataSet)[1] #获取列数
    centroid = np.zeros((k,m)) #生成0矩阵用以存放簇质心
    for i in range(m):  #按列生成
        dmin = np.min(dataSet[:,i])
        dmax = np.max(dataSet[:,i])
        centroid[:,i] = dmin + np.random.random(k)*(dmax-dmin)
    return cendroid
复制代码
kMeans主算法

def kMeans(dataSet,k):
    m = np.shape(dataSet)[0]  #获取行数
    centroid = randCent(dataSet,k)  #获取簇质心
    cluster = np.zeros((m,2))  #存放簇质心索引和平凡误差
    label = True
    while label:
        label = False
        for i in range(m):
            dmin = np.inf #初始距离无穷大
            index = -1
            for j in range(k):
                distance = dist(dataSet[i,:],centroid[j,:]) #调用辅助函数计算距离
                if distance < dmin:
                    dmin = distance
                    index = j
            if index != cluster[i,0]:  #判断是否改变簇质心
                label = True
                cluster[i,:] = index,dmin
        for i in range(k): #更新簇质心
            pst = dataSet[np.nonzero(cluster[:,0]==i)[0]]
            centroid[i,:] = np.mean(pts,axis=0)
    return centroid,cluster
    
复制代码

二分kMeans

概述

  • 改进kMeans可能收敛到局部最小值的缺点,二分kMeans收敛到全局最小值
  • 原理:
    • 将所有点视为一个簇
    • 当簇个数小于k:
      • 遍历所有簇
        • 计算划分后降低的SSE
      • 划分SSE降低幅度最大的簇

二分kMeans主函数


def dichKmeans(dataSet,k,dist):
    m = np.shape(dataSet)[0]
    cluster = np.zeros((m,2))
    centroid = np.mean(dataSet,axis=0).tolist()[0]
    centList = [centroid]
    for i in range(m):
        cluster[i,1] = dist(np.array(centroid),dataSet[i,:])
    while (len(centList) < k):
        lowestSSE = np.inf #初始SSE设置为无穷大
        for i in range(len(centList)): #遍历每一个簇计算划分后的SSE
            curSet = dataSet(np.nonzero(cluster[:,0]==i)[0],:) #获取当前簇索引的所有数据
            curCent,curCluster = kMeans(curSet,2) #将当前簇一分为二
            curSSE = np.sum(curCluster[:,1]) #新划分出来的两个簇的SSE
            SSE = np.sum(cluster[np.nonzero(cluster[:,i] != i),1]) + curSSE #计算总SSE
            if SSE < lowestSSE:
                bestIndex = i
                bestCent = curCent
                bestCluster = curCluster.copy()
                lowestSSE = curSSE
        #数组过滤器,修改簇编号
        bestCluster[np.nonzero(bestCluster[:,0]==1)[0],0] = len(centList)
        bestCluster[np.nonzero(bestCluster[:,0]==0)[0],0] = bestIndex
        centList[bestIndex] = bestCent[0,:]
        centLIst.append(bestCent[1,:])
        #更新簇特征值
        cluster[np.nonzero(cluster[:,0) == bestIndex)[0],:] = bestCluster
    return np.array(centList),cluster
复制代码

apriori算法

概述

  • 优点:易编码实现
  • 缺点:在大数据集上可能较慢
  • 适用数据类型:数值型或者标称型数据
  • 相关概念
    • 支持度
    • 可信度
    • 频繁项集
    • 关联规则
  • 原理:
    • 某个项集频繁->子集频繁
    • 某个项集非频繁->超集非频繁
  • 步骤
  1. 生成频繁项集
    • 生成元素为包含一个元素的列表的列表,作为待选集
    • 计算支持度,筛选出频繁集
    • 生成元素为包含两个元素的列表的列表,作为待选集
    • 计算支持度,筛选出频繁集
    • 重复直至包含x和元素的待选集为空
  2. 挖掘关联规则
    • 遍历包含一个元素的列表,到包含x-1个元素的列表
      • 遍历当前列表的每一个频繁集
        • 将频繁集化为包含只包含一个元素的集合的列表
        • 当前频繁集内元素大于1时:
          • 划分频繁集
        • 计算置信度,将满足最小置信度的规则存入列表
关注下面的标签,发现更多相似文章
评论