各位观众们一周不见，你们是不是已经等不及要看这期内容呢？这期的内容绝对不会让你失望。所以呢欢迎来到AI入门 - 集体智慧编程的第二章，这期内容里Pan会带着你制作一个简单的自动化归类系统，将知乎专栏中的文章聚合归类。

学习成果

知乎专栏这种阅读文章似乎并没有简书的分类那么完美，所以这次我们的目的就是实现100篇随机知乎专栏文章的分类！

没有分类的知乎专栏文章 :<

成功归类后的文章 :>

编程小技巧

# jieba分词用法
>>> import jieba
>>> from collections import Counter
# 假设content是一段很长的中文
>>> seg_list = jieba.cut_for_search(content)
>>> word_dict = Counter(seg_list)
>>> word_dict 
>>> Counter({'，': 17, '的': 17, '。': 9, '年龄': 5, '和': 5, '欢迎': 4, '会': 4, '、': 3, '是': 3, '考量': 3....}

# 所有的全角符号
>>> from zhon import hanzi
>>> hanzi.punctuation
>>> ＂＃＄％＆＇（）＊＋，－／：；＜＝＞＠［＼］＾＿｀｛｜｝～｟｠｢｣､　、〃〈〉《》「」『』【】〔〕〖〗〘〙〚〛〜〝〞〟〾〿–—‘’‛“”„‟…‧﹏﹑﹔·！？｡。

//字典排序
//假如word_dict是字典，那么我们可以根据值对于字典进行排列，reverse代表的是从大到小排序
>>> sorted_dict = sorted(word_dict.items(), key=lambda t: t[1], reverse=True)
>>> [('电影', 5), ('大家', 4), ('上映', 3), ('九月', 3), ('给', 3), ('做', 2), ('观看', 2), ('主力', 2)...]

什么是聚类?

什么是聚合归类？聚合归类顾名思义就是将具有同一特征的东西归为一类，比如我们根据人的身高可以分为高的人和低的人，根据体重作为标准可以将人分成胖子和瘦子。当然了总是把人分类似乎不是那么友好，我们可以做一些更有意思的事情，比如书籍的分类，我们可以把描述勇士，国王，恶龙的书籍归位冒险类书籍，可以把带有马克思，共产主义，资本主义话题的书籍归为政治类的文章。那么怎么给知乎专栏的文章归类呢？

你肯定已经猜到了。文章内容决定了文章的题材，如果把文章作为一个单位的话，什么是更小的单位？ 你也许会说段落，段落能决定文章的题材吗？显然是不能的。更小的单位呢？没错，就是词汇。 就像我上面所说的出现了特定词汇的文章有很大可能属于同一类，比如出现了”不能不看”，“人生”，“奋斗”，很大可能就是篇鸡汤文章，类似的也是如此。所以我们就根据这个标准前进吧！

单词向量(word vectors)

什么是单词向量？其实就是我们所需要的一个数据结构，为了是我们计算方便，这个矩阵统计了每个单词出现在每篇文章的数量，具体类似于下面这个表格

以文章3为例，眨眼望去和文章1的单词都差不多相似吧，但是和文章2的词汇大相径庭。所以我们得到结论文章3和文章1是同类文章的概率比文章3和文章2是同一类文章的概率大。

知乎专栏api介绍

数据的寻找过程不是此专题专门介绍的，不过机智的Pan已经替大家写好了接口。文件zhihu_zhuanlan.py是用来爬去知乎专栏的py文件，你可以尝试着去抓取任何感兴趣的专栏。那么怎么用呢？首先你得知道一个专栏的url，如果你细心的话，你可以看到zhihu_zhuanlan.py里有一个ZhiDailyNewsAPI类，其中有一个self.url的参数，所以我们可以替换成自己感兴趣的专栏进行聚类。在这里我以https://zhuanlan.zhihu.com/api/columns/happymuyi/posts?limit=100为示例抓取的。 其中还有一些有意思的方法:

test = ZhiDailyNewsAPI()# 调用class
size = get_article_size()# 得到此专栏有多少文章数
pprint(test.get_article(size=size)) # 获取此专栏所有的文章，默认size为10
test.save_as_text(size=size)# 保存文章到当前目录下

下面的article.txt为调用此知乎专栏调用test.save_as_text(size=size)得到的具体文章，很简单第一行为本篇文章的标题，第二行为本篇文章的内容，第三行为空格。每篇文章都遵循这样的规律，zhihu_zhuanlan.py和article.txt下载地址在本专题末尾。

专栏txt文章概览

词频统计(vocabulary frequency statistics)

数据有了，数据结构也有了，那么我们怎么才能把我们的数据变成这样的数据结构呢？在这里有几个问题需要注意：

• 中文词汇的分词，中文的词汇并不像英文的词汇，因为在英语中最基本的语言单位（具有表达效果）就是单词，但是中文中是汉字，有的单词是由好几个汉字组成的，所以怎么解决分词的难题呢？
• 如何把我们的数据转化成单词为行，文章为列的数据结构呢？
• 并不是每一个单词都是具有特征的，比如我就没有实际意义因为你根本无法根据我判断这篇文章的归属。

解决第一个问题我们需要借助一个python的包jieba，它可以帮助我们分解单词，具体的请在这期内容开头编程小技巧中查看。在ZhiDailyNewsAPI我又多写了一个叫ArticleAnalyze数据处理的新类，这个可以方便我们处理中文数据。

test = ArticleAnalyze()
test.save_article_analyze(n=test.get_article_size())

如果你使用上面的方法的话可以得到一个word_count.txt的文件，数据类型是我们已经每篇文章的词频统计：

每篇文章的词频统计

太好了我们已经对每一篇文章进行了词频统计，但是我们并没有把它转化成行为单词，列为文章的数据结构，在动手之前我们先解决下第二个问题，出现频率高的单词大多都是虚词并没有实际意义的，所以我们选取频率介于10%-50%的单词。现在我们创建自己的第一个generate_feed_vector.py的文件。

from chapter3.zhihu_zhuanlan import ArticleAnalyze

feeder = ArticleAnalyze()
# 得到文章的总量，这里我们直接得到此专栏的所有文章，所以不用上面的save_article_analyze方法
article_size = feeder.get_article_size()
article_list = feeder.get_article_analyze(n=article_size)

# ap_count统计出现单词的博客数目
ap_count = {}
for feed_single_article in article_list:
# api中content是字典中的键，对应的是文章的内容
    for word_tuple in feed_single_article["content"]:
        word = word_tuple[0]
        # 计数器统计所有单词的频率
        ap_count.setdefault(word, 1)
        if ap_count[word] >= 1:
            ap_count[word] += 1

# 选择介于10% - 50%之间的单词
word_list = []
for w, bc in ap_count.items():
    frac = float(bc) / article_size
    if frac > 0.1 and frac < 0.5:
        # 如果单词频率介于所有单词中的10%-50%添加尽我们的待处理列表
        word_list.append(w)

# 保存矩阵，记录真对每个博客的所有单词统计情况
out_file = open("article_data.txt", "w", encoding="utf-8")
out_file.write("Article")
for word in word_list:
     # 第一行写入所有单词
    out_file.write("\t{}".format(word))
out_file.write("\n")
for single_article in article_list:
    # 每行开头写入该文章的标题
    out_file.write(single_article["title"])
    single_article_contain_word_list = [i[0] for i in single_article["content"]]
    for word in word_list:
        # 如果
        if word in single_article_contain_word_list:
            # 如果本篇文章的单词在待处理列表里
            word_frequency = [i[1] for i in single_article["content"] if i[0] == word]
            # 写进文件里
            out_file.write("\t{}".format(word_frequency[0]))
        else:
            # 否则写0 
            out_file.write("\t0")
    out_file.write("\n")

运行generate_feed_vector.py这个文件你会得到一个article_data.txt文件，具体文件的数据结构如下：

article_data.txt

大功告成！我们已经得到词频数据的矩阵，别得意太早，这只是刚开始...那么接下来应该怎么判断哪些文章是属于同一类呢？

分级聚类(Hierarchical Clustering)

什么叫做分级聚类呢？分级聚类仅仅是聚类方式的一种，所以分级代表的是有严谨的层级结构，比如说文学包含小说，历史，其中小说又包含轻小说，历史又包含中国史和欧洲史。具体的流程如下所示，阶段1都是一些分散的文章，然后把最相似的小类归位一个更大的类，最后把归为更巨大的类。

hierarchicalcluster.png

现在请新创建一个叫做clust.py的文件我们开始动手啦～

# readfile是把我们上面的txt文件载入到python中列表化
def readfile(filename):
    lines = open(filename, encoding="utf-8").readlines()

    col_names = lines[0].strip().split("\t")[1:]
    row_names = []
    data = []
    for line in lines[1:]:
        p = line.strip().split('\t')
        row_names.append(p[0])
        # 加入词频
        data.append([float(x) for x in p[1:]])
    return row_names, col_names, data

先等等，怎么判断那两篇文章最相似？听上去有些耳熟？没错就是上篇文章讲的皮尔逊相关系数，这么说我可以循环整个文章列表给每两篇文章配对？ 真聪明。没想到的同学也不要紧，戳这儿再加深遍印象吧：） 相信我这世界上没有看不懂的文章，如果有，就看两遍。 好了请把皮尔逊相似度的公式加入到clust.py中

from math import sqrt
def pearson(v1, v2):
    # 简单求和
    sum1 = sum(v1)
    sum2 = sum(v2)

    # 求平方和
    sum1_sq = sum([pow(x, 2) for x in v1])
    sum2_sq = sum([pow(x, 2) for x in v2])

    # 求平方和
    p_sum = sum([v1[i] * v2[i] for i in range(len(v1))])

    num = p_sum - (sum1 * sum2 / len(v1))
    den = sqrt((sum1_sq - pow(sum1, 2) / len(v1)) * (sum2_sq - pow(sum2, 2) / len(v2)))

    if den == 0:
        return 0
    return 1.0 - num / den

接下来我们需要构造一个树的数据结构，用来储存当前的词频统计数据vec，子节点左边的树left， 子节点右边的树right，和到时候索引时的id,还有求出的相似系数distance。你可以把它看成咱们上面分级聚类步骤中包含两个小圆圈的空心圆环。别灰心，很简单的，把下面代码加入到clust.py中。

class BiCluster:
    def __init__(self, vec, left=None, right=None, distance=0.0, id=None):
        self.left = left
        self.right = right
        self.vec = vec
        self.id = id
        self.distance = distance

好终于到了最关键的一步了，我们开始聚类！思路就是咱们刚才想的当前列表中最小的两棵树配对，不过我们会合成一颗新的大树，大树的vec是原来两颗小数的平均值的一办，left是第一颗小数,right是第二颗小数,distance是这两颗小树的皮尔逊相似性值。然后我们就可以删除这两颗小数了，反正从大树我们也可以索引到，循环结束的条件是什么呢？不难想到最后的结果就是只剩下了一颗超级大的树，所以就是len(clust)等于1的时候停止。

def h_cluster(rows, distance=pearson):
    # 缓存距离
    distances = {}
    current_cluster_id = -1
    
    # 将每篇文章加入到`clust`中
    clust = [BiCluster(rows[i], id=i) for i in range(len(rows))]

    while len(clust) > 1:
        lowest_pair = (0, 1)
        # 计算两篇文章的相似度
        closest = distance(clust[0].vec, clust[1].vec)

        for i in range(len(clust)):
            for j in range(i + 1, len(clust)):
                # 寻找最相似的两篇
                if (clust[i].id, clust[j].id) not in distances:
                    distances[(clust[i].id, clust[j].id)] = distance(clust[i].vec, clust[j].vec)

                d = distances[(clust[i].id, clust[j].id)]
                if d < closest:
                    closest = d
                    lowest_pair = (i, j)
        # 合并两颗小数成大树
        mergevec = [
            (clust[lowest_pair[0]].vec[i] + clust[lowest_pair[1]].vec[i]) / 2.0 for i in range(len(clust[0].vec))
        ]

        # 建立新的聚类
        new_cluster = BiCluster(mergevec, left=clust[lowest_pair[0]], right=clust[lowest_pair[1]], distance=closest,
                                id=current_cluster_id)
        # 大树的id都是负数
        current_cluster_id -= 1
        del clust[lowest_pair[1]]
        del clust[lowest_pair[0]]
        clust.append(new_cluster)

    return clust[0]

终于聚类完成了，怎么检查结果呢，将下面的代码加入到你的clust文件中

def print_clust(clust, labels=None, n=0):
    # 控制距离开头的空格数量
    print(" " * n, end="")
    # 聚合树的id都为负数，所以用-表示
    if clust.id < 0:
        print("-")
    else:
        if labels == None:
            print(clust.id)
        else:
            print(labels[clust.id])
   # 如果有左节点的化就打印
    if clust.left != None:
        print_clust(clust.left, labels=labels, n=n + 1)
   # 如果有右节点的化就打印
    if clust.right != None:
        print_clust(clust.right, labels=labels, n=n + 1)


if __name__ == "__main__":
    article_names, words, data = readfile("article_data.txt")
    clust = h_cluster(data)
    print_clust(clust=clust, labels=article_names)

打印得到的部分结果如下，浏览下发现韩式挺准确的，比如第一个木易电影团 > 梁朝伟电影 > 母亲的电影都是关于电影的文章。 还有最后的恋爱关系 和驴得水都是关于恋爱题材的。

                 【木易观影团】第一期来了！想看黄轩、段奕宏如何“硬战”？欢迎报名！
                 -
                  梁朝伟在这部越南电影里是个混混，却演出了诗人气质！
                  -
                   十部关于母亲的高分电影，每一部都曾看哭许多人！
                   -
                    《星际迷航3》：让我们制造点声响，献给值得怀念的人
                    -
                     成长就是不断筛选，留下那些最重要的人
                     -
                      那一年，鲍勃·迪伦20岁
                      影评人的职责是什么？
                -
                 《金刚狼3》：漫长的告别，讲不出再见
                 -
                  -
                   专访 |《神秘巨星》导演：我希望制作这部电影来感谢我的妈妈
                   《当怪物来敲门》：爱让我们害怕失去，但人生注定要经历遗憾与离别
                  -
                   龙清泉奥运会破世界记录，八年起伏他不止是冠军！
                   -
                    -
                     《血战钢锯岭》让我动容的，是英雄背后的那位英雄
                     你是否曾爱过谁，比海还深？
                    -
                     《廊桥遗梦》：遇见一次婚姻之外的爱情，算出轨吗？
                     -
                      平淡日子里的苦，终会成为回忆里的甜
                      -
                       《推销员》：太过注重羞耻心的男人，为什么不值得尊敬？
                       《破碎人生》：对不起，还没来得及好好爱你
            -
             视频 | 专访赵立新：我本来就很小众
             九月观影指南：除了《敦刻尔克》，还有哪些电影值得一看？
  -
   在恋爱关系里，你会在乎对方的年龄吗？
   《驴得水》：别骂一个女人是婊子，也别骂一个男人是牲口

绘制树状图(Drawing the Dendrogram)

绘制文字形式的还是不够直观，对于一个观众无法一眼看到图中所表达的信息，为了构图出咱们文章该开始的图形效果，所以我们要开始画一个树状图。 请把以下代码加入到clust.py之中

# 得到聚类的高度直到叶节点为止
def get_height(clust):
    if clust.left == None and clust.right == None:
        return 1
    return get_height(clust.left) + get_height(clust.right)

# 得到聚类的深度
def get_depth(clust):
    if clust.left == None and clust.right == None:
        return 0
    # 一个枝节点等于左右两个分支较大者
    return max(get_depth(clust.left), get_depth(clust.right)) + clust.distance

# 用来画树
def draw_den_drog_gram(clust, labels, jpeg="clusters.jpg"):
    h = get_depth(clust) * 200
    w = 1200
    # 得到深度
    depth = get_depth(clust)
    # 缩放比例是为了调整图形的大小防止变形
    scaling = float(w - 300) / depth
    # 画张新的画布
    img = Image.new("RGB", (w, int(h)), (255, 255, 255)）
    draw = ImageDraw.Draw(img)
    # 画新的节点
    draw_node(draw, clust, 10, (h / 2), scaling, labels)
    img.save(jpeg, "JPEG")


def draw_node(draw, clust, x, y, scaling, labels):
    # 如果为枝节点的话画左右子节点
    if clust.id < 0:
        h1 = get_height(clust.left) * 40
        h2 = get_height(clust.right) * 40
        top = y - (h1 + h2) / 2
        bottom = y + (h1 + h2) / 2
        # 线的长度
        ll = clust.distance * scaling
        # 
        draw.line((x, top + h1 / 2, x, bottom - h2 / 2), fill=(255, 0, 0))
        draw.line((x, top + h1 / 2, x + ll, top + h1 / 2), fill=(255, 0, 0))
        draw.line((x, bottom - h2 / 2, x + ll, bottom - h2 / 2), fill=(255, 0, 0))

        draw_node(draw, clust.left, x + ll, top + h1 / 2, scaling, labels)
        draw_node(draw, clust.right, x + ll, bottom - h2 / 2, scaling, labels)
    else:
        font = ImageFont.truetype("/Library/Fonts/Arial Unicode.ttf")
        draw.text((x + 10, y - 7), labels[clust.id], (0, 0, 0), font=font)
# 测试一下吧
if __name__ == "__main__":
    article_names, words, data = readfile("article_data.txt")
    clust = h_cluster(data)
    # print_clust(clust=clust, labels=article_names)
    draw_den_drog_gram(clust, article_names, jpeg="zhihu_zhuanlan_clust.jpg")

结果如下，树状图也很准确和我们之前文字类型的基本吻合

zhihu_zhuanlan_clust.jpg

K-均值聚类(k-mean clustering)

前面介绍的是分局聚类，那么你肯定会问肯定还有其他聚类喽？没错K-均值聚类就是另一种重要的聚类方法，它和分级聚类有什么不同呢？K-均值聚类的具体工作方法如下：

k-mean clustering.jpeg

可以看到第一副图里有两个没有带字母的圆圈为我们设置的聚类点，其他的都是带字母的为文章。然后我们根据计算相似度逐渐向有字母点的中心靠拢， 最终达到一个稳定状态A 、B、C为一个聚类，D、E为一个聚类。所以他比分级聚类的好处在于我们可以人为的设置聚类的大小而不是机器自动生成。其次在于之前的聚类之中合并一个新聚类之后就要重新计算聚类，所以数据量很大时会非常慢，这个聚类显然就要快很多。 好了请把以下的代码加入到clsut.py之中

def k_cluster(rows, distance=pearson, k=4):
    # 寻找每个点的最大值和最小值random.random() * (ranges[i][1] - ranges[i][0]) + ranges[i][0]
    ranges = [(min([row[i] for row in rows]), max([row[i] for row in rows]))
              for i in range(len(rows[0]))]

    # 创建k个中心点，k为随机创建的聚类中心点个数，
    clusters = [[random.random() * (ranges[i][1] - ranges[i][0]) + ranges[i][0]
                 for i in range(len(rows[0]))]
                for j in range(k)]

    last_matches = None
    # 循环聚类次数
    for t in range(100):
        print("Iteration {}".format(t))
        best_matches = [[] for i in range(k)]

        # 和分级聚类的计算方法都相似就是求最相似的点
        for j in range(len(rows)):
            row = rows[j]
            best_match = 0
            for i in range(k):
                d = distance(clusters[i], row)
                if d < distance(clusters[best_match], row):
                    best_match = i
            # 
            best_matches[best_match].append(j)

        if best_matches == last_matches:
            break
        last_matches = best_matches
        
        # 重新计算聚类中心点的平均值,把中心点移到平均位置处
        for i in range(k):
            avgs = [0.0] * len((rows[0]))
            if len(best_matches[i]) > 0:
                for row_id in best_matches[i]:
                    for m in range(len(rows[row_id])):
                        avgs[m] += rows[row_id][m]
                        
                for j in range(len(avgs)):
                    avgs[j] /= len(best_matches[i])
                clusters[i] = avgs
    return best_matches

二维形式展示数据(View Data in Two Dimentions)

这里需要引入一种多维缩放的技术，这种技术可以帮助我们找到一种二维表达方法。什么意思呢？以我们的数据为例，我们现在只有k值聚类后的结果，每一个聚类列表中包含相似文章的数据，但是我们并没有办法得到他们之间的二维关系，然而利用多维缩放我们可以把数据转化成坐标形式再进行可视化。请将下面的代码加入到clust.py文件之中

def scale_down(data, distance=pearson, rate=0.01):
   n = len(data)
   # 计算每一对数据之间的距离
   real_list = [[distance(data[i], data[j]) for j in range(n)]
                for i in range(0, n)]

   outer_sum = 0.0
   # 随机初始化在二维空间中的位置
   loc = [[random.random(), random.random()] for i in range(n)]
   fake_dist = [[0.0 for j in range(n)] for i in range(n)]
   
   last_error = None
   for m in range(0, 1000):
       # 寻找投影后的距离
       for i in range(n):
           for j in range(n):
               fake_dist[i][j] = sqrt(sum([pow(loc[i][x] - loc[j][x], 2)
                                           for x in range(len(loc[i]))]))
       # 移动节点  
       grad = [[0.0, 0.0] for i in range(n)]

       total_error = 0
       for k in range(n):
           for j in range(n):
               if j == k:
                   continue
               # 误差值等于差值比真实值
               error_term = (fake_dist[j][k] - real_list[j][k]) / real_list[j][k]
               # 每一个节点都需要根据误差的多少按照比例移动
               grad[k][0] += ((loc[k][0] - loc[j][0]) / fake_dist[j][k]) * error_term
               grad[k][1] += ((loc[k][1] - loc[j][1]) / fake_dist[j][k]) * error_term

               total_error += abs(error_term)

       if last_error and last_error < total_error:
           break
       last_error = total_error

       for k in range(n):
           loc[k][0] -= rate * grad[k][0]
           loc[k][1] -= rate * grad[k][1]

   return loc

好了，让我们开始可视化吧～

def draw_2d(data, labels, jpeg="md2d.jpg"):
    img = Image.new("RGB", (2000, 2000), (255, 255, 255))
    draw = ImageDraw.Draw(img)
    for i in range(len(data)):
        x = (data[i][0] + 0.5) * 1000
        y = (data[i][1] + 0.5) * 1000
        font = ImageFont.truetype("/Library/Fonts/Arial Unicode.ttf", 14)
        draw.text((x, y), labels[i], (0, 0, 0), font=font)
    img.save(jpeg, "JPEG")

下面的是最终的缩放结果

two-dimensional-cluster

好耶！我们终于成功地把知乎专栏文章归类了，既然是已有的模型，只要有更多的数据我们就可以不断的归类了～

附加

• article.txt
• clust.py
• generate_feed_vector.py
• zhihu_zhuanlan.py