新聞中心
公司新聞
行業動態
國外生活
異域風情
政策指南

人人都能讀懂的無監督學習:什麽是聚類和降維?

時間:2017-08-31 來源:36氪

機器學習已經成爲了改變時代的大事,一時間似乎人人都應該懂一點機器學習。但機器學習涉及到的數學知識和編程能力往往讓沒有相關經驗的人望而卻步。

YupTechnologies 机器学习专家 Vishal Maini 近日在 Medium 上发布了一个介绍机器学习的系列文章《人人读得懂的机器学习(Machine Learning for Humans)》,用普通人能理解的语言对机器学习领域的一些核心概念进行了阐述。机器之心在这里编译了这一系列文章的第三部分「无监督学习」,对主要的聚類和降維算法进行了介绍,其中包括 K 均值聚類、层次聚類、主成分分析(PCA)和奇異值分解(SVD)。

HG娱乐可以怎樣發現一個數據集的底層結構?HG娱乐可以怎樣最有用地對其進行歸納和分組?HG娱乐可以怎樣以一種壓縮格式有效地表征數據?這都是無監督學習的目標,之所以稱之爲「無監督」,是因爲這是從無標簽的數據開始學習的。

HG娱乐将在这里探索的两种无监督学习任务是:1)将数据按相似度聚類(clustering)成不同的分组;2)降維(reducing dimensionality),以便在保留数据结构和有用性的同时对数据进行压缩。

無監督學習方法可能有用的案例:

  • 一家廣告平台需要根據相似的人口學特征和購買習慣將美國人口分成不同的小組,以便廣告客戶可以通過有關聯的廣告接觸到他們的目標客戶。

  • Airbnb 需要将自己的房屋清单分组成不同的社区,以便用户能更轻松地查阅这些清单。

  • 一個數據科學團隊需要降低一個大型數據集的維度的數量,以便簡化建模和降低文件大小。

和監督學習不同,要找到評價無監督學習算法優劣的指標可並不輕松。「表現水平」往往是主觀的,而且因領域不同而各不相同。

聚類

聚類的一个有趣的真实应用案例是营销数据提供商 Acxiom 的人生阶段聚類系统 Personicx。这项服务将美国家庭分成了 70 个不同的聚類,它们分属于 21 个人生阶段分组,可以被广告主用于投放定向 Facebook 广告、陈列式广告和直邮广告等。

人人都能讀懂的無監督學習:什麽是聚類和降維?

Personix 人口学特征聚類的一部分

他们的白皮书表明他们使用了重心聚類(centroid clustering)和主成分分析,这两种技术在这一节都有覆盖。

你可以想象,如果广告主想(1)理解他们已有的客户群,(2)通过相关的人口学特征、兴趣和生活习惯向潜在新客户投放定向广告以便高效利用广告开支,那么这些聚類将对他们非常有用。

人人都能讀懂的無監督學習:什麽是聚類和降維?

实际上,你只需要在 Acxiom 的「我属于哪个聚類?」工具中回答几个简单问题,你就能知道你个人属于哪个聚類,体验地址:https://isapps.acxiom.com/personicx/personicx.aspx

让HG娱乐了解几种聚類方法,看看这样的任务是如何完成的。

K 均值聚類

「重心之赛有 k 个魔戒,在那之上,是希望的力量。」

聚類的目标是为数据点分组,使得不同聚類中的数据点是不相似的,同一聚類中的数据点则是类似的。

使用 K 均值聚類,HG娱乐希望将HG娱乐的数据点聚類为 K 组。K 更大时,创造的分组就更小,就有更多粒度;K 更小时,则分组就更大,粒度更少。

该算法的输出是一组「标签」,这些标签将每个数据点都分配到了 K 组中的一组。在 K 均值聚類中,这些组的定义方式是为每个组创造一个重心(centroid)。这些重心就像是聚類的心脏,它们可以「捕获」离自己最近的点并将其加入到自己的聚類中。

你可以把這些重心看作是派對上成爲關注焦點的人,他們就像是有磁性一樣。如果只有一個這樣的人,每個人都會圍繞在他周圍;如果有很多這樣的人,就會形成很多更小一點的活動中心。

K 均值聚類的步骤如下:

  • 定义 K 个重心。一开始这些重心是随机的(也有一些更加有效的用于初始化重心的算法)

  • 寻找最近的重心并且更新聚類分配。将每个数据点都分配给这 K 个聚類中的一个。每个数据点都被分配给离它们最近的重心的聚類。这里的「接近程度」的度量是一个超参数——通常是欧几里得距离(Euclidean distance)。

  • 将重心移动到它们的聚類的中心。每个聚類的重心的新位置是通过计算该聚類中所有数据点的平均位置得到的。

重复第 2 和 3 步,直到每次迭代时重心的位置不再显著变化(即直到该算法收敛)。

这就是 K 均值聚類工作方式的精简版!该算法的可视化演示可在这里查看:https://www.naftaliharris.com/blog/visualizing-k-means-clustering/,你可以像读漫画一样理解。平面上的每个数据点都根据离自己最近的重心加了颜色。你可以看到这些重心(更大一点的蓝点、红点和绿点)一开始是随机的,然后很快进行了调整,得到了它们各自的聚類。

人人都能讀懂的無監督學習:什麽是聚類和降維?

K 均值聚類的另一个真实应用是分类手写数字。假设HG娱乐有用像素亮度的长向量表示的数字的图像。假设这些图像是黑白两色的,大小为 64×64 像素。每个像素代表一个维度。那么这些图像就生活在一个有 64×64=4096 个维度的世界里。

在这个 4096 维的世界里,K 均值聚類让HG娱乐可以按接近程度对这些图像分组,并且假设这些靠得很近的图像都是同一个数字。这种算法可以在数字识别上得到相当好的结果,参阅:http://ieeexplore.ieee.org/document/6755106/?reload=true

层次聚類

「让HG娱乐把 100 万个选项变成 7 个选项。或者 5 个。或者 20 个?呃,HG娱乐可以过会儿决定。」

层次聚類类似于常规的聚類,只是你的目标是构建一个聚類的层次。如果你最终的聚類数量不确定,那这种方法会非常有用。比如说,假设要给 Etsy 或亚马逊等网络市场上的项目分组。在主页上,你只需要少量大组方便导航,但随着你的分类越来越特定,你需要的粒度水平也越来越大,即区别更加明显的项聚類。

在算法的输出方面,除了聚類分配,你也需要构建一个很好的树结构,以帮助你了解这些聚類之间的层次结构。然后你可以从这个树中选择你希望得到的聚類数量。

层次聚類的步骤如下:

  • 首先从 N 个聚類开始,每个数据点一个聚類。

  • 将彼此靠得最近的两个聚類融合为一个。现在你有 N-1 个聚類。

  • 重新计算这些聚類之间的距离。有很多可以办到这件事的方法(参见这个教程了解更多细节:https://home.deib.polimi.it/matteucc/Clustering/tutorial_html/hierarchical.html)。其中一种方法(平均连接聚類,average-linkage clustering)是将两个聚類之间的距离看作是它们各自元素之间所有距离的平均。

  • 重复第 2 和 3 步,直到你得到包含 N 个数据点的一个聚類。你就会得到如下图所示的树(也被称为树状图))。

  • 选择一个聚類数量,然后在这个树状图中划一条水平线。比如说,如果你想要 K=2 个聚類,你应该在距离大约为 20000 的位置画一条水平线,你会得到一个包含数据点 8、9、11、16 的聚類和包含其它数据点的另一个聚類。一般而言,你得到的聚類的数量就是水平线与树状图中的竖直线的交叉点的数量。

人人都能讀懂的無監督學習:什麽是聚類和降維?

更多有关层次聚類的详细信息,可参阅这个视频:https://www.youtube.com/watch?v=OcoE7JlbXvY

降維

「對于那些該砍去的非精髓部分的態度,並不是每天增加吸收,而是每日盡量排減。」——李小龍

降維看上去很像压缩。这是为了在尽可能保存相关的结构的同时降低数据的复杂度。如果你有一张简单的 128×128×3 像素的图像(长×宽×RGB 值),那么数据就有 49152 维。如果你可以给这个图像空间降維,同时又不毁掉图像中太多有意义的内容,那么你就很好地执行了降維。

HG娱乐将了解两种实际中很常用的降維技术:主成分分析和奇异值分解。

主成分分析(PCA)

首先,了解一點線性代數知識——看看空間(space)和基(base)。

你应该知道由原点 O(0,0) 和基向量 i(1,0) 与 j(0,1) 定义的坐标平面。事实上,你也可以选择一个完全不同的基础,其中的数学仍然有效。比如说,你可以保持原点仍然为 O,但选择 i'=(2,1) 和 j'=(1,2) 作为基向量。如果你有耐心计算一下,你会发现在 i', j' 坐标系统中标记为 (2,2) 的点在 i, j 系统标记为 (6, 6)。

人人都能讀懂的無監督學習:什麽是聚類和降維?

使用 Mathisfun 的「交互式笛卡尔坐标」绘制:https://www.mathsisfun.com/data/cartesian-coordinates-interactive.html

这意味着HG娱乐可以修改空间的基础。现在想象有更高维度的空间,比如有 5 万维。你可以为这个空间选择一个基础,然后根据这个基础仅选择 200 个最重要的向量。这些基向量被称为主成分,而且你可以选择其中一个子集构成一个新空间,它的维度比原来的空间少,但又保留了尽可能多的数据复杂度。

要選擇出最重要的主成分,HG娱乐需要檢查這些數據的方差,並按這個指標給它們排序。

理解 PCA 的另一个思路是 PCA 将HG娱乐数据中存在的空间重映射成了一个更加紧凑的空间。这种变换后的维度比原来的维度更小。

仅需使用重映射空间的前几个维度,HG娱乐就可以开始理解这个数据集的组织结构。这就是降維的目的:减少复杂度(即这里的维度),同时保留结构(方差)。这里有篇 Samer 写的论文,介绍了使用 PCA(以及扩散映射等技术)试图理解维基解密披露的电报:http://mou3amalet.com/cargocollective/675_xuesabri-final.pdf

奇異值分解(SVD)

假设HG娱乐将HG娱乐的数据表示成一个 A=m×n 的大型矩阵。SVD 让HG娱乐可以将这个大型矩阵分解成 3 个较小的矩阵的乘积;这 3 个矩阵分别是 U=m x r、对角矩阵 Σ=r x r、V=r x n,其中 r 是一个很小的值。

人人都能讀懂的無監督學習:什麽是聚類和降維?

在这个 r×r 的对角矩阵 Σ 中的值被称为奇异值。这些值的奇妙之处是可以被用于压缩原来的矩阵,如果你丢弃奇异值中最小的 20% 以及矩阵 U 和 V 中相关的列,你就可以节省大量空间,同时仍然能很好地表征原来的矩阵。

爲了更准確地了解其中的含義,HG娱乐來看看一張小狗的圖片:

人人都能讀懂的無監督學習:什麽是聚類和降維?

HG娱乐将使用 Andrew Gibiansky 写的关于 SVD 的文章中代码:http://andrew.gibiansky.com/blog/mathematics/cool-linear-algebra-singular-value-decomposition/。首先,HG娱乐发现如果HG娱乐根据大小排序这些奇异值(矩阵 Σ 的值),那么前 50 个奇异值将包含整个矩阵 Σ 的大小的 85%。

人人都能讀懂的無監督學習:什麽是聚類和降維?

根据这个事实,HG娱乐可以丢弃后面的 250 个值(即将它们设为 0),仅保留这张小狗图像的「rank(秩)50」版本。这里,HG娱乐创建了秩为 200、100、50、30、20、10 和 3 的小狗照片。显然,照片变小了。但假设HG娱乐认为秩为 30 的小狗仍然很好,现在让HG娱乐看看HG娱乐实现了多少压缩。

原先的图像矩阵有 305*275 = 83,875 个值,秩为 30 的图像则有 305*30+30+30*275=17,430 个值。值的数量差不多少了 5 倍,但质量却下降很少。上述计算的原因是当HG娱乐执行 UΣ'V 运算时,U 和 V 矩阵中的一部分因为乘 0 也被丢弃(其中 Σ' 是 Σ 的修改后版本,其中仅包含了前面的 30 个值)。

人人都能讀懂的無監督學習:什麽是聚類和降維?

无监督学习常常被用于数据预处理。一般而言,这意味着以某种平均-保留的方式压缩数据,比如 PCA 或 SVD;之后,这些数据可被用于深度神经网络或其它监督式学习算法。

轉載36氪:http://36kr.com/p/5090797.html