精华内容
下载资源
问答
  • 讨论了求解非线性方程重根问题,针对此时Moore区间牛顿法不再适用,以及Hansen改进...证明了其局部平方收敛的性质,给出了数值算例。验证了新算法比Hansen改进的区间牛顿法具有更快的收敛速度,且算法是有效和可靠的。
  • 一元方程求根

    2018-11-22 09:35:41
    已知f(x)=0f(x)=0f(x)=0,求x. 1.二分法求根 要求:f(x)f(x)f(x)连续,且在[a,b]上有...优点:具有平方收敛的速度 缺点: 重根情形下为局部线性收敛 计算量大(除了要计算函数值还要计算导数值) 选取的初始...

    已知f(x)=0f(x)=0,求x.

    1.二分法求根

    要求:f(x)f(x)连续,且在[a,b]上有根
    优点:简单可靠
    缺点:不能求复根和偶重根
    解决:选用一个合适的步长h对[a,b]进行扫描搜索,当发现哪个子区间有根时再用二分法求其中之根。
    在这里插入图片描述
    在这里插入图片描述

    2.牛顿迭代法

    优点:具有平方收敛的速度
    缺点:

    • 重根情形下为局部线性收敛
    • 计算量大(除了要计算函数值还要计算导数值)
    • 选取的初始值要靠近精确解(解决:先用二分法求出足够精度的x0x_0再用牛顿法迭代到收敛为止)
      在这里插入图片描述

    补充知识

    1、泰勒公式

    将一个在x=x0x=x_0处具有n阶导数的函数f(x)f(x)利用关于(xx0)(x-x_0)的n次多项式来逼近函数的方法。
    f(x)=i=0nf(i)(x0)i!(xx0)i+Rn(x)f(x)=\sum_{i=0}^n\frac{f^{(i)}(x_0)}{i!}(x-x_0)^i+R_n(x)
    其中f(i)(x)f^{(i)}(x)代表xxii阶导数,剩余的Rn(x)R_n(x)是泰勒公式的余项,是(xx0)n(x-x_0)^n的高阶无穷小。

    2、牛顿法对方程重根的处理

    • 已知重根的重数m(m>1),利用m构造新的迭代公式
      xk+1=xkmf(xk)f(xk)(k=0,1,...)x_{k+1}=x_k-m\frac{f(x_k)}{f^{'}(x_k)}\quad (k=0,1,...)
    • 未知重根的重数,新迭代公式是
      xk+1=xkf(xk)f(xk)[f(xk)]2f(xk)f(xk)(k=0,1,...)x_{k+1}=x_k-\frac{f(x_k)f^{'}(x_k)}{[f^{'}(x_k)]^2-f(x_k)f^{''}(x_k)}\quad (k=0,1,...)
      缺点:需要求ff的2阶导数,计算量大,应用前提是f(x)f(x)要简单。
    展开全文
  • 二分K-means聚类,K-Means改进

    千次阅读 2015-12-09 18:35:18
    由于K-means 有可能会收敛局部最优值,而无法收敛到全局最优值,影响聚类性能 一种用于度量聚类效果的指标是SSE(Sum of Squared Error,误差平方和),对应予 clusterAssment第二列 此算法的思想是,为克服K-均值...

    由于K-means 有可能会收敛到局部最优值,而无法收敛到全局最优值,影响聚类性能

    一种用于度量聚类效果的指标是SSE(Sum of Squared Error,误差平方和),对应予 clusterAssment第二列

    此算法的思想是,为克服K-均值算法收敛于局部最小值,我们使用二分K-均值:先将所有点作为一个簇,然后将该簇一分为二。之后选择其中一个簇继续进行划分,选择哪一个簇进行划分取决于是否可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复,直到得到用户指定的簇数目为止

    会用到我写的另一篇http://blog.csdn.net/skyonefly/article/details/50235735 ,[R语言实现K-Means算法数据集iris]

    <span style="font-family:Comic Sans MS;font-size:14px;">#引入kmeans.r文件,以便调用其中自定义的函数
    #详细见http://blog.csdn.net/skyonefly/article/details/50235735
    source("E:/R programmer/kmeans.r")
    #二分K-均值聚类算法
    biKmeans <- function(dataSet,k,distEnclud){
      m = nrow(dataSet)
      #创建一个空矩阵
      clusterAssment = matrix(data = 1,nrow = m,ncol = 2,byrow = FALSE,dimnames = list( NULL, c("label","SSE")))
      #创建一个初始簇
      centroids0 = apply(dataSet,2, mean)
      centList = rbind(NULL,centroids0)
      for(j in 1:m){
        clusterAssment[j,2] = distEnclud(dataSet[j,],centList)^2#欧几里得距离
      }
      while(nrow(centList) < k){
        lowestSSE = Inf#把SSE设置为无穷,来找最小值
        for(i in 1:nrow(centList)){
          ptsInCurrCluster = dataSet[which(clusterAssment[,1] == i),]
          output = kMeans(ptsInCurrCluster,2,distEnclud,randCent)
          centroidsMat = output$centroids
          splitClusterAss = output$clusterAssment
          sseSplit = sum(splitClusterAss[,2])
          sseNotSplit = sum(clusterAssment[which(clusterAssment[,1] != i),2])
          if(sseSplit + sseNotSplit < lowestSSE){
            bestCentToSplit = i
            bestNewCents = centroidsMat
            bestClustAss = splitClusterAss
            lowestSSE = sseSplit + sseNotSplit
          }
        }
        
        bestClustAss[which(bestClustAss[,1] == 2),1] = nrow(centList) + 1
        bestClustAss[which(bestClustAss[,1] == 1),1] = bestCentToSplit
       
        clusterAssment[which(clusterAssment[,1] == bestCentToSplit), ] = bestClustAss
        centList = centList[-bestCentToSplit,]
        centList = rbind(centList,bestNewCents)
      }
      
      results = list(clusterAssment = clusterAssment,centroids = centList)
      return (results)
    }
    
    start.time = proc.time()
    dataSet = loadData()
    output = biKmeans(dataSet,3,distEnclud)
    
    #绘制Sepal.Length,Sepal.Width 两列
    plot(dataSet[c("Sepal.Length","Sepal.Width")],col = output$clusterAssment[,1]) 
    points(output$centroids[,1],output$centroids[,2],col = 1:3,pch = 8,cex = 2)
    #绘制Petal.Length,Petal.Width 两列
    plot(dataSet[c("Petal.Length","Petal.Width")],col = output$clusterAssment[,1])
    points(output$centroids[,"Petal.Length"],output$centroids[,"Petal.Width"],col = 1:3,pch =8,cex =2)
    table(iris$Species,output$clusterAssment[,1])
    end.time = proc.time()</span>
    <span style="font-family:Comic Sans MS;font-size:14px;">#总的运行时间
    end.time - start.time</span>
    


    运行结果




    展开全文
  • 2015-09-21

    2015-09-21 23:10:46
    k-均值算法收敛但聚类效果较差的原因是,k-均值算法收敛到了局部最小值,而非全局最小值(局部最小值指结果还可以但并非最好结果,全局最小值是可能的最好结果)。 2.如何改进kmeans算法? 一种用于度量聚类效果...


    常用的欧氏距离kmeans方法的问题:

    1.       为什么常见的kmeans方法效果较差?

    k-均值算法收敛但聚类效果较差的原因是,k-均值算法收敛到了局部最小值,而非全局最小值(局部最小值指结果还可以但并非最好结果,全局最小值是可能的最好结果)。

    2.如何改进kmeans算法?

    一种用于度量聚类效果的指标是SSE(Sum of Squared Error,误差平方和)。SSE值越小表示数据点越接近于它们的质心,聚类效果也越好。因为对误差取了平方,因此更加重视那些远离中心的点。一种肯定可以降低SSE的方法是增加簇的个数,但这违背了聚类的目标。聚类的目标是在保持簇数目不变的情况下提高簇的质量。

    1.       如何提升簇的质量?

    一种方法是将具有最大SSE值的簇划分成两个簇。具体实现时可以将最大簇包含的点过滤出来并在这些点上运行k-means方法,其中k设为2.为了保持簇总数保持不变,可以将某两个簇进行合并。但是,很容易对二维数据上的聚类进行可视化,但是如果遇到40维的数据应该如何去做?

    有两种可以量化的方法:合并最近的质心,或者合并两个使SSE增幅最小的质心。第一种思路通过计算所有质心之间的距离,然后合并距离最近的两个点来实现。第二种方法需要合并两个簇然后计算总SSE值。必须在所有可能的两个簇上重复上述过程,直到找到合并最佳的两个簇为止。

    明日处理:

    1.      categorical data和k-means稳定性问题(暂缓,吃饭中间时间做这个事情吧,不能再耽误时间了)

    2.      看论文,我觉得明天还是先把k-means改进先实现了,然后categorical data可以回头看

    3.      Unsupervised learning这个方面分类的文章?暂且可以听一下劝告,去看下

    今日收获:

    1.      貌似倒库有点心得了

    2.      学会游泳了,使劲呱唧呱唧

    3.      思路问题被否定了,不过感觉很有成就感的事情就是我曾经用自己的思路说服了老师一下,不过这到底是一种什么样的思维方式呢?我到底应该怎么训练出来?A+B的方法不是创新,要想到什么是真正的创新,对A和B进行修改才是。大部分文章都是从新提出应用场景来的,我想这还是读文章太少造成的。其实不用担心也不用在乎别人是不是发了论文,要一篇高质量的文章才是最重要的,也许刚开始要求高才是真真正正的为自己好,不过也不用苛求自己为什么不是刚上来就能写文章的那种,毕竟我不是天才。冰冻三尺非一日之寒,这才第一次,第一千次跌倒第一千零一次还勇敢地站起来,这才是我,有韧性,敢坚持。踏踏实实做事,开开心心做人,与有思想人共事,从无字句处读书。

    展开全文
  • 二分K-均值聚类

    2019-03-21 11:30:08
    K-均值算法算法可以实现收敛,但是存在一个问题是,K-均值算法会收敛局部最优解而不是全局最优。 一种用于度量聚类效果的指标是SSE(sum of Squared Error,误差平方和)。SSE值越小表示数据点越接近它们的质心,...

    K-均值算法算法可以实现收敛,但是存在一个问题是,K-均值算法会收敛到局部最优解而不是全局最优。

    一种用于度量聚类效果的指标是SSE(sum of Squared Error,误差平方和)。SSE值越小表示数据点越接近它们的质心,聚类效果也就越好。应为误差取了平方,因此更加重视那些远离中心的点。一种肯定可以降低SSE值的方法是增加簇的个数,但这违背了聚类的目标。聚类的目标是在簇数目不变的情况下提高簇的质量。

    对K-均值进行改进的方案之一是对生成的簇进行后处理,一种方法是将具有最大SSE值的簇划分两个簇。

    二分K-均值算法

    概算发首先将所有点作为一个簇,然后将该簇一分为二。之后选择其中一个簇进行划分,选择哪一个簇进行划分取决于其划分结果是否可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复,直到得到用户指定的簇的数目为止。

    二分K-均值算法的伪代码形式如下:

    • 将所有点看成一个簇
    • 当簇数目小于k时:
      • 对每一个簇
        • 计算总误差
        • 在给定的簇上面进行K-均值划分(k=2)
        • 计算将该簇一分为二之后的总误差
      • 选择使得总误差最小的那个簇的进行划分

    代码:

    import numpy as np
    import matplotlib.pyplot as plt
    
    def loadDataSet(fileName):
        dataList = []
        with open(fileName) as fr:
            for line in fr.readlines():
                currentLine = line.strip().split('\t')
                floatLine = list(map(np.float, currentLine))
                dataList.append(floatLine)
        return np.array(dataList)
    
    
    def calcEcludDist(vecA, vecB):
        return np.sqrt(np.sum(np.power(vecA - vecB, 2)))
    
    
    def randCent(dataSet, k):
        n = np.shape(dataSet)[1]    #n: 特征数量
        centroids = np.zeros((k, n))  #centroids的维度(类别数, 特征数)
        for j in range(n):
            minJ = np.min(dataSet[:, j])
            rangeJ = float(np.max(dataSet[:, j]) - minJ)
            mean = (minJ + np.max(dataSet[:, j])) / 2
            centroids[:, j] = minJ + rangeJ * np.random.rand(k, 1).T
        return centroids
    
    
    def KMeans(dataSet, k, distMeans=calcEcludDist, createCent = randCent):
        m = np.shape(dataSet)[0]
        clusterAssment = np.array(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 = distMeans(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] == cent)[0]]
                centroids[cent, :] = np.mean(ptsInClust, axis=0)
        return centroids, clusterAssment
    
    
    def biKMeans(dataSet, k, distMeans = calcEcludDist):
        """
    
        :param dataSet:
        :param k: the number of expected classes
        :param distMeans: function that describes how to calculate distance
        :return:
        """
        global bestNewCents, bestCentToSplit, bestClustAss
        m = np.shape(dataSet)[0]  # m: the number of data set
        clusterAssment = np.array(np.zeros((m, 2))) # (类别,距离质心的距离平方)
        centroid0 = np.mean(dataSet, axis=0) # 选择均值作为最开始的质心
        centroidList = [centroid0]  # 质心向量
        for j in range(m):
            clusterAssment[j, 1] = distMeans(centroid0, dataSet[j, :]) ** 2 # 计算每个样本距离质心的距离平方
        while len(centroidList) < k:    # 如果当前的质心小于期望的质心数量(分类数量)
            lowestSSE = np.inf
            for i in range(len(centroidList)):
                ptsInCurrentCluster = dataSet[np.nonzero(clusterAssment[:, 0] == i)[0], :]  # 第i类的数据放入集合ptsInCurrentCluster
                newCentroids, splitClustAss = KMeans(ptsInCurrentCluster, 2, calcEcludDist) # 将第i类再分2类
                sseSplit = np.sum(splitClustAss[:, 1])  # 已分类数据的SSE总和
                sseNotSplit = np.sum(clusterAssment[np.nonzero(clusterAssment[:, 0] != i)[0], 1])   # 未分类数据的SSE总和
                print("sse split and not split: ", sseSplit, sseNotSplit)
                if sseSplit + sseNotSplit < lowestSSE:  # 如果SSE小于最小SSE,则说明应该对第i类数据再分类
                    bestCentToSplit = i
                    bestNewCents = newCentroids
                    bestClustAss = splitClustAss.copy()
                    lowestSSE = sseSplit + sseNotSplit
            bestClustAss[np.nonzero(bestClustAss[:, 0] == 1)[0], 0] = len(centroidList) # 选中的那类再分两类,如果类别为1,则新的类别号为len(centroidList)
            bestClustAss[np.nonzero(bestClustAss[:, 0] == 0)[0], 0] = bestCentToSplit   # 如果类别为0,则新的类别号为bestCenToSplit
            print("the bestCentToSplit is: ", bestCentToSplit)
            print("the len of bestClustAss is: ", len(bestClustAss))
            print("new cluster assessment: \n", bestClustAss)
            centroidList[bestCentToSplit] = bestNewCents[0, :]
            centroidList.append(bestNewCents[1, :])
            clusterAssment[np.nonzero(clusterAssment[:, 0] == bestCentToSplit)[0], :] = bestClustAss
        return centroidList, clusterAssment
    
    
    if __name__ == "__main__":
        dataList = loadDataSet('testSet2.txt')
        sseSplit, sseAssments = biKMeans(dataList, 3)
        fig = plt.figure()
        ax = fig.add_subplot(111)
        ax.scatter(dataList[np.nonzero(sseAssments[:, 0] == 0)[0], 0], dataList[np.nonzero(sseAssments[:, 0] == 0)[0], 1], 
                   c="blue")
        ax.scatter(dataList[np.nonzero(sseAssments[:, 0] == 1)[0], 0], dataList[np.nonzero(sseAssments[:, 0] == 1)[0], 1],
                   c="red")
        ax.scatter(dataList[np.nonzero(sseAssments[:, 0] == 2)[0], 0], dataList[np.nonzero(sseAssments[:, 0] == 2)[0], 1],
                   c="green")
        plt.show()

    划分结果:

     

    CONTACT INFORMATION

    E-Mail: birdguan@seu.edu.cn

    QQ: 46611253

    展开全文
  • sgd:mini-batch gradientdescent 每一轮迭代计算mini batch的梯度,然后对参数进行更新/所有参数同样的学习率,容易收敛局部最优解 momentum:动量,冲量,能在相关方向加速sgd,抑制振荡,加速收敛 nesteror:在...
  • 二分k均值 Python实现

    千次阅读 2016-04-27 20:16:48
    可能收敛局部最小值(对初始k个聚类中心的选择敏感),在大规模数据集上收敛较慢 适用数据类型:数值型数据 度量聚类效果的指标: SSE(sum of squared error, 误差平方和),SSE值越小表示数据点越接近于他们的...
  • 收敛到了局部最小值,而非全局最小值,也就是还需要继续收敛; 3、用误差平方和SSE来度量聚类效果。 即程序中clusterAssment矩阵的第一列之和,SSE越小表示数据点越接近它们的质心,聚类效果也越好。 4、一种...
  • 缺点:可能收敛局部最小,且在大规模数据集上收敛较慢 适用数据:数值型数据 一般流程: 收集数据 准备数据:需要数值型数据计算举例,标称型数据需要映射为二值型数据。 分析数据 训练算法:无监督学习不需要...
  • kmeans优缺点 及改进

    千次阅读 2016-04-29 10:49:53
    可能收敛局部最小值(对初始k个聚类中心的选择敏感),在大规模数据集上收敛较慢 适用数据类型:数值型数据 度量聚类效果的指标: SSE(sum of squared error, 误差平方和),SSE值越小表示数据点越接近于他们...
  • 从本节开始,将介绍无...缺点:可能收敛局部最小值,在大规模的数据集上的收敛速度慢。 适用数据类型:数值型。 可以用的误差指标如误差的平方和(Sum of Squared Error,即SSE)来评价算法的效果。k值是需要...
  • 该算法可通过调节控制参量g1,g2和w,优化模式的收敛速度, 使控制信号快速收敛到一个可靠的局部最优解。搭建基于微机械薄膜变形镜(MMDM)的自适应光学系统, 测量光学影响函数并验证单个电极电压和镜面变形之间的准平方...
  • k-均值 聚类算法

    2018-12-10 11:50:18
    首先初始化k个点作为质心,遍历数据集,...改进算法:二分-k-均值算法(克服k-均值局部收敛) 二分-k-均值 聚类算法  将所有点看成一个簇,利用2均值聚类将簇一分为二,选择SSE最大的簇进行划分,直到达到用户指...
  • 无监督学习——KMeans

    千次阅读 2018-02-08 10:01:35
    Means算法中,聚类中簇的个数K是用户预先给定的值,k均值算法收敛局部最小值,而非全局最小值(局部最小值指结果还可以但并非最好结果,全局最小值是可能的最好结果),用于度量聚类效果的指标是SSE(误差平方和)...
  • # -*- coding: utf-8 -*- ...因为单次只能收敛局部最优解 所以需要多次尝试 最所有对象的误差的平方和最小的结果。 二维数据 ''' #设定K值 K = 3 #从文本中获取对象列表 src_file_name = 'F:\\study\
  • K-means

    2018-07-23 20:31:00
    一种用于度量聚类效果的指标使SSE(误差平方和),SSE值越小表示数据点越接近于他们的质心,聚类效果也越好...为克服K-均值算法收敛局部最小值的问题,有人提出了另一个称为二分—K均值的算法。该算法首先将所有点...
  • 定义相应的能量函数, 可使其在机械手轨迹分布上取得极小, 通过Snake能量的轨迹收敛实现对机械手运动点的跟踪定位.利用轨迹能量系数的动态调节,可避免Snake搜索过程陷入局部极小.使用平方轨迹最小二乘预测器对轨迹点...
  • 针对BP神经网络收敛速度慢及容易陷入局部最优解的缺点,结合遗传算法全局搜索的特点,提出了一种基于遗传算法和BP神经网络建立近红外光谱煤质分析模型的方法;并利用主成分分析法提取煤炭样品的主成分值,有效地压缩了...
  • 直到类别的聚类中心点不发生变化算法的时间复杂度是O(nkt),n是所有对象的数目,k是簇的数目,t是迭代的次数,这个算法是局部收敛的。它找到的是使平方误差函数值最小的k个划分,当簇是密集的,球状的时候,聚类效果...
  • 为克服粒子群算法实现逆运动学求解收敛慢、易陷入局部最优等缺陷,依据得到的关节角度约束关系,以实际角度与理想角度的误差平方和作为适应度函数,提出利用粒子群优化神经网络的学习型算法进行求解。仿真实验验证了...
  • 机器学习公式推导

    2019-04-05 10:17:15
    文章目录线性回归逻辑回归线性判别...**代价函数:**使用L2平方差,由于模型函数变了,会导致J()变成非凸函数,有可能出现很多局部最小值,梯度下降很难收敛到全局最小值 线性判别分析 LDA思想:将高维样本投影到...
  • 计算表明,该畸变测度具有较好的抗噪声能力,而遗传算法能避免收敛局部极小值,减少了矫正图像的均方根误差。实验表明,对多幅图像分别和联合校正,相应矫正图像之间的均方根误差较小。计算和实验都表明该校正方法具有...
  • 通过引入步长线性搜索,SQP算法在一定的假设条件下可以具有全局和局部超线性收敛性。然而在传统的SQP算法中,其二次规划子问题可能不相容,也就是子问题可行集是空集。 为了解决这个不足,备种技术相继被提出。特别...
  • 机器学习算法-K-means聚类

    千次阅读 2015-06-03 12:30:14
    引文: k均值算法是一种聚类算法,所谓聚类,他是一种无监督学习,将相似的对象归到同一个蔟中。蔟内的对象越相似,聚类的效果越好。聚类和分类最大的不同在于,分类的目标事先已知,而聚类则...缺点:可能收敛局部
  • 卷积神经网络的调参技巧1 方法: 一、更多的优化算法 二、激活函数 三、网络的初始化 四、批归一化 五、数据增强 六、采用更多的调参技巧 ...1.调整学习率::使梯度有个累积值,将以往的梯度进行平方
  • 因为h(x)本身就是非线性,再去平方加和,更是非线性,就可能会使得代价函数的图形变为下图左边 这种图用梯度下降算法的话,可能会找到好多局部最优,但并不一定是全局最优。 我们是希望右图这种,可以保证使用梯度...
  • K-均值聚类算法研究

    2020-07-04 16:06:50
    本文就K-均值聚类算法的聚类结果依赖于初始中心,而且经常收敛局部最优解,而非全局最优解,以及聚类类别数K需要事先给定这两大缺憾展开研究。提出了分别解决这两个问题的算法各一个首先,本文将Hae-Sang等人的快速K-...
  • 算法词典20210224

    2021-02-24 14:14:57
    功能:将数据集根据聚类个数进行聚类,使得样本到聚类中心的距离平方最小。其实并没有全局最小化,而是一个局部最小化算法。 伪代码: 1. 获得聚类个数k及聚类中心c_1,c_2...c_k. 2. 重复步骤3和4直到算法收敛或者...

空空如也

空空如也

1 2
收藏数 28
精华内容 11
关键字:

局部平方收敛