RBF Network

前面的一篇SVM中，最后的分割函数：

使用高斯核函数方式把数据维度扩展到无限维度进而得到一条粗壮的分界线。仔细看一下这个分割函数，其实就是一些Gaussian函数的线性组合，y就是增长的方向。
Gaussian函数还有另外一个叫法——径向基函数，这是因为这个base function的结果只和计算这个x和中心点xn的距离有关，与其他的无关。
从其他方面来看SVM，先构造一个函数：
g(x) = y_nexp(-γ|x - x_n|^2)指数求出来的其实就是x点和中心点的相似度，相似度越高，那么=晚y这个方向投票的票数就会越多。不同的g(x)有不同的权重，他们的线性组合就成了SVM，g(x)函数称为是radial function。所以Gaussian SVM就是把一些radial function联合起来做linear aggregation。

RBF Network就是SVM的延伸，目的就是找到所有radial hypotheses的linear aggregation，得到更好的网络模型。

可以看到这两种网络其实很类似，Neural Network的隐藏层是权值和数据做內积非线性转换再uniform的组合得到最后的输出，而对于RBF Network隐藏层是求高斯距离在做aggregation的方法。比较大的不同点就在于hidden层的不同了。

β就是每一个radial function的权值，μ就是中心点，m为中心点的个数，主要的，对比一下之前的SVM，β就是αy，μ就是支持向量。由于是一个分类问题，所以最后的output function就是sign函数了。

之前讲过，一个核函数不是随便乱选的，要满足两个条件：对称，半正定。对于SVM里面的核函数，其实ius把当前的数据提升到某一个很高很高的维度，然后做切片把数据分出来，polynomial function也是一样的，只不过是有限维度的。而RBF其实就是在当前的空间做相似度处理，而那些kernel其实就是转换到z空间来计算核函数以表征两个向量的相似度。所以RBF和kernel都是衡量相似度的方式。虽然SVM和RBF Network都很相似，甚至可以说最后的决策函数基本一致的，但是他们的学习过程是很不一样的，一个是直接x空间，一个是转换到z空间。

衡量相似性并不止一种RBF方法，余弦相似度这些也可以衡量向量之间的相似度。

回过头来思考一下SVM，其实支持向量机就是先通过凸优化的一些方法找到有投票权利的点，之后给出相应的权值，最后决策就是这些有投票权利的点进行决策；对于其他线性模型，其实主要的不同就是他们每一个点都有投票的权利，这就导致很远的点都会干扰到边界。而RBF Network事实上做的事情和SVM有点像，因为RBF函数是指数增长，如果这个点很远的话会非常小，近乎就是0了，所以也起到了弱化远的点投票权，强化近的点投票权的能力。

RBF Network Learning

RBF Network的决策函数：

μ就是中心点，中心点是自己选择的。有一种选择中心点的方法，就是所有的点都作为中心点，那么每一个样本对于预测都会有影响，β就是影响的程度。如果影响的程度都是一样的，那么就是1了，β = 1*y，最后相乘做uniform aggregation之后sign得到结果。这种我们称为full RBF Network。

这个时候，full RBF Network就可以表示为：

这是一个指数函数，距离越远，那么衰减的就越快，x与中心点的距离越近那么就越大，距离越远就越小。也就是说，如果我们的样本点是N个，那么起了关键作用的一般就是最近的那个点而已，当然，不一定是最近的一个点，可以是最近的K个点，用这k个点来代替N个点，当前的点周围最近的k个点哪个类别最多，那么这个当前这个点就是属于哪个类别的。这种算法就叫K近邻算法。

k nearest neighbor通常比nearest neighbor model效果更好，计算量上也比full RBF Network要简单一些。值得一提的是，k nearest neighbor与full RBF Network都是比较“偷懒”的方法。因为它们在训练模型的时候比较简单，没有太多的运算，但是在测试的时候却要花费更多的力气，甚至可以说是几乎没有运算在里面，只需要做一些简单的数据处理即可，找出最相近的中心点，计算相对复杂一些。
如果是做回归问题，我们就只需要去掉output：

很明显，这样就是一个线性回归的问题了，每一个RBF 其实可以看做就是一个矩阵比如第一个元素x1，那么经过RBF的转换之后：
z_1 = [RBF(x_1,x_1), RBF(x_1, x_2), RBF(x_1,x_3),RBF(x_1,x_3)...RBF(x_1,x_N)]
那么Z就是z的按列排序了，按照线性回归的解公式：
β = (Z^TZ)^{-1}Z^Ty
上述矩阵Z是一个方阵，大小是N，有多少个中心点那么就有多少个N。如果每一个x都是不一样的，那么这个矩阵就是可以逆的矩阵了，毕竟x是训练数据，一样的就没有意义了。

化简一下：
β = Z^{-1}y
我们以x1为例子，那么解就是：

这个结果对于我们来说非常奇怪，如果这样的话那么对于所有的x都有：
g_{RBF}(x_n) = y_n所有Ein = 0，这样对于机器学习来说并不是一个好事情，因为这样很大概率会出现过拟合。当然，某些情况下还是很有用的，比如函数拟合或者是做autoencode。

为了避免过拟合，使用ridge regression的方法：


L2范式正则化。Z矩阵是由一系列Gaussian函数组成，每个Gaussian函数计算的是两个样本之间的distance similarity。这里的Z与之前我们介绍的Gaussian SVM中的kernel K是一致的。当时使用ridge regression得到的解：

比较一下kernel ridgeregression与regularized full RBF Network的β解，形式上相似但不完全相同。这是因为regularization不一样，在kernel ridgeregression中，是对无限多维的特征转换做regularization，而在regularized full RBF Network中，是对有限维（N维度）的特征转换做regularization。因此，两者的公式解有细微差别。

对于解决过拟合，还有另外的一种方法，可以选择K个具有代表性的点来代表这N个点，这样减少了中间点减少了权重的数量，VC维就减少了，可以起到regularization的作用。

原本的问题是求解中心点μ，β权重，现在β可以通过回归求解，那么只需要求μ了。

K Mean Algorithm

选择代表的原因，就是因为这些点有很高的相似性，所以可以使用一个中心点来代表，从所有的点中选择几个有代表性的点。

首先聚类算法是一种非监督的算法，不需要有label。需要确定的一般就是两个变量，分群值Sm，没一个分类可以表示为S1,S2,S3,S4...Sm，另一个就是中心值μm，μ1，μ2，μ3，μ4...μm，每一个分群就对应着中心，要求的就是这个中心。对于这类问题的优化，就可以使用square error function了。优化的步骤也是一样，求导，梯度下降或者梯度为0求最优值解。

刚刚也说过了，既然是衰减的形式，那么只需要取最大的就好了，最大也就意味着这需要求距离最近的即可。所以，表达式里面只有属于这个类别的数据求error。
最后就是求导做优化了：

两个变量组合的优化问题，通常的方法就是对这两个变量分别求。仔细观察一下这两个变量，可以发现，只要确定了μ，就可以确定S；或者只要确定了S，求个平均也可以得到μ。所以假设μ已经是固定的了，那么可以依次迭代x，和哪个μ的距离最小就属于哪个类别。

如果类别S是确定的，那么目标就是找到对应的μ中心点，显然这个，求个导的事，梯度下降就可以解决了。

所以这就成了一个鸡生蛋蛋生鸡的问题，所以一般一开始我们会选择随机的几个点作为中心μ，然后按照上诉步骤优化。

优化有结果吗？

这个优化的过程好像有些不一样，求导等于0应该是直接求出了最优的解，linear regression就是这个道理，但是为什么要一直这样迭代呢？这是因为求出来的这个μ并不是一个全局的μ，只是在当前对于每一个群S的一个最优，但是这个S并不是最优的，之前也说了：这个S和μ是互相牵制的，鸡生蛋蛋生鸡的问题，S可以得到μ，μ也可以得到S。所以整个过程通俗点就是通过μ求局部最优的S，通过S有球局部的最优μ，不断的迭代，慢慢的跑到全局。但是也没有可以跑到局部呢？这个是有可能的，这于初值有关，所以Kmean均值算法也是一个初值敏感的算法。对于局部这个问题，有一种解法就是可以合并最近的几个质心。事实上如果中心比较小，比如3个这样，一般都不会有局部出现，因为\sum_{m=1}^M(x_n - μ_m)^2不会这么的弯曲。
停止是一定的，因为无论是通过S优化μ还是μ优化S都朝Ein = 0为目的，如果Ein增加了是不会继续的，所以最后一定会到达一个平衡点。

The process of the RBF Network

既然中心有其他算法可以帮忙解决了，那么整个算法也就清晰了：

求解优化的过程中，可以使用validation来求解最优的λ和M。

RBF Network and KMeans in action

k值的大小和初始位置的不同都会影响聚类的结果。
把这些机构k均值使用到RBF里面：

对于正则化也有不同的影响。

coding

KMeans

接下来就是代码实现KMeans算法了。KMeans算法其实很简单，首先随机得到几个中心点，根据中心点预测做聚类算法即可。

def loadDataSet():
    '''loading data......'''
    data = dataSet.load_iris()
    dataset = data.data
    target = data.target
    PCA = pca.PCA(n_components=2)
    dataset = PCA.fit_transform(dataset)
    return np.mat(dataset), np.mat(target)
    pass

加载数据，iris数据集进行降维操作便于可视化。

def distEclud(vecA, vecB):
    '''calculate the distance from vecA to vecB'''
    return np.sqrt(np.sum(np.power(vecA - vecB, 2)))
    pass

def randCent(dataSet, k):
    '''create the center'''
    n = np.shape(dataSet)[1]
    centroids = np.mat(np.zeros((k, n)))
    for j in range(n):
        minJ = np.min(dataSet[:, j])
        rangeJ = float(max(dataSet[:, j]) - minJ)
        centroids[:, j] = minJ + rangeJ * np.random.rand(k, 1)
    return centroids

计算距离，随机选择中心点。随机选择中心点这里是先计算了每一个维度的范围，之后在这个范围里面随机选择。

def KMeans(dataSet, k, distMeas = tool.distEclud, createCent = tool.randCent):
    '''KMeans Algorithm is running......'''
    m = np.shape(dataSet)[0]
    clusterAssment = np.mat(np.zeros((m, 2)))
    centroids = createCent(dataSet, k)
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(m):
            minDist = np.inf
            minIndex = -1
            for j in range(k):
                distJI = distMeas(centroids[j,:], dataSet[i,:])
                if distJI < minDist:
                    minDist = distJI
                    minIndex = j
            if clusterAssment[i, 0] != minIndex:
                clusterChanged = True
            clusterAssment[i, :] = minIndex, minDist**2
        for cent in range(k):
            ptsInClust = dataSet[np.nonzero(clusterAssment[:, 0].A == cent)[0]]
            centroids[cent, :] = np.mean(ptsInClust, axis=0)
    dataFrame = pd.DataFrame(data=np.hstack((dataSet, clusterAssment[:,0])))
    return dataFrame, centroids

选择和calculate distance的算法都是动态的方式，便于以后的改进。整个过程也比较简单，离哪个近就属于哪个类别。

RBF Network

①获取中心点

_,center = kMeans.KMeans(np.mat(x_train), k)

刚刚写好的KMeans就是这个作用。

②计算β值

beta = rbf(x_train, center, y_train, gama=gamma, lamda=lamda)

rbf函数的实现：

def rbf(x_train, center, y_train, gama = 0.001, lamda = 0.01):
    M = center.shape[0]
    N = len(x_train)
    Z = np.zeros((M, N))
    for i in range(M):
        for j in range(N):
            Z[i][j] = Gaussian(x_train[j], center[i], gama)
    I1 = np.eye(N, k = 0)
    beta = np.linalg.inv(np.dot(Z.T, Z) + lamda * I1)
    beta = np.dot(beta, Z.T)
    y_train = np.mat(y_train)
    beta = np.dot(y_train, beta)
    return beta
    pass

def Gaussian(vecA, vecB, gama):
    x_x = np.abs(np.sum(vecA - vecB))
    x_x_2 = np.power(x_x, 2)
    return np.exp(-1.0 * gama * x_x_2)
    pass

首先是计算Z矩阵，就是φ(x)的矩阵。其实就是和上面步骤一模一样的，使用的是线性回归，β = (Z^TZ + λI)^{-1}Z^Ty使用直接就可以算，要是逻辑回归也是一样。

③预测

def predict(beta, x_train, center, gama):
    result = []
    for x in x_train:
        x = np.mat(x)
        sum = 0
        for i, vecB in enumerate(center):
            sum += beta[0,i]*Gaussian(x, vecB, gama)
        result.append(sum)
    return result
    pass

为了方便调用，整合成一个函数：

def RBF(y_test, x_test, y_train, x_train, gamma = 0.001, lamda = 0.01, k = 4):
    Again = True
    while Again == True:
        _,center = kMeans.KMeans(np.mat(x_train), k)
        beta = rbf(x_train, center, y_train, gama=gamma, lamda=lamda)
        Again = False
        for i in range(beta.shape[1]):
            if np.isnan(beta[0, i]):
                Again = True
    result = predict(beta, x_train, center, gamma)
    for i in range(len(result)):
        if result[i] > 0:
            result[i] = 1
        else:
            result[i] = -1
    posibility = 0
    for i in range(len(result)):
        if result[i] == y_train[i]:
            posibility += 1
    train_accuracy = posibility/len(result)
    result = predict(beta, x_test, center, gamma)

    for i in range(len(result)):
        if result[i] > 0:
            result[i] = 1
        else:
            result[i] = -1
    posibility = 0
    for i in range(len(result)):
        if result[i] == y_test[i]:
            posibility += 1
    test_accuracy = posibility/len(result)
    return train_accuracy, test_accuracy

可以计算不同gamma，lamda，k的影响。

④获取数据

def load_data():
    data = dataset.load_breast_cancer().data
    target = dataset.load_breast_cancer().target
    for i in range(len(target)):
        if target[i] == 0:
            target[i] = -1
    x_train, x_test, y_train, y_test = train_test_split(data, target, random_state=42, shuffle=True, test_size=0.4)
    return x_train, x_test, y_train, y_test
    pass

⑤启动函数

if __name__ == '__main__':
    x_train, x_test, y_train, y_test = load_data()
    gamma = [1,0.1,0.01,0.001,0.0001]
    lamda = gamma
    train_accuracy = []
    test_accutacy = []
    c = ['red', 'blue', 'orange', 'green', 'yellow', 'black']
    for n, i in enumerate(gamma):
        for j in lamda:
            train, text = RBF(x_test=x_test, y_test=y_test, x_train=x_train, y_train=y_train, gamma=i, lamda=j)
            print('gama : ',i, ' lamda : ', j, ' train_accuracy : ', train, ' text_accuray : ', text)
            train_accuracy.append(train)
            test_accutacy.append(text)
        plt.plot(lamda, train_accuracy, c = c[n], label = 'gamma:'+str(i) + ' (train)')
        plt.plot(lamda, test_accutacy, c = c[n], linestyle='--', label = 'gamma:'+str(i) + ' (test)')
        plt.xlabel('lambda')
        plt.ylabel('accuracy')
        plt.legend(loc = 'upper right')
        train_accuracy = []
        test_accutacy = []
    plt.show()

    for n, i in enumerate(lamda):
        for j in gamma:
            train, text = RBF(x_test=x_test, y_test=y_test, x_train=x_train, y_train=y_train, gamma=j, lamda=i)
            print('lamda : ',i, ' gama : ', j, ' train_accuracy : ', train, ' text_accuray : ', text)
            train_accuracy.append(train)
            test_accutacy.append(text)
        plt.plot(gamma, train_accuracy, c = c[n], label = 'lamda:'+str(i) + ' (train)')
        plt.plot(gamma, test_accutacy, c = c[n], linestyle='--', label = 'lamda:'+str(i) + ' (test)')
        plt.xlabel('gamma')
        plt.ylabel('accuracy')
        plt.legend(loc = 'upper right')
        train_accuracy = []
        test_accutacy = []
    plt.show()

    ks = [2,3,4,5,6,7]
    train_accuracy = []
    test_accutacy = []
    for i in range(6):
        for n, i in enumerate(ks):
            train, text = RBF(x_test=x_test, y_test=y_test, x_train=x_train, y_train=y_train, gamma=0.0001, lamda=0.01, k=i)
            print('k == ' + str(i))
            train_accuracy.append(train)
            test_accutacy.append(text)
        plt.plot(ks, train_accuracy, c = c[n], label = 'train')
        plt.plot(ks, test_accutacy, c = c[n], linestyle='--', label = 'test')
        plt.xlabel('the number of k')
        plt.ylabel('accuracy')
        plt.legend(loc = 'upper left')
        plt.show()
        train_accuracy = []
        test_accutacy = []
    pass

效果的讨论

在运行函数得到结果后进行分析。

①当γ固定了，看看lamda变化对于结果的影响。

其实还是很正常的，随着gamma的减少，准确率慢慢提上去了，虚线的测试数据，直线是准确率。Gaussian函数：g(x) = exp(-γ|x_n - μ|^2)γ越小，就相当于σ变大，高斯函数的标准差变大那么这个函数就会变的更加平滑，泛化能力会很强。其实就是regularization的过程。
观察上图是可以得到λ对于整体的影响不会太大。基本是平缓的。

②当λ固定了，看看γ变化对于结果的影响。

γ越小效果越好，但是如果γ非常小，那么λ对于模型的影响几乎是没有影响。

③对于k的数量和准确率的讨论

效果不太稳定，我多做了几次。

效果非常非常不稳定，我之前怀疑是线性回归的解不稳定的缘故，之前学习到病态矩阵，也就是近似奇异矩阵的矩阵，而regularization L2正则化就是为了使得病态矩阵转换成正常矩阵，所以增大了λ，显然并没有什么卵用。虽然整体效果不错。上面的结果就已经是λ增大的结果了。

所以最后还有两个问题没有解决，一个就是λ为什么对于模型的影响很很小，另一个上面没有提到，为什么测试数据的准确率会大于训练数据的准确率？这还打的明显，不知道是不是没有做交叉验证的结果，因为懒。。。。之前看到的解释是：

如果程序很好的实现了模型，那么就是模型不适合你的数据，因为这表明存在如下问题：每次训练，都使得训练之后的模型对测试的 1折效果很好，而对用于训练的9折效果惨淡，也就是模型落入了局部极值点而非全局极值点。这很有可能是模型在具体数据下的失效问题。

但是这个问题已经重复过了很多次，一直在使用test_train_split区分，同时也有shuffle。事实上在γ比较小的时候，测试数据就超过了训练数据的准确率，上面γ的变化可以看到。

最后附上GitHub代码：https://github.com/GreenArrow2017/MachineLearning/tree/master/MachineLearning/RBFNetwork