精华内容
下载资源
问答
  • 对5单9对j对q对k单a
    千次阅读
    2018-09-10 12:38:56

    Git合并单个文件和[y,n,q,a,d,/,K,j,J,g,e,?]

    前言

    今天想要合并两个分支的同一个文件,查了网上一些资料,将A分支的a文件合并到B分支的a文件上。可以通过以下方式合并

    git checkout B
    git checkout --patch A a

    先切换到B分支,将A分支的a文件给与B。
    然后碰到了Apply this hunk to index and worktree [y,n,q,a,d,/,K,j,J,g,e,?]?
    刚开始我是一个一个y按得,后来觉得太慢也不敢乱按网上查询一下意思,在stackoverflow发现答案

    [y,n,q,a,d,/,K,j,J,g,e,?]

    y - stage this hunk
    n - do not stage this hunk
    q - quit; do not stage this hunk nor any of the remaining ones
    a - stage this hunk and all later hunks in the file
    d - do not stage this hunk nor any of the later hunks in the file
    g - select a hunk to go to
    / - search for a hunk matching the given regex
    j - leave this hunk undecided, see next undecided hunk
    J - leave this hunk undecided, see next hunk
    k - leave this hunk undecided, see previous undecided hunk
    K - leave this hunk undecided, see previous hunk
    s - split the current hunk into smaller hunks
    e - manually edit the current hunk
    ? - print help

    上面这些文字都是输入?打印出来的。

    Apply this hunk to index and worktree [y,n,q,a,d,/,K,j,J,g,e,?]??

    y - 存储这个hunk
    n - 不存储这个hunk
    q - 离开,不存储这个hunk和其他hunk
    a - 存储这个hunk和这个文件后面的hunk
    d - 不存储这个hunk和这个文件后面的hunk
    g - 选择一个hunk
    / - 通过正则查找hunk
    j - 不确定是否存储这个hunk,看下一个不确定的hunk
    J - 不确定是否存储这个hunk,看下一个hunk
    k - 不确定是否存储这个hunk,看上一个不确定的hunk
    K -不确定是否存储这个hunk,看上一个hunk
    s - 把当前的hunk分成更小的hunks
    e - 手动编辑当前的hunk
    ? - 输出帮助信息

    合并其他分支单个/多个commit

    https://www.cnblogs.com/phpper/p/7609238.html
    https://git-scm.com/book/zh/v2/Git-%E5%B7%A5%E5%85%B7-%E9%AB%98%E7%BA%A7%E5%90%88%E5%B9%B6

    更多相关内容
  • 逆序的数量(c++)(详细解答)

    千次阅读 2020-07-09 16:06:11
    a[j],则其为一个逆序;否则不是。 输入格式 第一行包含整数n,表示数列的长度。 第二行包含 n 个整数,表示整个数列。 输出格式 输出一个整数,表示逆序的个数。 数据范围 1≤n≤100000 输入样例 6 2 3 4 5 6 ...

    逆序对的数量(c++)(详细解答)

    题目如下:
    给定一个长度为n的整数数列,请你计算数列中的逆序对的数量。

    逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满足 i < j 且 a[i] > a[j],则其为一个逆序对;否则不是。

    输入格式
    第一行包含整数n,表示数列的长度。

    第二行包含 n 个整数,表示整个数列。

    输出格式
    输出一个整数,表示逆序对的个数。

    数据范围
    1≤n≤100000
    输入样例

    6
    2 3 4 5 6 1
    

    输出

    5
    

    下面为解答过程:
    这道题用到的是“归并排序”分而治之的思想,所以我们先来回顾一下归并排序的概念。
    先简单看一下归并排序的代码:

    void merge_sort(int q[],int l,int r)
    {
        if(l>=r) return;
        int mid=l+r>>1;
        
        merge_sort(q,l,mid);merge_sort(q,mid+1,r);
        
        int k=0,i=l,j=mid+1;
        while(i<=mid&&j<=r)
        {
            if(q[i]<=q[j]) tmp[k++]=q[i++];
            else tmp[k++]=q[j++];
        }
        while(i<=mid) tmp[k++]=q[i++];
        while(j<=r) tmp[k++]=q[j++];
        for(i=0,j=l;j<=r;i++,j++) q[j]=tmp[i];
    }
    

    先设立一个中心点mid,进行递归处理,将数组不断分成两,最后成为单一的元素,此为分。
    在这里插入图片描述

    然后既是让每一个元素符合我们的要求,也就是从小到大排序,此为治。
    在这里插入图片描述
    这是归并排序,既然归并排序把数组分为两段,我们再来看看逆序对的情况

    1. 逆序对的两个元素都在左端
    2. 逆序对的两个元素都在右端
    3. 一个元素在左端,一个元素在右端

    在这里插入图片描述

    我们是把q[i],q[j]进行比较,把较小的元素放到一个新数组t[]中。所以我们能保证i左边的元素都是小于j的,然后i右边的元素都是大于j的,所以对于q[j]来说,满足的元素有(mid-i+1)个。在这里插入图片描述

    所以我们只要在q[i]>q[j]的情况下,加上一个计数器res+=mid-i+1,就可以自然而然的完成我们的“治”,也就是寻找并记录下我们的逆序对。

    #include<iostream>
    
    using namespace std;
    
    const int N=100010;
    int q[N],t[N],n;
    long long res;//假如按照逆序对最多的情况,也就是倒序,例:5 4 3 2 1。
    				//int不能满足res。
    
    void merge_sort(int l,int r)
    {
        if(l>=r) return;
        
        int mid=l+r>>1;
        merge_sort(l,mid),merge_sort(mid+1,r);//  “分”
        
        int k=0,i=l,j=mid+1;
        while(i<=mid&&j<=r)
        {
            if(q[i]<=q[j]) t[k++]=q[i++];
            else
            {
                t[k++]=q[j++];
                res+=mid-i+1;//  “治”
            }    
        }
        while(i<=mid) t[k++]=q[i++];//收尾:假如左端或者右端先填完了,得把另一端的数都加上。
        while(j<=r) t[k++]=q[j++];
        
        for(i=l,j=0;i<=r;i++,j++) q[i]=t[j];
    }
    
    int main()
    {
        cin >> n;
        for(int i=0;i<n;i++) cin >> q[i];
        
        merge_sort(0,n-1);
        cout << res << endl;
        
        return 0;
    }
    

    最后,以上是我个人对这道题以及分治的一点见解,如有错误,请指正!

    展开全文
  • 如果要使用聚类分析算法一堆文本分类,关键要解决这几个问题: 如何衡量两个对象是否相似 算法的性能怎么度量 如何确定分类的个数或聚类结束的条件 选择哪种分类算法 下面就带着这几个问题,以我工作中的一个...

    聚类分析是一种无监督机器学习(训练样本的标记信息是未知的)算法,它的目标是将相似的对象归到同一个簇中,将不相似的对象归到不同的簇中。如果要使用聚类分析算法对一堆文本分类,关键要解决这几个问题:

    • 如何衡量两个对象是否相似
    • 算法的性能怎么度量
    • 如何确定分类的个数或聚类结束的条件
    • 选择哪种分类算法

     下面就带着这几个问题,以我工作中的一个业务需求为例,来学习一下怎么对中文文本进行聚类。(此文略长,包含了理论基础、算法院里、代码实现和实验效果分析

    一. 业务需求

    我在工作中遇到这样一个需求:有个铁路通信专业的业务系统,收集了一些通信设备的生产厂商信息,共4500多条。由于数据是人工录入的,非常不规范,存在数据重复、信息不规范、错别字等现象,需要对数据进行分析归类,将相同或相似的数据划到一起,再通过人工审核规范数据,最终形成规范的字典数据。


    二、理论基础

    1. 相似度计算

    • 欧氏距离

    欧氏距离是一种常用的距离定义,指在m维空间中两个点之间的真实距离,对多维向量A=(A1,A2,……,An),B=(B1,B2,……,Bn),欧氏距离的计算公式如下:

     

    • 余弦相似度

    余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体差异的大小。相比欧氏距离度量,余弦相似度更加注重两个向量在方向上的差异,而非距离或长度上的差异。余弦值的计算公式如下:

    相对于欧氏距离,余弦相似度更适合计算文本的相似度。首先将文本转换为权值向量,通过计算两个向量的夹角余弦值,就可以评估他们的相似度。余弦值的范围在[-1,1]之间,值越趋近于1,代表两个向量方向越接近;越趋近于-1,代表他们的方向越相反。为了方便聚类分析,我们将余弦值做归一化处理,将其转换到[0,1]之间,并且值越小距离越近。

    2. 性能度量

    在选择聚类算法之前,首先来了解什么样的聚类结果是比较好的。我们希望同一个簇内的样本尽可能相似,不同簇的样本尽可能不同,也就是说聚类结果的“簇内相似度”高且“簇间相似度”低。

    考虑聚类结果的簇划分C={\left \{ C_{1},C_{2}, ...,C_{K}\right \}}, 定义:

    avg(C)=\frac{2}{(|C|(|C|-1))}\sum_{1\leq i< j\leq \left | C \right |}dist(x_i,x_j)

    diamC=max_{1\leq i< j\leq \left | C \right |}dist(x_{i},x_{j})

    d_{min} (C_i,C_j )= min_{x_i\in C_i,x_j\in C_j} dist(x_i,x_j)

    d_{cen} (C_i,C_j )=dist(\mu _i,\mu_j)

    其中,\mu代表簇C的中心点;avg(C) 代表簇C内样本的平均距离;diamC代表簇C内样本间的最远距离;d_{min} (C_i,C_j )对应于簇C_iC_j簇最近样本间的距离;d_{cen} (C_i,C_j )对应于簇C_iC_j 中心点间的距离。基于以上公式可导出下面两个常用的聚类性能度量内部指标:

    • DB指数(Davies-Bouldin Index,简称DBI)

    DBI=\frac{1}{k}\sum_{i=1}^{k}max_{j\neq i}\left ( \frac{avg(C_i)+avg(C_j)}{d_{cen}(C_i,C_j)} \right )

    • Dumn指数(Dumn Index,简称DI)

    DI=min_{1\leqslant i\leq k}\left \{ min_{j\neq i}\left ( \frac{d_{min}(C_i,C_j)}{max_{1\leqslant l\leq k}diam(C_l)} \right ) \right \}

    DB指数的计算方法是任意两个簇内样本的平均距离之和除以两个簇的中心点距离,并取最大值,DBI的值越小,意味着簇内距离越小,同时簇间的距离越大;Dumn指数的计算方法是任意两个簇的最近样本间的距离除以簇内样本的最远距离的最大值,并取最小值,DI的值越大,意味着簇间距离大而簇内距离小。因此,DBI的值越小,同时DI的值越大,意味着聚类的效果越好


    三、聚类过程

    有了相似度计算方法和性能度量这两个理论基础,下面就开始对文本分类了。

    1. 分词

    要对中文文本做聚类分析,首先要对文本做分词处理,例如“联想移动通信科技有限公司”,我们希望将其切分为“联想 移动 通信 科技 有限 公司”。python提供专门的中文切词工具“jieba”,它可以将中文长文本划分为若干个单词。

    为了提高分类的准确率,还要考虑两个干扰因素:一是英文字母大小写的影响,为此我们将英文字母统一转换为大写;二是例如 “有限”、“责任”、“股份”、“公司”等通用的词汇,我们将这样的词汇连同“()”、“-”、“/”、“&”等符号作为停用词,将其从分词结果中去除掉,最后得到有效的词汇组合,代码和结果如下:

    # 加载停用词,这里主要是排除“有限公司”一类的通用词
    def loadStopWords(fileName):
        dataMat = []
        fr = open(fileName)
        words = fr.read()
        result = jb.cut(words, cut_all=True)
        newWords = []
        for s in result:
            if s not in newWords:
                newWords.append(s)
        newWords.extend([u'(', u')', '(', ')', '/', '-', '.', '-', '&'])
        return newWords
    
    
    # 把文本分词并去除停用词,返回数组
    def wordsCut(words, stopWordsFile):
        result = jb.cut(words)
        newWords = []
        stopWords = loadStopWords(stopWordsFile)
        for s in result:
            if s not in stopWords:
                newWords.append(s)
        return newWords
    
    
    # 把样本文件做分词处理,并写文件
    def fileCut(fileName, writeFile, stopWordsFile):
        dataMat = []
        fr = open(fileName)
        frW = open(writeFile, 'w')
        for line in fr.readlines():
            curLine = line.strip()
            curLine1 = curLine.upper()  # 把字符串中的英文字母转换成大写
            cutWords = wordsCut(curLine1, stopWordsFile)
            for i in range(len(cutWords)):
                frW.write(cutWords[i])
                frW.write('\t')
            frW.write('\n')
            dataMat.append(cutWords)
        frW.close()

    2. 构建词袋模型

    文本被切分成单词后,需要进一步转换成向量。先将所有文本中的词汇构建成一个词条列表,其中不含重复的词条。然后对每个文本,构建一个向量,向量的维度与词条列表的维度相同,向量的值是词条列表中每个词条在该文本中出现的次数,这种模型叫做词袋模型。例如,“阿尔西集团”和“阿尔西制冷工程技术(北京)有限公司”两个文本切词后的结果是“阿尔西 集团”和“阿尔西 制冷 工程技术 北京”,它们构成的词条列表是[阿尔西, 集团, 制冷, 工程技术, 北京],对应的词袋模型分别是[1,1,0,0,0],[1,0,1,1,1]。

    # 创建不重复的词条列表
    def createVocabList(dataSet):
        vocabSet = set([])
        for document in dataSet:
            vocabSet = vocabSet | set(document)
        return list(vocabSet)
    
    
    # 将文本转化为词袋模型
    def bagOfWords2Vec(vocabList, inputSet):
        returnVec = [0] * len(vocabList)
        for word in inputSet:
            if word in vocabList:
                returnVec[vocabList.index(word)] += 1
            else:
                print "the word: %s is not in my Vocabulary!" % word
        return returnVec

    3. 权值转换

    TF-IDF是一种统计方法,用来评估一个词条对于一个文件集中一份文件的重要程度。TF-IDF的主要思想是:如果某个词在一篇文章中出现的频率TF高,并且在其他文件中很少出现,则认为此词条具有很好的类别区分能力,适合用来分类。将词袋向量转换为TF-IDF权值向量,更有利于判断两个文本的相似性。

    • TF(词频,term frequency):

    tf_{i,j} =\frac{n_{i,k}}{\sum_{k}n_{k,j}}

           分子是词条t_i在文件d_j中出现的次数,分母是文件d_j中所有词条出现的次数之和。

    • IDF(逆向文件频率,inverse document frequency):

    idf_i=log\frac{\left | D \right |}{\left |\left \{ j:t_i\in d_j \right \} \right |}

            对数内的分子是文件总数,分母是包含词条t_i的文件数,如果该词不存在,就会导致分母为零,因此一般使用1+\left |\left \{ j:t_i\in d_j \right \} \right |作为分母。

    tfidf_{i,j} = tf_{i,j}\times idf_i

    # 计算所有文本包含的总词数
    def wordsCount(dataSet):
        wordsCnt = 0
        for document in dataSet:
            wordsCnt += len(document)
        return wordsCnt
    
    
    # 计算包含某个词的文本数
    def wordInFileCount(word, cutWordList):
        fileCnt = 0
        for i in cutWordList:
            for j in i:
                if word == j:
                    fileCnt = fileCnt + 1
                else:
                    continue
        return fileCnt
    
    
    # 计算权值,并存储为txt
    def calTFIDF(dataSet, writeFile):
        allWordsCnt = wordsCount(dataSet)  # 所有文本的总词数
        fileCnt = len(dataSet)  # 文本数
        vocabList = createVocabList(dataSet)  # 词条列表
        # tfidfSet = []
        frW = open(writeFile, 'w')
        for line in dataSet:
            wordsBag = bagOfWords2Vec(vocabList, line)  # 每行文本对应的词袋向量
            lineWordsCnt = 0
            for i in range(len(wordsBag)):
                lineWordsCnt += wordsBag[i]  # 计算每个文本中包含的总词数
            tfidfList = [0] * len(vocabList)
            for word in line:
                wordinfileCnt = wordInFileCount(word, dataSet)  # 包含该词的文本数
                wordCnt = wordsBag[vocabList.index(word)]  # 该词在文本中出现的次数
                tf = float(wordCnt) / lineWordsCnt
                idf = math.log(float(fileCnt) / (wordinfileCnt + 1))
                tfidf = tf * idf
                tfidfList[vocabList.index(word)] = tfidf
            frW.write('\t'.join(map(str, tfidfList)))
            frW.write('\n')
            # tfidfSet.append(tfidfList)
    
        frW.close()

    4. 计算余弦相似度

    前面已经介绍过,相对欧氏距离,余弦相似度更适合文本分类,Python实现如下:

    # 计算余弦距离
    def gen_sim(A, B):
        num = float(dot(mat(A), mat(B).T))
        denum = linalg.norm(A) * linalg.norm(B)
        if denum == 0:
            denum = 1
        cosn = num / denum
        sim = 0.5 + 0.5 * cosn  # 余弦值为[-1,1],归一化为[0,1],值越大相似度越大
        sim = 1 - sim  # 将其转化为值越小距离越近
        return sim

    5. 使用K-均值聚类算法分类

    K-均值是将数据集划分为k个簇的算法,簇的个数k是用户给定的,每个簇通过其质心(簇中所有点的中心)来描述。K-均值算法的工作流程是:

    (1)随机确定k个初始点作为质心。

    (2)将数据集中的每个点找到距离最近的质心,并将其分配到该质心对应的簇中。

    (3)将每个簇的质心更新为该簇中所有点的平均值。

    (4)重复第(2)、(3)步骤,直到簇的分配结果不再变化。

    为了评价聚类的质量,定义一种用于衡量聚类效果的指标SSE(Sum of Squared Error,误差平方和),误差是指样本到其质心的距离。SSE值越小,表示数据点越接近质心。

    由于K-均值算法是随机选取质心,因此可能会收敛到局部最小值,而非全局最小值。为了克服这个问题,提出了一种二分K-均值算法。该算法的思路是将所有点作为一个簇,然后将该簇一分为二。之后选择一个能最大程度降低SSE值的簇继续进行划分,直到得到用户指定的簇数目为止。

    注意:该算法需要确定簇的个数,而我的需求中分类的个数是未知的。因此,希望通过观察性能度量指标DI和DBI的变化趋势来确定一个合适k值。

    性能度量指标的实现:

    # 计算簇内两个样本间的最大距离
    def diamM(dataSet):
        maxDist = 0
        m = shape(dataSet)[0]
        if m > 1:
            for i in range(m):
                for j in range(i + 1, m):
                    dist = gen_sim(dataSet[i, :], dataSet[j, :])
                    if dist > maxDist:
                        maxDist = dist
        return maxDist
    
    
    # 计算两个簇间,样本间的最小距离
    def dMin(dataSet1, dataSet2):
        minDist = 1
        m = shape(dataSet1)[0]
        n = shape(dataSet2)[0]
        for i in range(m):
            for j in range(n):
                dist = gen_sim(dataSet1[i, :], dataSet2[j, :])
                if dist < minDist:
                    minDist = dist
        return minDist
    
    
    # 计算簇内样本间的平均距离
    def avg(dataSet):
        m = shape(dataSet)[0]
        dist = 0
        avgDist = 0
        if m > 1:
            for i in range(m):
                for j in range(i + 1, m):
                    dist += gen_sim(dataSet[i, :], dataSet[j, :])
            avgDist = float(2 * dist) / (m * (m - 1))
        return avgDist
    

    二分K-均值算法实现:

    def biKmeans(dataSet, k, distMeas=gen_sim):
        m = shape(dataSet)[0]
        clusterAssment = mat(zeros((m, 2)))
        SSE = []  # 用于记录每次迭代的总误差
        DI = 0  # DI指数,用于衡量簇间的相似度,值越大越好
        DBI = 0
        dmin = 1
        diam = []
        diam.append(diamM(dataSet))
        centroid0 = mean(dataSet, axis=0).tolist()[0]
        centList = [centroid0]  # 创建质心列表,初始只有一个质心
        for j in range(m):  # 计算初始的平方误差
            clusterAssment[j, 1] = distMeas(centroid0, dataSet[j, :]) ** 2
        SSE.append([0, sum(clusterAssment[:, 1]), 1, 0])
        while (len(centList) < k):  # 聚类数小于k时
            lowestSSE = inf
            for i in range(len(centList)):  # 对每个质心循环
                # 获取第i个质心对应的数据集(簇)
                ptsInCurrCluster = dataSet[nonzero(clusterAssment[:, 0].A == i)[0],
                                   :]
                # 对该簇使用k均值算法,分为2个簇
                centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)
                # 计算该簇的总误差
                sseSplit = sum(splitClustAss[:, 1])
                # 计算未分割的其他簇的总误差
                sseNotSplit = sum(
                    clusterAssment[nonzero(clusterAssment[:, 0].A != i)[0], 1])
                # print "sseSplit, and notSplit: ",sseSplit,sseNotSplit
                if (sseSplit + sseNotSplit) < lowestSSE:  # 寻找最小误差对应的簇
                    bestCentToSplit = i
                    bestNewCents = centroidMat
                    bestClustAss = splitClustAss.copy()
                    lowestSSE = sseSplit + sseNotSplit
    
            # 更新簇的分配结果,将多分出来的簇作为最后一个簇
            bestClustAss[nonzero(bestClustAss[:, 0].A == 1)[0], 0] = len(
                centList)  # change 1 to 3,4, or whatever
            bestClustAss[nonzero(bestClustAss[:, 0].A == 0)[0], 0] = bestCentToSplit
            # 更新质心列表
            centList[bestCentToSplit] = bestNewCents[0, :].tolist()[0]
            centList.append(bestNewCents[1, :].tolist()[0])
            # 更新分类结果
            clusterAssment[nonzero(clusterAssment[:, 0].A == bestCentToSplit)[0],
            :] = bestClustAss
            index = len(centList);
            error = sum(clusterAssment[:, 1])
    
            # 新划分的两个簇
            newDataSet1 = dataSet[
                          nonzero(clusterAssment[:, 0].A == bestCentToSplit)[0], :]
            newDataSet2 = dataSet[
                          nonzero(clusterAssment[:, 0].A == len(centList) - 1)[0],
                          :]
    
            # 计算DI指数,该值越大越好
            diam1 = diamM(newDataSet1)
            diam2 = diamM(newDataSet2)
            diam[bestCentToSplit] = diam1
            diam.append(diam2)
    
            for l in range(len(centList) - 1):
                dataSetl = dataSet[nonzero(clusterAssment[:, 0].A == l)[0], :]
                dist = dMin(dataSetl, newDataSet2)
                if dist < dmin:
                    dmin = dist
    
            DI = float(dmin) / max(diam)
    
            # 计算DBI指数,该值越小越好
            maxDBI = 0
            sumDBI = 0
            DBI = 0
            for i in range(len(centList)):
                for j in range(i + 1, len(centList)):
                    dataSeti = dataSet[nonzero(clusterAssment[:, 0].A == i)[0], :]
                    dataSetj = dataSet[nonzero(clusterAssment[:, 0].A == j)[0], :]
                    DBIij = (avg(dataSeti) + avg(dataSetj)) / gen_sim(
                        mat(centList[i]), mat(centList[j]))
                    if DBIij > maxDBI:
                        maxDBI = DBIij
                sumDBI += maxDBI
            DBI = sumDBI / len(centList)
    
            SSE.append([index, error, DI, DBI])
            print '---' + getTime() + '---'
            print u'误差最小的簇是: ', bestCentToSplit
            print u'该簇的长度是: ', len(bestClustAss)
            print u'分为%d个簇,误差是%f' % (index, error)
            print u'分为%d个簇,DI值是%f,DBI值是%f' % (index, DI, DBI)
        return mat(centList), clusterAssment, mat(SSE)

    由于计算DI和DBI值的复杂度较高,先选取500多个样本测试一下效果,得到的趋势如下图所示,然而结果并不理想,DBI值趋于不变,DI值的变化趋势也没有规律。同时,分别对500多个样本划分为200、300、420个簇,经过人工校验,被成功聚类的样本分别为111个、106个、105个。由此可以推断,K-均值算法不适合对厂商名称的分类,分析其原因可能是每个厂商名称所包含的词汇量太少。接下来我们再尝试另一种聚类算法——层次聚类。

    6. 使用层次聚类算法

    层次聚类试图在不同的层次对数据集进行划分,可以采用“自底向上”的聚类策略,也可以采用“自顶向下”的分拆策略。一般采用“自底向上”的策略,它的思路是先将数据集中的每个样本看作一个初始聚类簇,然后找出两个聚类最近的两个簇进行合并,不断重复该步骤,直到达到预设的聚类个数或某种条件。关键是如何计算两个簇之间的距离,每个簇都是一个集合,因此需要计算集合的某种距离即可。例如,给定簇C_iC_j ,可通过以下3种方式计算距离:

    • 最小距离:d_{min}(C_i,C_j)=min_{x\in C_i,z\in C_j}dist(x,z)
    • 最大距离:d_{max}(C_i,C_j)=max_{x\in C_i,z\in C_j}dist(x,z)
    • 平均距离: d_{avg}(C_i,C_j)=\frac{1}{\left | C_i \right |\left | C_j \right |}\sum_{x\in C_i}\sum_{z\in C_j}dist(x,z)

    最小距离由两个簇的最近样本决定,最大距离由两个簇的最远样本决定,平均距离由两个簇的所有样本决定。

    接下来要考虑如何确定一个合适的聚类个数或某种结束条件,具体思路是:

    (1)选定一部分测试样本,对其进行层次聚类分析。

    (2)记算性能度量指标DBI和DI的变化趋势,结合人工校验,得到一个合适的聚类个数和对应的距离阈值。

    (3)将此距离阈值作为聚类结束的条件,对所有样本做聚类分析。此时无需再计算DBI和DI值,计算效率可以大幅提升。

    # 计算两个簇的最小距离
    def distMin(dataSet1, dataSet2):
        minD = 1
        m = shape(dataSet1)[0]
        n = shape(dataSet2)[0]
        for i in range(m):
            for j in range(n):
                dist = gen_sim(dataSet1[i], dataSet2[j])
                if dist < minD:
                    minD = dist
        return minD
    
    
    # 计算两个簇的最大距离
    def distMax(dataSet1, dataSet2):
        maxD = 0
        m = shape(dataSet1)[0]
        n = shape(dataSet2)[0]
        for i in range(m):
            for j in range(n):
                dist = gen_sim(dataSet1[i], dataSet2[j])
                if dist > maxD:
                    maxD = dist
        return maxD
    
    
    # 计算两个簇的评均距离
    def distAvg(dataSet1, dataSet2):
        avgD = 0
        sumD = 0
        m = shape(dataSet1)[0]
        n = shape(dataSet2)[0]
        for i in range(m):
            for j in range(n):
                dist = gen_sim(dataSet1[i], dataSet2[j])
                sumD += dist
        avgD = sumD / (m * n)
        return avgD
    
    
    # 找到距离最近的两个簇
    def findMin(M):
        minDist = inf
        m = shape(M)[0]
        for i in range(m):
            for j in range(m):
                if i != j and M[i, j] < minDist:
                    minDist = M[i, j]
                    minI = i
                    minJ = j
        return minI, minJ, minDist
    
    
    
    # 层次聚类算法
    def hCluster(dataSet, k, dist, distMeas=distAvg):
        m = shape(dataSet)[0]
        clusterAssment = mat(zeros((m, 1)))
        performMeasure = []
        M = mat(zeros((m, m)))  # 距离矩阵
        # 初始化聚类簇,每个样本作为一个类
        for ii in range(m):
            clusterAssment[ii, 0] = ii
    
        for i in range(m):
            for j in range(i + 1, m):
                dataSeti = dataSet[nonzero(clusterAssment[:, 0].A == i)[0], :]
                dataSetj = dataSet[nonzero(clusterAssment[:, 0].A == j)[0], :]
                M[i, j] = distMeas(dataSeti, dataSetj)
                M[j, i] = M[i, j]
            if mod(i,10) == 0: print i
        q = m  # 设置当前聚类个数
        minDist = 0
        # while (q > k):
        while (minDist < dist):
            i, j, minDist = findMin(M)  # 找到距离最小的两个簇
            # 把第j个簇归并到第i个簇
            clusterAssment[nonzero(clusterAssment[:, 0].A == j)[0], 0] = i
            for l in range(j + 1, q):  # 将j之后的簇重新编号
                clusterAssment[nonzero(clusterAssment[:, 0].A == l)[0], 0] = l - 1
            M = delete(M, j, axis=0)
            M = delete(M, j, axis=1)
            for l in range(q - 1):  # 重新计算第i个簇和其他簇直接的距离
                dataSeti = dataSet[nonzero(clusterAssment[:, 0].A == i)[0], :]
                dataSetl = dataSet[nonzero(clusterAssment[:, 0].A == l)[0], :]
                M[i, l] = distMeas(dataSeti, dataSetl)
                M[l, i] = M[i, l]
    
            DBI = DBIvalue(dataSet, clusterAssment, q)
            DI = DIvalue(dataSet, clusterAssment, q)
           
            performMeasure.append([q - 1, minDist, DBI, DI])
    
            q = q - 1
    
            print '---' + getTime() + '---'
            print u'当前簇的个数是:', q
            print u'距离最小的两个簇是第%d个和第%d个,距离是%f,DBI值是%f,DI值是%f' % (
                i, j, minDist, DBI, DI)
    
        return clusterAssment, mat(performMeasure)

    仍然选择K-均值聚类分析的500多个样本,对其进行层次聚类,得到的性能指标变化趋势如下:

    从上图可以看出,DI值呈下降趋势,DBI值呈阶跃上升趋势,根据性能度量的规则(DBI的值越小越好;DI的值越大越好),最优值可能出现阶跃点附近,即划分为471类和445类两个点,同时结合人工校验,可以确定445类更加合理。

    接下来,将k值设置为445进行层次聚类分析,发现仍有少量相似的样本被划分到不同的类。根据业务需求,为了减少后续的核实工作量,我们希望将相似的样本尽可能划分到同一类中,同时可以接受少部分不同的样本划分到同一类,我们给予k值适当的冗余,将其设置为420,再分别基于最大距离、最小距离、平均距离进行分析。

    距离计算方法

    聚到簇中的样本数

    最佳距离

    最大距离

    160

    0.2975

    最小距离

    167

    0.2556

    平均距离

    167

    0.2839

    从以上分类结果看出,采用层次聚类算法对测试样本进行分类,效果明显优于K-均值聚类算法。并且,该算法可以通过学习得到距离阈值作为聚类结束的条件,从而解决了分类个数k值无法确定的问题。

    为了降低个别样本对整体结果的影响,选择基于平均距离的距离分析算法,并将距离阈值设置为0.29,对4574个样本做聚类分析,最后得到3128个类,看一下部分样本的分类效果:


    四、总结

    对文本聚类主要有几个步骤:对文本分词、构建词袋模型、权值转换、计算余弦相似度、选取聚类算法、性能度量、确定聚类结束条件。如果文本所含的词汇量较多,并且已知分类的个数k,可以选择二分K-均值聚类算法。而层次聚类算法根据样本距离来分类,并且可以以样本距离作为分类结束的条件,比较适合k未知的情况。


    代码资源下载地址(留言回复可能不及时,请您自行下载):

    https://download.csdn.net/download/leaf_zizi/12073625

    网盘下载链接: https://pan.baidu.com/s/1EXyaEfQ2K-JVe4mbX41c-Q 提取码: ghas(下载后记得给文章点赞哦)


    参考:

    周志华《机器学习》

    Peter Harrington 《机器学习实战》

    https://blog.csdn.net/songzhilian22/article/details/49636725/

     

    展开全文
  • A站、B站、C站、D站、E站、F站、G站、H站、I站、J站、K站、L站、M站、N站、O站、P站、Q站、R站、S站、T站、U站、V站、W站、X站、Y站、Z站都是什么网站? A站 https://www.acfun.cn/ AcFun弹幕视频网 - 认真你就输...

    A站、B站、C站、D站、E站、F站、G站、H站、I站、J站、K站、L站、M站、N站、O站、P站、Q站、R站、S站、T站、U站、V站、W站、X站、Y站、Z站都是什么网站?Q站是什么?

    A站、B站、C站、D站、E站、F站、G站、H站、I站、J站、K站、L站、M站、N站、O站、P站、Q站、R站、S站、T站、U站、V站、W站、X站、Y站、Z站都是什么网站?

    A站

    https://www.acfun.cn/

    AcFun弹幕视频网 - 认真你就输啦 (・ω・)ノ- ( ゜- ゜)つロ

    A站 AcFun ACG 弹幕 视频 动画 漫画 游戏 新番 鬼畜 东方 初音 DOTA MUGEN

    AcFun是国内首家弹幕视频网站,这里有全网独家动漫新番, 友好的弹幕氛围,有趣的UP主,好玩有科技感的虚拟偶像,年轻人都在用。

     

    B站

    https://www.bilibili.com/

    哔哩哔哩 (゜-゜)つロ 干杯~-bilibili

    bilibili是国内知名的视频弹幕网站,这里有及时的动漫新番,活跃的ACG氛围,有创意的Up主。大家可以在这里找到许多欢乐。

    Bilibili,哔哩哔哩,哔哩哔哩动画,哔哩哔哩弹幕网,弹幕视频,B站,弹幕,字幕,AMV,MAD,MTV,ANIME,动漫,动漫音乐,游戏,游戏解说,二次元,游戏视频,ACG,galgame,动画,番组,新番,初音,洛天依,vocaloid,日本动漫,国产动漫,手机游戏,网络游戏,电子竞技,ACG燃曲,ACG神曲,追新番,新番动漫,新番吐槽,巡音,镜音双子,千本樱,初音MIKU,舞蹈MMD,MIKUMIKUDANCE,洛天依原创曲,洛天依翻唱曲,洛天依投食歌,洛天依MMD,vocaloid家族,OST,BGM,动漫歌曲,日本动漫音乐,宫崎骏动漫音乐,动漫音乐推荐,燃系mad,治愈系mad,MAD MOVIE,MAD高燃

     

    C站

    不详(请各位大佬评论区补充)

     

    D站

    貌似因侵权暂时已关闭(请各位大佬评论区补充)

     

    E站

    不详(请各位大佬评论区补充)

     

    F站

    不详(请各位大佬评论区补充)

     

    G站

    叽哩叽哩游戏网ACG(G站) – ACG爱好者聚集地

    叽哩叽哩(G站)为ACG爱好者提供最新最好玩的ACG资源下载,P站,pixiv图集下载,单机游戏下载,单机游戏资讯等精彩内容

    单机游戏,P站,pixiv,单机游戏推荐,ACG,ACG游戏下载,G站,二次元,galgame,叽哩叽哩游戏网

     

    H站

    哈哩哈哩-还是那个温馨小站(H站)

    哈哩哈哩让你爱不离手的温馨小站,这里有最新最全的动漫、剧集、影视等作品供您欣赏,还有最新鲜的资讯让你提前知晓世间动态,哈哩哈哩爱不离手。

     

    I站

    不详(请各位大佬评论区补充)

     

    J站

    不详(请各位大佬评论区补充)

     

    K站

    K站 - 次元街

     

    L站

    http://www.lqzhan.com/

    L站-乐Q站-乐Q导航网

    乐Q导航网是专注于网络技术相关行业网址导航,提供最新前沿it技术资源分享相关行业网站网址,一站式网络技术学习起点站,用心打造最实用的技术网站导航!

    L站,乐Q站,乐Q导航,乐Q导航网,导航,资源导航,影视导航,站长导航,网址大全,网址收录,网站收录

     

    M站

    猫耳FM_来自二次元的声音_( :3」∠)_M站

    M站(猫耳FM)是第一家弹幕音图站,同时也是中国声优基地,在这里可以听电台,音乐,翻唱,小说和广播剧,用二次元声音连接三次元.

    猫耳FM,有声漫画,广播剧,催眠,日抓,配音,翻唱,电台,铃声,3D音乐,新闻,声优

     

    N站

    不详(请各位大佬评论区补充)

     

    O站

    Orzice_冰尘网 - 您的二次元ACGN爱好者社区ヾ(◍°∇°◍)ノ゙(O站)

    Orzice_冰尘网简称“O站”,一个综合性的二次元ACGN爱好者社区,动漫美图,cosplay,漫展活动,300英雄等ACGN资源应有尽有。一起吐槽楼主,寻找好姬友一起分享二次元日常。

     

    P站

    http://www.pixiv.net/

    插画交流网站 | pixiv

    动漫,p站,pixiv,acg,二次元

    pixiv(P站)是最大的动漫资源分享平台,专为ACG爱好者收集海量最新最好玩的ACG资源下载,P站图集,pixiv图集下载,有意思的动漫资讯,乐翻天的ACGN幻想次元领域,让您流连忘返。

     

    Q站

    http://www.iqzhan.com/

    Q站-好东西不私藏 乐于分享-关注QQ最新动态,掌握QQ第一资讯,分享最具价值内容

    Q站资源网,是一家QQ技术网,涵盖了QQ活动网的所有QQ资源,每天免费分享大量QQ技术教程,致力建设最大的QQ技术网站!

    Q站,情话,情感,励志,资源网,QQ教程,QQ活动,QQ资源,免费源码,免费软件,情感语录

     

    R站

    R站|学习使我快乐! - 专注C4D三维|建模|渲染|后期|动效|绑定|产品|包装|动画|自由艺术|设计学习交流

     

    S站

    嘶哩嘶哩-萌导航_silisili.cc | 您的私人二次元导航姬

    嘶哩嘶哩萌导航是一个极简风格的二次元导航主页网站,简洁清新,轻快大方,在嘶哩嘶哩导航你可以自定义喜欢的背景,以及自由切换偏好的搜索引擎,获取更舒适便捷的上网体验!

    嘶哩嘶哩,嘶哩嘶哩萌导航,二次元导航,简约导航网站,无广告,自定义壁纸主页网站,网址导航,网站导航,自定义网址导航,S站灯塔,silisili

     

    T站

    不详(请各位大佬评论区补充)

     

    U站

    不详(请各位大佬评论区补充)

     

    V站

    不详(请各位大佬评论区补充)

     

    W站

    不详(请各位大佬评论区补充)

     

    X站

    不详(请各位大佬评论区补充)

     

    Y站

    不详(请各位大佬评论区补充)

     

    Z站

    不详(请各位大佬评论区补充)

     

     

    展开全文
  • 比如排除黑桃J 8 2 7 3 草花K 6 这样甲就会在开局说不知道 而乙说“我知道你不知道”,也就是说乙所知道的花色内的数字一定不包含被排除的哪些数字中 那么乙手中的花色一定是黑桃和方块 紧接着甲说知道了...
  • GJK SPP 5BGK AEC F04A tB9 D4 RMP

    万次阅读 2021-01-13 08:43:09
    专业供应各种小封装贴片二极管 贴片三极管 贴片集成电路 贴片集成IC 专业反查贴片元件,以下为部分元件的MARKING 代码 CODE 丝印 顶...MARK TOP TTWIC MARK PART MARKING 6M.R V57N p8Q V16 203 83U 19 4C7 B8LW 109...
  • Guided Filter三维点云降噪

    千次阅读 2019-04-28 23:58:52
    Guided Filter一般用来2D图像进行降噪等处理,实际上,稍作修改后可以3D点云进行降噪。 从Guided Filter的基本假设出发,可以推导出针对3D数据的处理方法。这里仅考虑引导数据是点云本身的情况。 首先,根据局部...
  • 《算法导论》实验五:最近点算法(C++)

    万次阅读 多人点赞 2015-12-15 14:59:00
    最近点问题: 在n>=2个点的集合Q中寻找最近点。 “最近”是指通常意义下的欧几里得距离:即点p1(x1,y1)和p2(x2,y2)之间的距离为:sqrt((x1-x2)2 +(y1-y2)2)。
  • ACM 逆序(逆序数)总结

    万次阅读 多人点赞 2018-07-25 17:44:54
    与之前不同的地方在于,求小于某个数的个数时用到了线段树,所以非常快 这里的线段树表示某个范围内的值个数query 1--3,就表示值在1--3的个数 然后对于1--n个数,我们每个数都进行两步操作 查询1--a[i],点更新a...
  • 小型汽车(蓝牌)川A2D1E7 川AEH989 川AG17G6 川BFZ775 川BR3727 川BZA453川LN7823 鄂A13F07 鄂A16MG9 鄂A6B258 鄂A8YZ73 鄂AD75P6鄂AKU713 鄂AL0Q98 鄂ALA589 鄂AMX770 鄂ANZ246 鄂ARB360鄂AT18A1 鄂AZ37Z8 鄂FRW567 ...
  • 分析(SPA)——综合评价

    千次阅读 2020-09-07 22:29:43
    分析是在一定的问题背景下,中2个集合的确定性与不确定性以及确定性与不确定性的相互作用所进行的一种系统和数学分析。通常包括中2个集合的特性、关系、结构、状态、趋势、以及相互联系模式所进行的...
  • 9 价值的组合、切分(Combining and Splitting Value) 尽管,我们可以电子货币的交易进行单独的处理。但实际上,在转让过程中为每一分钱进行单独的交易是很不方便的(比如交易1.2个BTC,我们不能按0.00001BTC为...
  • 如果令 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 分别等于 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 那么   Hard work (努力工作) H+A+R+D+W+O+R+K...
  • 今天的算法课上主要讲了最近点的问题,在老师的讲解下这个问题有了一个基础的认识和了解,这里就先这个问题做一个简单的总结吧。 最近点问题介绍: 最近点问题说来其实很简单,主要就是在二维平面内的n...
  • WhatsAPP通讯协议端端加密人工智能

    万次阅读 2021-09-16 09:46:01
    本文是一个以 whatsapp 为案例的,针对端端聊天加密通讯协议整理的一个学习笔记,仅供大家学习。Signal protocol 是真正的端到端的通讯加密协议,号称是世界上最安全的通讯协议,任何第三方包括服务器都无法查看...
  • 0001292814-19-000947.txt : 201903290001292814-19-000947.hdr.sgml : 2019032920190328190010ACCESSION NUMBER:0001292814-19-000947CONFORMED SUBMISSION TYPE:6-KPUBLIC DOCUMENT COUNT:11CONFORMED PERIOD OF R...
  • -.V-._-.d-.g-/+-0$-0H-1%-1/-10-1^-1o-2/-2@-3'-4)-4o-5>-5H-5U-6,-6J-7/-7P-9e-9g-9h-9i-9j-:l", "bu": "0$192,FKJgT=UYZ^e+hhjmm8mFoGpGp}sjw]w{-'7-'E-/m-3#-4.-6=", "fou": "4I:L:O:Q~1-3:", "mian": "!...
  • 本文全文原创 转载请注明出处 ...平面最近点,即平面中距离最近的两点 分治算法: int SOLVE(int left,int right)//求解点集中区间[left,right]中的最近点 {  double ans; //answer  0) 调用前的预...
  • 密码分析(表代换): 密文1: UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZQWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPPZSZUFPOMBZWPFUPZHMDJUDTMOHMQ 密文2: ...
  • 分治法-最接近点问题

    千次阅读 多人点赞 2018-12-30 19:05:29
    例如:在空中交通控制中,若将飞机作为空间中的一个点来处理,则具有最大碰撞危险的两架飞机所处的点,就是这个空间中距离最接近的一对点。 这类问题是计算几何学中研究的基本问题之一。 我们着重考虑平面上的最...
  • 0007算法笔记——【分治法】最接近点问题

    万次阅读 多人点赞 2013-01-09 22:09:13
    问题场景:在应用中,常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中,常需要了解其邻域中其他... 问题描述:给定平面上n个点,找其中的一对点,使得在n个点的所有点中,该点
  • 【LeetCode】﹝回文ி﹞数、串、链表、 文章目录【LeetCode】﹝回文ி﹞数、串、链表、回文数★回文链表★最长回文串★验证回文串★破坏回文串★★最长回文子序列★★回文★★★最短回文串★★★ 回文数★ 9. ...
  • 聚类分析(K-means算法)

    万次阅读 多人点赞 2018-05-28 22:05:44
    C_j = arg\min_{C_k}\frac{1}{n}\sum_{p\in C_k}|p-X_i|^2 其中p是某个簇Ck中的样本。即,用Xi到某个簇所有样本平均距离作为衡量该点到该簇的距离后, 选择离Xi最近的一个簇作为最近簇。 sklearn.metrics....
  • 分治法解决最近点问题

    万次阅读 多人点赞 2018-07-04 11:23:09
    问题 给定平面上n个点,找其中的一对点,使得在n个点的所有点中,该点的距离最小。严格地说,最接近点可能多于1。为了简单起见,这里只限于找其中的一对。原理(这段为抄袭...
  • HTML5全屏烟花特效 html代码 <!DOCTYPE html> <html lang="zh"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> <meta name=...
  • 小型汽车(蓝牌)川A77HE2 川A9Z05P 川AH39B7 川AJ20N2 川AU7X72 川AV228N川HF3109 川JU9108 川YN4946 鄂A07ZY2 鄂A16KL8 鄂A23B47鄂A23BA7 鄂A6Q120 鄂A71NS2 鄂A71NW9A83P99 鄂AC1J17鄂AHP189 鄂AR65M1 鄂AV3A97 ...
  • 点云匹配算法ICP、PL-ICP、NICP和IMLS-ICP的理解

    万次阅读 多人点赞 2019-11-27 15:55:25
    点云匹配算法是为了匹配两帧点云数据,从而得到传感器(激光雷达或摄像头)前后的位姿差,即里程数据。...Trace(A)≥Trace(BA) H H H进行SVD分解 H = U Λ V T H=U \Lambda V^{T} H=UΛVT 令 X = V...
  • 标签多分类及多标签多分类算法

    千次阅读 2020-03-27 15:45:07
    标签二分类算法,标签多分类算法,多标签多分类算法及多标签多分类在Scikit-learn中的实现方式。
  • %dij4=sqrt(0.5*(E(A(1),1)-E(A(5),1))^2); %dij5=sqrt(0.5*(E(A(1),1)-E(A(6),1))^2); %if dij1 %if E(A(1),3)(A(2),3) %M(i,:)=E(A(1),(1:2)); %else %M(i,:)=E(A(2),(1:2)); %end %continue; %elseif ...
  • 归并排序求逆序

    千次阅读 2017-01-31 21:33:28
    给一列数a1,a2,...,an,求它的逆序对数,即有多少个有序(i,j),使得iaj。n可以高达10^6。 输入 第一行输入整数N(2 接下来一行N个正整数数分别是a1,a2,...,an(ai 输出 输出一个数表示逆序对数。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 460,515
精华内容 184,206
热门标签
关键字:

对5单9对j对q对k单a