六种常见聚类算法

六种常见聚类算法六种常见聚类算法

六种常见聚类算法六种常见聚类算法

目录

Kmeans

DBSCAN-基于密度的空间聚类算法

谱聚类

GMM-高斯混合模型

MeanShift-均值迁移

层次聚类

代码

Kmeans

聚类原则:以空间中k个点为中心进行聚类,对最靠近他们的对象归类。逐次计算各簇中心的值为新的中心值,迭代更新,直至簇中心位置不再改变或者达到最大迭代次数。

Kmeans的目标函数

定义为:各簇成员到其簇首的距离的平方和最小,如下所示

六种常见聚类算法

式中,C为簇首(聚类中心)集合,共有K个簇首。计算目标函数梯度,令梯度为0,计算簇首 C

六种常见聚类算法

式中l(x)表示簇成员个数。通过迭代优化目标函数来计算最佳参数 C。由上式得,在每次迭代中需更新聚类中心为每个簇的簇心即簇成员的均值。

算法流程:

  1. 适当选择k个类的初始中心;
  2. 在第n次迭代中,对任意一个样本,求其到k个中心的距离,将该样本归到距离最短的中心所在的类/簇;
  3. 利用均值等方法更新该类的中心值;
  4. 对于所有的k个聚类中心,如果利用(2)(3)的迭代法更新后,聚类中心的位置保持不变,则迭代结束;否则,则继续迭代。

优点

速度快,简单

缺点

  1. 适合聚类球状类簇,不能发现一些混合度较高,非球状类簇
  2. 需指定簇个数
  3. 算法结果不稳定,最终结果跟初始点选择相关,容易陷入局部最优
  4. 对噪声或离群点比较敏感:无法区分出哪些是噪声或者离群点,只能给每个数据点都判断出一个类别来,这样会导致样本质心偏移,导致误判或者聚类紧密程度降低。

六种常见聚类算法六种常见聚类算法
  • kmeans算法结果易受初始点影响
    由于kmeans算法结果易受初始点影响,得到的结果是局部最优,为次,我们可以运行n次kmeans算法,每次运行的初始点均为随机生成。然后在n次运行结果中,选取目标函数(代价函数)最小的聚类结果。
  • 聚类数量k如何确定?
    通常在数据集有多少个聚类是不清楚的。对于低维的数据,对其可视化,我们可以通过肉眼观察到有多少个聚类,但这样并不准确,而且大部分数据也无法可视化显示。方法1:我们可以通过构建一个代价函数与聚类数量k的关系图,如下图所示,横坐标是聚类数量,每个聚类数量对应的代价函数J均是n次运行的最优结果。观察下图,代价函数随聚类数量增大而减小,但并不是说聚类数量越多越好,比如:对于m个样本,m个聚类的代价函数自然是0,但这样根本不合理。观察下图,代价函数在没有到拐点之前下降很快,拐点之后下降变缓,我们就可以考虑选择这个拐点对应的数量作为聚类数量,这是一种较为合理的方法,但受限于能否得到一个清晰的拐点,如右下图所示,
  • 六种常见聚类算法六种常见聚类算法
    方法2:结果导向。我们使用kmeans算法的目的是什么?来确定k值能更好的服务于后续的目的。根据业务需求,多少个类别能够满足需求,效果更好来确定聚类数量。

DBSCAN-基于密度的空间聚类算法

聚类原则:聚类距离簇边界最近的点

算法流程:

核心点:核心点的半径范围内的样本个数≥最少点数

边界点:边界点的半径范围内的样本个数小于最少点数大于0

噪声点:噪声点的半径范围的样本个数为0


1. 根据半径、最少点数区分核心点、边界点、噪声点
2.先对核心点归类:
     while:
           随机选取一核心点作为当前簇
           寻找距离当前簇最近的核心点:与簇边缘最近的核心点,,
           if 若该核心点距离当前簇的边界核心点的距离小于半径:
              则将该核心点归类到当前簇
           if 若剩余的未归类的核心点距离当前簇边界距离均大于半径:
              说明:距离第numC个簇最近的核心点不在该簇邻域内,说明第numC个簇已全部分类完毕,可以
              生成新簇来归类核心点,则在剩余的未归类的核心点随机选取一核心点归类到新的簇中
           if 核心点已全部归类:
              停止迭代
3. 再根据半径和已归类的核心点来归类边界点

六种常见聚类算法

优点

能够识别任意形状的样本. 该算法将具有足够密度的区域划分为簇,并在具有噪声的空间数据库中发现任意形状的簇,它将簇定义为密度相连的点的最大集合。

缺点

需指定最少点个数,半径(或自动计算半径)

谱聚类

是从图论中演化出来的算法,后来在聚类中得到了广泛的应用。它的主要思想是把所有的数据看做空间中的点,这些点之间可以用边连接起来。距离较远的两个点之间的边权重值较低,而距离较近的两个点之间的边权重值较高。通过对所有数据点组成的图进行切图,让切图后不同的子图间边权重和尽可能的低,而子图内的边权重和尽可能的高,从而达到聚类的目的。

六种常见聚类算法

算法流程:

  1. 生成邻接矩阵(权重矩阵/相似度矩阵):W:m*m,用高斯函数度量样本之间的距离,距离越远,权重越小六种常见聚类算法
  2. 生成度量矩阵D:m*m,D=np.diag(np.sum(W,axis=1))、拉普拉斯矩阵L:L=D-W
  3. 标准化拉普拉斯矩阵:Ncut切图:L_norm=D^(-0.5)LD^(-0.5),注意:这里是矩阵叉乘六种常见聚类算法
  4. 生成标准化拉普拉斯矩阵对应的特征值和特征向量,对特征值排序(升序),选取前k个最小的特征值对应的特征向量,组成m*k矩阵data
  5. 对降维后的矩阵data使用kmeans、GMM或其他聚类方法来聚类

拉普拉斯映射

简单说,谱聚类其实就是使用了一种映射方法,将原有数据映射到新的数据空间,使得原数据中空间位置接近的样本在映射后更加接近,这种映射称为拉普拉斯映射。注意:步骤4中是选取最小的k个特征值对应特征向量, 那么问题来了,为什么要选取最小特征值呢?特征值有什么物理意义呢?

对于一个方阵(L为对称矩阵也是方阵且是半正定矩阵),可以称之为变换矩阵,当它叉乘某一个向量时,其物理意义为对该向量作 旋转和缩放的变换,即将原有向量所在的空间映射到一个新的空间。那么,缩放尺度如何度量?可以用变换矩阵的特征值来度量,如下所示 A为变换矩阵,向量 αA的特征向量(对于特征向量,对其变换时,只做缩放变换,其向量方向不变,更多详细内容见看图就懂:线性代数之特征值分解与奇异值分解),λ为特征值, I为单位向量,向量 α左乘 A等于对特征向量缩放λ倍。

六种常见聚类算法

特征值在物理意义上可以表示为缩放倍数,特征值越大,对应的特征向量放大倍数越大,而特征向量越大,对应的样本点映射后在空间位置上也更分散,而谱聚类或者拉普拉斯特征映射的目标就是将原本比较接近的点在映射后更加接近,使得属于不同簇的样本的 可分离性变强,所以拉普拉斯特征映射自然要选择小特征值对应的空间,这样也就实现了原数据中空间位置接近的样本在映射后更加接近。 如下图是原始特征空间与拉普拉斯特映射后的样本空间(2d、3d显示)的聚类结果

六种常见聚类算法 六种常见聚类算法

六种常见聚类算法 六种常见聚类算法

六种常见聚类算法

六种常见聚类算法 六种常见聚类算法

六种常见聚类算法

PCA

经过拉普拉斯映射后样本的可分离性比较好,易于聚类。于此相对的是,PCA降维选用的降序特征值即选取 最大的k个特征值对应的特征向量,因为PCA的目的是对原数据作旋转变换,将原数据映射到特征基(关于特征基概念见看图就懂:线性代数之特征值分解与奇异值分解),投影到特征基方向上的样本相对比较分散,如下图所示,二维原数据旋转到二维特征基上和降到1维效果图

六种常见聚类算法

总之,特征值越大对应的向量空间方差越大,即向量方向上的数据越分散。降维数据肯定会丢失一部分信息,PCA适用于处理高维数据,可以在尽可能保留更多信息的同时对高维数据降维处理,如何保留更多数据信息呢?某种意义上,数据分布越分散(方差)或者说越混乱(熵),能得到的信息越多,PCA通过将数据映射到特征基上(特征基不止一个),然后从中选取k个方差最大的特征基(k个最大特征值对应的特征向量)组成新的特征空间,从而实现降维+保留大部分信息效果。

拉普拉斯映射与PCA区别

设有原数据X,为m行n列数据、m个样本n个特征,k为维度个数:

  1. 拉普拉斯映射是根据 样本的相似矩阵作变换得到新的 样本空间六种常见聚类算法,这个新样本空间六种常见聚类算法可以直接用来聚类。
  2. PCA是根据 特征(变量)的 协方差矩阵作变换得到一个 变换矩阵六种常见聚类算法,然后使用该变换矩阵映射原数据得到:六种常见聚类算法
  3. 拉普拉斯映射提取升序特征值对应的特征向量,PCA提取降序特征值对应的特征向量

优点

谱聚类能够识别任意形状的样本空间且收敛于全局最优解,其基本思想是利用样本数据的相似矩阵(拉普拉斯矩阵)进行特征分解后得到的特征向量进行聚类。

谱聚类只需要数据之间的相似度矩阵,因此对于处理稀疏数据的聚类很有效。由于使用了降维,因此在处理高维数据聚类时的复杂度比传统聚类算法好

缺点

如果最终聚类的维度非常高,则由于降维的幅度不够,算法的运行速度和最终聚类效果均不好

聚类效果依赖于相似度矩阵(权重矩阵/邻接矩阵),不同的相似度矩阵得到的最终聚类效果可能差别很大

需指定聚类个数,高斯参数。

GMM-高斯混合模型

高斯混合混合模型(GMM)是一种概率生成模型,模型通过学习先验分布后推导后验分布来实现聚类。当我们做聚类任务的时候,可以根据距离最近原则,将样本聚类到距离其最近的聚类中心,如k-means算法,或者将样本聚类到距离某个簇边缘最近的簇,如DBSCAN算法,而GMM是假设样本每个类的特征分布遵循高斯分布,即整个数据集可由不同参数的高斯分布线性组合来描述,GMM算法可以计算出每个样本属于各个簇的概率值并将其聚类到概率值最大的簇。

GMM如何实现?

GMM是以假设数据各个类别的特征分布是高斯分布为基础,所以首要步骤就是先得到各个类别的概率分布密度函数参数,对于一元变量,需要计算各个类别的均值和期望,而对于多元变量,则需要计算均值和协方差矩阵。有如下数据集 X,共有m个样本,n项特征,k个类别

六种常见聚类算法

高斯概率分布密度函数公式如下:

六种常见聚类算法

一元变量:n=1

六种常见聚类算法

多元变量:n>1

六种常见聚类算法

式中,

六种常见聚类算法表示协方差矩阵,n行n列矩阵,六种常见聚类算法表示计算第k个类别的协方差矩阵的行列式。

现有如下数据集,如何使用GMM聚类?

六种常见聚类算法六种常见聚类算法

在学习GMM聚类算法前,先从大学概率论课本上的一个例子入手。

例如:投掷一颗骰子,实验的样本空间为:S={1,2,3,4,5,6}。

存在以下事件

  • 事件X={投掷一个骰子出现i点},
  • 事件六种常见聚类算法={投掷一个骰子出现偶数点},
  • 事件六种常见聚类算法= {投掷一个骰子出现奇数点},

六种常见聚类算法 是样本空间S的一个划分每做一次实验时,事件 必有一个且仅有一个发生。则有

六种常见聚类算法

证明过程如下:

六种常见聚类算法

则事件X={投掷一个骰子出现i点}的概率p(X)为

六种常见聚类算法

式中的

六种常见聚类算法称为先验概率,进一步得到以下公式: 贝叶斯公式

六种常见聚类算法

综上我们可以得到,投掷一颗骰子后,发生事件

六种常见聚类算法的概率为

六种常见聚类算法

回到聚类任务中,上述 事件X={投掷一个骰子出现i点}其实就是我们的训练集对应 X,事件

就是类别,对应 y。如下所示:

六种常见聚类算法

p(X)是训练集样本出现的概率,公式如下:

六种常见聚类算法

GMM代价函数

GMM首先需要计算每个类别的分布函数的参数,如何估计参数呢?可以采用 极大似然估计方法。

极大似然估计,就是利用已知的样本信息,反推最具有可能(最大概率)导致这些样本出现的模型参数值。换句话说,极大似然估计提供了一种通过给定观察数据来估计模型参数的方法,即:模型已定,参数未知。可以这样理解,既然事情(样本)已经发生了,为什么不让这个结果出现的可能性最大呢?这也就是极大似然估计核心。

通过极大似然估计方法来使样本出现的概率p(X)最大从而得到分布函数参数,这样我们可以得到代价函数

六种常见聚类算法

由于连乘可能会导致下溢,所以需要取对数。对数函数是一个严格递增的函数,取对数后不会改变数据的相对关系,即对数化后,我们仍然可以获得具有相同临界点的最优化函数,代价函数如下所示

六种常见聚类算法

已知多元变量的高斯分布公式如下

六种常见聚类算法

可以得到

六种常见聚类算法

注意,式中

六种常见聚类算法 ,这里直接用概率分布密度函数表示概率分布可能有一定误导性。为什么这样表达呢?如下

六种常见聚类算法

六种常见聚类算法是每个类的一个常量乘法因子,在之后的对后验概率六种常见聚类算法进行规范化的时候就抵消掉了。因此可以直接使用六种常见聚类算法来估计类条件概率六种常见聚类算法

综上,GMM代价函数的最终公式如下

六种常见聚类算法

通过求解代价函数,就可以得到各个类别的高斯分布函数参数,进而能计算样本属于某个类别的概率,从而实现聚类,公式如下

六种常见聚类算法

以上过程其实就是一个建模过程,建模过程包括如下

  1. 分析业务类型(聚类问题),√
  2. 确定模型类型(非参数+概率+生成模型),√
  3. 确定代价函数,√
  4. 目标函数:超参数
  5. 优化模型:调参

在得到代价函数后,我们还要确定这个代价函数是否具有凸性,因为凸函数有一个好性质,若代价函数是凸函数,则其局部最优解也是全局最优解。若无法得到凸代价函数,则尝试更换模型或者使用迭代算法来逼近全局最优解。

目标函数一般是代价函数+正则项,用来确定超参数,防止过拟合,来提高模型泛化能力。本文这里先跳过这一步,直接讲如何计算参数

六种常见聚类算法

使用EM算法计算GMM参数

EM(期望最大)算法是一个迭代算法,其思想就是多次迭代来估计参数,直到算法收敛。EM算法就是一个迭代逼近过程,若目标函数为非凸函数,则EM算法不能保证收敛至全局最优解,且EM算法的求解结果与初值的选择有较大关系,该算法对初值敏感。

EM算法求解参数思路可以将其理解为对两个未知变量的方程求解。首先固定其中一个未知数,求另一个未知数的偏导数,之后再反过来固定后者,求前者的偏导数,反复迭代直到目标函数值不变、收敛。EM算法就是相互迭代,求出一个稳定值,用于在无法直接找到参数的情况下寻找模型的最大似然估计(MLE)。它包括两个步骤:期望步骤和最大化步骤。在聚类问题中,步骤如下

  1. 初始化参数:混合高斯分布函数参数六种常见聚类算法
  2. 根据估计的参数计算簇成员后验概率:六种常见聚类算法
  3. 最大化步骤:代价函数代入六种常见聚类算法,求参数偏导,更新每一个参数六种常见聚类算法
    (六种常见聚类算法分别可以只用一个未知量六种常见聚类算法来表达)
  4. 重复1、2步骤直到对数似然值收敛。

具体步骤如下

1、初始化参数

六种常见聚类算法,根据估计参数计算给定数据点六种常见聚类算法属于六种常见聚类算法类别的概率(后验概率):
六种常见聚类算法
2、最大化步骤:对代价函数求偏导, 根据第一步得到的六种常见聚类算法 来更新每一个参数,六种常见聚类算法
六种常见聚类算法
六种常见聚类算法
3、重复1、2步骤,直到算法收敛。

参数推导过程

六种常见聚类算法可通过对代价函数求偏导得到,过程比较复杂,所以本文从另一个角度来解释参数的计算过程。

关于均值μ:

六种常见聚类算法

六种常见聚类算法

关于协方差矩阵如何计算:给定如下训练集X:m*2,假设有k个类别,则

六种常见聚类算法

六种常见聚类算法

六种常见聚类算法

GMM的代价函数是最大化数据 X出现的概率p(X)。若多次迭代后的p(X)保持不变,则说明程序已收敛。在得到参数

六种常见聚类算法,即得到数据集每个类别的概率分布函数,就可以计算每个样本属于各个类别的概率,样本选择最大的概率值对应的聚类中心,从而实现聚类。

六种常见聚类算法

GMM算法优缺点

优点

GMM假设生成数据的是一种混合的高斯分布,为模型找到最大似然估计。与将数据点硬分配到聚类的K-means方法(假设围绕质心的数据呈圆形分布)相比,它使用了将数据点软分配到聚类的方法(即概率性,因此更好)。速度:它是混合模型学习算法中的最快算法;无偏差性:由于此算法仅最大化可能性,因此不会使均值趋于零,也不会使聚类大小具有可能适用或不适用的特定结构。
(A)通过使用软分配捕获属于不同聚类的数据点的不确定性,(B)对圆形聚类没有偏见。即使是非线性数据分布,它也能很好地工作,具有较强的鲁棒性

缺点

  • 奇异性:当每个混合模型的点数不足时,估计协方差矩阵将变得困难,并且除非对协方差进行人为正则化,否则该算法会发散并寻找无穷大似然函数值的解。GMM:需要求逆
  • 分量数量:该算法将始终使用它可以使用的所有分量,所以在没有外部提示的情况下,需要留存数据或者信息理论标准来决定用多少个分量。
  • 适合聚类球状类簇,不能发现一些混合度较高,非球状类簇
  • 需要指定簇个数

MeanShift-均值迁移

该算法也叫做均值漂移,在目标追踪中应用广泛。本身其实是一种基于密度的聚类算法。

1、算法思路:

主要思路是:计算某一点A与其周围半径R内的向量距离的平均值M即迁移向量,更新该点下一步的迁移位置(A=M+A)。当该点不再移动时(norm(Mnew-Mold)

Original: https://blog.csdn.net/qingtianhaoshuai/article/details/123861759
Author: TingXiao-Ul
Title: 六种常见聚类算法



相关阅读

Title: 【论文笔记】KGCN:知识图谱 + 图卷积神经网络的推荐系统

Knowledge Graph Convolutional Networks for Recommender Systems
Hongwei Wang, Miao Zhao, Xing Xie, Wenjie Li, Minyi Guo.

In Proceedings of The 2019 Web Conference (WWW 2019)

论文原文(arXiv):https://arxiv.org/pdf/1904.12575v1.pdf
源码:https://github.com/hwwang55/KGCN(tensorflow / official)** https://github.com/zzaebok/KGCN-pytorch(pytorch)

1 introduction

(先日常嘲协同过滤系算法

协同过滤类的方法(CF-based methods)存在一定的不足之处,例如数据稀疏与冷启动问题。为缓解部分问题,当前大多采用知识图谱(KG)的思路,即将物品属性,用户信息,社交网络关系等多种可以辅助决策的属性(attribute)通过知识图谱的方式结合,以得到能够较好融合 side information 的网络,并同时建立各个实体之间,实体与属性之间的关系。

知识图谱,在此多以异构信息网络的形式,主要有以下几个优点:

  • 利用更多的 side information 数据信息以帮助决策,可以更好地发掘用户的潜在兴趣
  • 此时各个实体之间存在多种多样的关系,能够帮助提高用户推荐的多样性(diversity)
  • 推荐结果具有较好的解释性

然而将知识图谱与推荐系统本身进行融合的工作本身面临诸多挑战,当前大多使用 embedding 的方法进行融合(KGE),即将各个实体与关系转化为一定维度的向量表示(主流模型参考这里),但存在训练目标与下游任务不匹配的问题:以 Trans 系算法为例,在进行 embedding 时的训练往往基于头结点,关系与尾结点的运算关系,更适用于单纯基于 KG 的下游任务,而和推荐系统最终推荐 / 点击预测的目标是不匹配的。

同理,基于路径的方法同样存在其问题,人工设计 meta-path 与 meta-graph 往往要求一定的专家建议,且有效性与全面性难以得到保证(KDD2017 这篇 就是典型的基于路径的方法,注意下游任务往往又是回到矩阵分解 / 分解因子机的)

其他方法,如 RippleNet 同样存在一定的问题(RippleNet 论文笔记戳这里):首先其降低了关系 R 的重要性,其直接的 v T R h v^TRh v T R h 的计算方式难以捕捉关系带来的信息;其次,随着整个 ripple 的范围的扩大,此时加入模型训练的实体会大幅增多,带来巨大的计算负担和冗余。

原文提出一种融合 KG 特点与图卷积神经网络的模型(KGCN),也就是在计算 KG 中某一个给定的 entity 的表示时,将邻居信息与偏差一并结合进来。主要体现出如下的优势:

  • 通过邻居信息的综合,可以更好地捕捉局部邻域结构(local proximity structure)并储存在各 entity 中
  • 不同邻居的权重取决于之间的关系和特定的用户 u,可以更好地体现用户的个性化兴趣,以展示 entity 的特点

2 模型解释

2.1 问题叙述

本质上还是基于知识图谱的推荐系统,考虑此时已经得到一个构造好的,由 (实体,关系,实体)的三元组组成的知识图谱,记作 G \mathcal{G}G

给定 用户 – 物品矩阵 Y Y Y(本身是一个稀疏矩阵) 和知识图谱 G \mathcal{G}G ,判断用户 u 是否会对物品 v 有兴趣,也就是需要学习到一个预测方程(prediction function):y ^ u , v = F ( u , v ∣ Θ , Y , G ) \hat{y}_{u,v} = \mathcal{F}(u,v | \text{ } \Theta,Y,\mathcal{G} )y ^​u ,v ​=F (u ,v ∣Θ,Y ,G ),这里的 Θ \Theta Θ 定义为整个模型的学习参数的集合。

2.2 KGCN layer

符号定义

  • N ( v ) N(v)N (v ):所有和实体 v 直接相连的(也就是一跳内的)所有实体的集合
  • r e i , e j r_{e_i, e_j}r e i ​,e j ​​:实体 ei 和 ej 之间的关系
  • 定义函数g g g:某个函数,可以使得R d × R d → R R^d \times R^d \to R R d ×R d →R(比如内积),用来计算用户 u 和某个关系 r 之间的分数:π r u = g ( r , u ) \pi_r^u= g(r,u)πr u ​=g (r ,u ),这里的d d d 是 KG 的 embedding 表示的维度。注意这里的现实含义可以理解为(计算用户对不同的关系的偏好程度),比如某个用户非常在意影片的演员,则他对于 star 这类的 relationship 会有更多的关注,也会更愿意看他喜欢的演员的电影;而对于不是很在意演员的用户,可能对导演 director 之类的 relationship 反而有更多的帮助,这里的 g 函数即用于衡量用户对于不同关系的偏好程度。

利用邻居信息的线性组合来刻画结点 v 的邻域信息,定义为:v N ( v ) u = ∑ e ∈ N ( v ) π r v , e u e v_{N(v)}^u = \sum_{e\in N(v)}{ \pi_{r_{v,e}}^u e}v N (v )u ​=e ∈N (v )∑​πr v ,e ​u ​e,注意这里的权重 π \pi π 同时和(v,e 两个结点之间的关系)和(此时对应的用户 u 的特点)有关。这里的权重也就是 v 对应的 N(v) 中的所有实体 e 和关系 r 的 g 函数得分再归一化,计算如下:π r v , e u = e x p ( π r v , e u ) ∑ e ∈ N ( v ) e x p ( π r v , e u ) \pi_{r_{v,e}}^u = \frac{exp(\pi_{r_{v,e}}^u)}{\sum_{e\in N(v)} {exp(\pi_{r_{v,e}}^u)}}πr v ,e ​u ​=∑e ∈N (v )​e x p (πr v ,e ​u ​)e x p (πr v ,e ​u ​)​

个人感觉这里实际上和 KGAT 的第二部分有点像(KGAT 论文笔记),在 KGAT 中以 v 结点周围的 N(v) (这里的 N(v) 是所有以 v 为头结点的三元组的集合)中的实体 e (也就是尾节点)的线性组合来表示 v,具体计算各个 e 的权重的时候用的是注意力机制,可以理解为,此时决定权重的是在关系 r 的空间上,要被表示的头结点和尾节点的相似程度。但是这里更多地考虑了当前关系 r 对于用户 u 的重要性(通过上面的得分函数 g)

控制邻居个数:注意可能会出现某一个结点 v 存在过多的邻居的情况,会为整体的模型的计算带来巨大的压力。此时定义一个超参数 K K K,对于每一个结点 v,只是选取 K 个邻居进行计算。也就是说,此时 v 的邻域表示记作v S ( v ) u v_{S(v)}^u v S (v )u ​,且满足:S ( v ) → { e ∣ e ∈ N ( v ) } , ∣ S ( v ) ∣ = K S(v) \to \lbrace e| e\in N(v)\rbrace \text{ },\text{ }\text{ } |S(v)| = \mathcal{K}S (v )→{e ∣e ∈N (v )},∣S (v )∣=K

将原 embedding 与邻域表示结合起来:这里提供了几个可以用的聚合器(aggregators):

六种常见聚类算法六种常见聚类算法
注意最后一个 neighbor 的聚合器直接就是利用邻域表示来代替 v 结点的表示。

预测层:得到各个结点的表示后,同理使用 u v 的内积搭配 sigmoid 函数作点击概率预测,就不再赘述了。

summary
下图为上面计算方法的一个示例,这里的 K = 2:

六种常见聚类算法
在参数迭代的过程中,比如对于第 h+1 次迭代,就是用第 h 次迭代时得到的实体 e 的 embedding 表示作为初始值,再更新计算当前结点 v 的邻域表示,再和第 h 次得到的 v 的邻域表示进行 aggregate,得到第 h+1 次结点 v 的邻域表示。

个人感觉这段就是很像 KGAT(KGAT 论文笔记),KGAT 是每轮参数迭代的时候也是通过多次迭代的方式(以一个超参数控制)融合多跳位置的信息,再扔进去预测;这里同理,比如第 2 次训练的时候,要用到 v 的邻域 e’ 的第一次训练的结果,而 e’ 的第一次训练的结果是包含了 e’ 的再邻域的,也就是此时将 v 的二跳的 entity 的信息综合到 v 中了,也就是可以实现多跳位置的信息的捕捉。具体看后面模型学习部分的算法流程,通过一个超参数 H 来确定要吸收几跳的信息。也就是将(得到邻域表示 + 原本表示 → 融合)的过程重复 H 遍,再往下一个流程走。

此时个人感觉最大的区别还是在(邻居的权重)的计算方式上,此时是通过一个和关系,和 u 有关的得分函数 g 来计算的;而 KGAT 是通过图注意力机制,考察的是在关系 r 这个空间上,尾节点 t 和头结点 h 之间的相似程度,越相似越容易得到更大的权重,但没有考虑不同 u 对于不同 r 的偏重是不同的。

; 2.3 模型学习

整体模型的损失函数:

六种常见聚类算法
注意,在衡量的时候本身一个用户 u 没有发生过行为的物品数量是要远远大于发生过行为的物品数量的,对于类别不平衡问题,这里采用的是负采样。本质上损失函数就是交叉熵函数,前面部分是考虑了负采样的分布的交叉熵损失函数(也就是最后的推荐行为的损失函数 = 预测用户是否会点击 = 二分类问题),最后带一个 L2 正则项减轻过拟合。

整体模型的迭代过程

六种常见聚类算法
这里的 M[h] 就是不断得到 v 对应的邻域,注意随着迭代的 h 的次数上升,是不断将多跳范围的信息都融合进入了 v 的 embedding 的。

3 测试

实验用的数据集:

六种常见聚类算法
注意这里的 K 都不是很大,一般只要选择一部分的邻居来计算邻域表示本身的效果就不错。同理 H 选取也不大,如果过多跳的信息融入,一方面是计算很大,另一方面会导致重合(也就是每一个 v 都是它为中心的一大块范围的信息的融合,则不同的 v 之间会有趋同的倾向,反而是向模型中引入了噪音)。

这里用 F1 和 AUC 来评价:

六种常见聚类算法
注意这里选择不同的 aggregator (上面给了三种选择)的结果还是存在一定的差异的,具体实验的时候还是都试试会比较好。

阅读仓促,存在错误 / 不足欢迎指出!期待进一步讨论~
转载请注明出处。知识见解与想法理应自由共享交流,禁止任何商用行为!

[En]

Please indicate the source of the reprint. Knowledge, opinions and ideas should be shared and exchanged freely, and any commercial behavior is prohibited!

Original: https://blog.csdn.net/m0_46522688/article/details/113770785
Author: HicSuntLeones
Title: 【论文笔记】KGCN:知识图谱 + 图卷积神经网络的推荐系统

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/191082/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

最近整理资源【免费获取】:   👉 程序员最新必读书单  | 👏 互联网各方向面试题下载 | ✌️计算机核心资源汇总