程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
23478 人已学习
课程目录
已完结 57 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 作为程序员,为什么你应该学好数学?
免费
导读 (1讲)
导读:程序员应该怎么学数学?
基础思想篇 (18讲)
01 | 二进制:不了解计算机的源头,你学什么编程
02 | 余数:原来取余操作本身就是个哈希函数
03 | 迭代法:不用编程语言的自带函数,你会如何计算平方根?
04 | 数学归纳法:如何用数学归纳提升代码的运行效率?
05 | 递归(上):泛化数学归纳,如何将复杂问题简单化?
06 | 递归(下):分而治之,从归并排序到MapReduce
07 | 排列:如何让计算机学会“田忌赛马”?
08 | 组合:如何让计算机安排世界杯的赛程?
09 | 动态规划(上):如何实现基于编辑距离的查询推荐?
10 | 动态规划(下):如何求得状态转移方程并进行编程实现?
11 | 树的深度优先搜索(上):如何才能高效率地查字典?
12 | 树的深度优先搜索(下):如何才能高效率地查字典?
13 | 树的广度优先搜索(上):人际关系的六度理论是真的吗?
14 | 树的广度优先搜索(下):为什么双向广度优先搜索的效率更高?
15 | 从树到图:如何让计算机学会看地图?
16 | 时间和空间复杂度(上):优化性能是否只是“纸上谈兵”?
17 | 时间和空间复杂度(下):如何使用六个法则进行复杂度分析?
18 | 总结课:数据结构、编程语句和基础算法体现了哪些数学思想?
概率统计篇 (14讲)
19 | 概率和统计:编程为什么需要概率和统计?
20 | 概率基础(上):一篇文章帮你理解随机变量、概率分布和期望值
21 | 概率基础(下):联合概率、条件概率和贝叶斯法则,这些概率公式究竟能做什么?
22 | 朴素贝叶斯:如何让计算机学会自动分类?
23 | 文本分类:如何区分特定类型的新闻?
24 | 语言模型:如何使用链式法则和马尔科夫假设简化概率模型?
25 | 马尔科夫模型:从PageRank到语音识别,背后是什么模型在支撑?
26 | 信息熵:如何通过几个问题,测出你对应的武侠人物?
27 | 决策树:信息增益、增益比率和基尼指数的运用
28 | 熵、信息增益和卡方:如何寻找关键特征?
29 | 归一化和标准化:各种特征如何综合才是最合理的?
30 | 统计意义(上):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
31 | 统计意义(下):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
32 | 概率统计篇答疑和总结:为什么会有欠拟合和过拟合?
线性代数篇 (13讲)
33 | 线性代数:线性代数到底都讲了些什么?
34 | 向量空间模型:如何让计算机理解现实事物之间的关系?
35 | 文本检索:如何让计算机处理自然语言?
36 | 文本聚类:如何过滤冗余的新闻?
37 | 矩阵(上):如何使用矩阵操作进行PageRank计算?
38 | 矩阵(下):如何使用矩阵操作进行协同过滤推荐?
39 | 线性回归(上):如何使用高斯消元求解线性方程组?
40 | 线性回归(中):如何使用最小二乘法进行直线拟合?
41 | 线性回归(下):如何使用最小二乘法进行效果验证?
42 | PCA主成分分析(上):如何利用协方差矩阵来降维?
43 | PCA主成分分析(下):为什么要计算协方差矩阵的特征值和特征向量?
44 | 奇异值分解:如何挖掘潜在的语义关系?
45 | 线性代数篇答疑和总结:矩阵乘法的几何意义是什么?
综合应用篇 (6讲)
46 | 缓存系统:如何通过哈希表和队列实现高效访问?
47 | 搜索引擎(上):如何通过倒排索引和向量空间模型,打造一个简单的搜索引擎?
48 | 搜索引擎(下):如何通过查询的分类,让电商平台的搜索结果更相关?
49 | 推荐系统(上):如何实现基于相似度的协同过滤?
50 | 推荐系统(下):如何通过SVD分析用户和物品的矩阵?
51 | 综合应用篇答疑和总结:如何进行个性化用户画像的设计?
加餐 (3讲)
数学专栏课外加餐(一) | 我们为什么需要反码和补码?
数学专栏课外加餐(二) | 位操作的三个应用实例
数学专栏课外加餐(三):程序员需要读哪些数学书?
结束语 (1讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

36 | 文本聚类:如何过滤冗余的新闻?

黄申 2019-03-08
你好,我是黄申。
前两节,我讲了向量空间模型,以及如何在信息检索领域中运用向量空间模型。向量空间模型提供了衡量向量之间的距离或者相似度的机制,而这种机制可以衡量查询和被查询数据之间的相似程度,而对于文本检索来说,查询和文档之间的相似程度可作为文档的相关性。
实际上,除了文档的相关性,距离或者相似度还可以用在机器学习的算法中。今天,我们就来聊聊如何在聚类算法中使用向量空间模型,并最终实现过滤重复文章。

聚类算法

在概率统计模块中,我们介绍了分类(Classification/Categorization)和回归(Regression)这两种监督式学习(Supervised Learning)。监督式学习通过训练资料学习并建立一个模型,并依此模型对新的实例进行预测。
不过,在实际场景中,我们常常会遇到另一种更为复杂的情况。这时候不存在任何关于样本的先验知识,而是需要机器在没人指导的情形下,去将很多东西进行归类。由于缺乏训练样本,这种学习被称为“非监督学习”(Unsupervised Learning),也就是我们通常所说的聚类(Clustering)。在这种学习体系中,系统必须通过一种有效的方法发现样本的内在相似性,并把数据对象以群组(Cluster)的形式进行划分。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(7)

  • 余泽锋
    请问一下老师,余弦夹角本质上可以说是归一化的欧式距离么?

    作者回复: 可以这么认为

    2019-04-09
    2
  • mickey
    # encoding=utf-8
    from sklearn.feature_extraction.text import CountVectorizer

    #模拟文档集合
    corpus = ['I like great basketball game',
              'This video game is the best action game I have ever played',
              'I really really like basketball',
              'How about this movie? Is the plot great?',
              'Do you like RPG game?',
              'You can try this FPS game',
              'The movie is really great, so great! I enjoy the plot']

    #把文本中的词语转换为词典和相应的向量
    vectorizer = CountVectorizer()
    vectors = vectorizer.fit_transform(corpus)

    from sklearn.feature_extraction.text import TfidfTransformer

    #构建tfidf的值
    transformer = TfidfTransformer()
    tfidf = transformer.fit_transform(vectorizer.fit_transform(corpus))

    # 输出每个文档的向量
    tfidf_array = tfidf.toarray()
    words = vectorizer.get_feature_names()

    from Bio.Cluster import kcluster

    #进行聚类,使用向量间的夹角余弦作为相似度的度量
    clusterid, error, nfound = kcluster(tfidf_array, nclusters=3, dist='u')
    print(clusterid)
    '''
    Kmeans 的欧式距离:[0 2 0 1 2 2 1]
    Bio 的夹角余弦:[2 0 0 2 0 2 1]
    '''

    作者回复: 尝试了不同的方法👍

    2019-03-08
    2
  • Joe
    def customKmeans(vec_array, n_clusters=3, epochs=50):
        '''
        @description: 手动实现kmeans,以向量间的夹角余弦作为相似度
                     根据上述tf-idf得到的7条文本向量tfidf_array,进行聚类算法
        @param {type} vec_array- 向量组, n_clusters-聚类数目, epochs- 训练次数
        @return: cluster_labels- 分类标签
        '''

        # 初始化质心的位置
        cluster_centers = []
        cluster_centers_indx = []
        while (len(cluster_centers_indx) < n_clusters):
            indx = random.randint(0, len(vec_array)-1)
            if indx not in cluster_centers_indx:
                cluster_centers_indx.append(indx)
                cluster_centers.append(vec_array[indx])

        # 初始化向量类别
        cluster_labels = [0] * len(vec_array)
        max_similarity = [-1] * len(vec_array)
        epoch = 0
        while(epoch < epochs):
            # 计算每个向量与质心的相似性,并将其归纳到最近的质心集群中
            for i in range(0, len(vec_array)):
                max_similarity[i] = computeCosine(vec_array[i], cluster_centers[0])
                for j in range(1, n_clusters):
                    temp = computeCosine(vec_array[i], cluster_centers[j])
                    if (temp > max_similarity[i]):
                        max_similarity[i] = temp
                        cluster_labels[i] = j

            # 更新质心位置
            for i in range(0, n_clusters):
                # 找到集群对应原向量的下标
                indxs = [indx for indx, cluster in enumerate(
                    cluster_labels) if cluster == i]
                # 根据集群向量的平均值更新质点位置
                cluster_centers[i] = np.average(
                    [vec_array[indx] for indx in indxs], axis=0)

            # 当满足迭代次数或平均最大相似性时退出算法
            epoch += 1
            if (np.average(max_similarity) > 0.9):
                break
        return cluster_labels


    def computeCosine(vec1, vec2):
        # 计算向量间的余弦值
        vecCosine = np.dot(vec1, vec2) / \
            (np.linalg.norm(vec1) * np.linalg.norm(vec2))
        return vecCosine


    # 应用customkmeans
    labels = customKmeans(tfidf_array, n_clusters=3, epochs=1000)
    print(labels)

    输出结果:
    [0 2 0 1 2 2 1]
    2019-03-15
    1
  • Paul Shan
    kmeans方法用的是利用几何信息将空间点归类的方法,最终的结果是归好类的点集质心之间的距离远,但是集合内点之间距离近的效果,可以类比于软件开发中的高内聚低耦合原则来记忆。

    作者回复: 嗯,这个比喻好👍

    2019-09-26
  • Aaron(健廷)
    请问一下老师,“如果这个 K 值取得太小,群组可能切分太细,每个之间区别不大。如果 K 值取得太大,群组的粒度又太粗,造成群组内差异明显。”,這段話是不是寫反了?

    作者回复: 是的,笔误写反了。。。感谢指正

    2019-04-10
  • Bindy🌲
    老师,这里如果是中文,是不是要做分词呢

    作者回复: 是的,如果是中文,肯定要做分词的。

    2019-04-10
  • Joe
    老师,现在很多机器学习的算法都有现成的库了,如sklearn等。但是直接调库,总觉得停留在表面。请问有没有必要自己手动去实现一些经典的机器学习算法呢?

    作者回复: 这是一个好问题,可以参照专栏中的一些介绍,尝试实现某些算法,加强印象,甚至于将来可以根据具体的应用,对算法实现进行优化。

    2019-03-14
收起评论
7
返回
顶部