FFM (Field-aware Factorization Machines)

一.简介

通过引入field的概念,FFM把相同性质的特征归于同一个field。FFM相对于FM加入了field的概念,每个特征的隐向量不再是只有一个,而是针对每个field学习一个独立的隐向量,防止互相影响

二.原理

连续特征,一个特征就对应一个Field (也可连续特征离散化,一个分箱成为一个特征);  离散特征,采用one-hot编码,同一种属性的归到一个Field。

以上文的表格数据为例,计算用户1的FFM组合特征:

算一下𝑦̂ 𝑣1,𝑓2的偏导

注意𝑥2,𝑥3,𝑥4是同一个属性的one-hot表示,即𝑥2,𝑥3,𝑥4中只有一个为1,其他都为0 (对于每个样本来说,同一个field下只有一个feature的值不是0,其他feature的值都是0)。在本例中𝑥3=𝑥4=0, 𝑥2=1,所以:

推广到一般情况:

𝑥𝑗属于Field 𝑓𝑗,且同一个Field里面的其他𝑥𝑚都等于0。实际项目中𝑥是非常高维的稀疏向量,求导时只关注那些非0项即可。

三.参考

FM (Factorization Machine)

一. 应用场景

在计算广告领域,点击率CTR(click-through rate)和转化率CVR(conversion rate)是衡量广告流量的两个关键指标。准确的估计CTR、CVR对于提高流量的价值,增加广告收入有重要的指导作用。预估CTR/CVR,业界常用的方法有人工特征工程 + LR(Logistic Regression)、GBDT(Gradient Boosting Decision Tree) + LR、FM(Factorization Machine)和FFM(Field-aware Factorization Machine)

二.目的

旨在解决稀疏数据下的特征组合问题

三.优点

    • 高度稀疏数据场景;
    • 具有线性的计算复杂度。

四.原理

公示推导

    • 通过组合交叉的特性来学习特征为0样本的权重参数。每个参数 [公式] 的训练需要大量[公式] 和 [公式]都非零的样本;由于样本数据本来就比较稀疏,满足“[公式] 和 [公式]都非零”的样本将会非常少。训练样本的不足,很容易导致参数 [公式] 不准确,最终将严重影响模型的性能;[公式] 和 [公式]的系数分别为 [公式] 和 [公式] ,它们之间有共同项 [公式]即尽管 [公式]为0,但由于[公式]不为0 ,那么就可以通过[公式] 来学习[公式]。也就是说,所有包含“ [公式] 的非零组合特征”(存在某个 [公式] ,使得 [公式] )的样本都可以用来学习隐向量[公式],这很大程度上避免了数据稀疏性造成的影响。而在多项式模型中, [公式] 和 [公式] 是相互独立的。
    • 由于[公式]是对阵矩阵,也即半正定矩阵,这边当作正定矩阵近似求解,这个矩阵就可以分解为 [公式]
    • 由于[公式] 代表向量内积(点乘/数量积),具有对称性,即<a,b>=<b,a>,所以<x_i, x_j>为实对称矩阵,则是对称矩阵,而FM项 是这个对称矩阵的上三角部分(不包含对角线),所以FM项就等于减去对角线再除以2
    • FM的复杂度是 [公式] 。通过计算优化,FM的二次项可以化简,其复杂度可以优化到 [公式]

SGD梯度更新参数

 

其中, [公式] 代表样本的特征数量,[公式]是第 [公式] 个特征的值, [公式] 是模型参数,vi/vj隐向量的长度为 [公式]

五.参考

K-Means的K值确定

一、elbow method

x轴为聚类的数量,y轴为WSS(within cluster sum of squares)也就是各个点到cluster中心的距离的平方的和。

Elbow method就是“肘”方法,对于n个点的数据集,迭代计算k from 1 to n,每次聚类完成后计算每个点到其所属的簇中心的距离的平方和,可以想象到这个平方和是会逐渐变小的,直到k==n时平方和为0,因为每个点都是它所在的簇中心本身。但是在这个平方和变化过程中,会出现一个拐点也即“肘”点,盗了张图可以看到下降率突然变缓时即认为是最佳的k值。

def elbow_method(data2vec):
    distortions = []
    K = range(1, 31)
    for k in tqdm(K):
        clf = KMeans(n_clusters=k,
                     n_init=20,
                     init='k-means++', n_jobs=multiprocessing.cpu_count() - 1)  # n_init选择质心的次数,返回最好的结果
        km = clf.fit(data2vec)
        print('Fit over, begin to compute cdist.')
        distortions.append(sum(np.min(cdist(data2vec, km.cluster_centers_, 'euclidean'), axis=1)) / data2vec.shape[0])
    print(K)
    print(distortions)
    with open('result_elbow.txt', 'w') as f:
        for k in K:
            f.write(str(k) + ' ')
        f.write('\n')
        for dis in distortions:
            f.write(str(dis) + ' ')
        f.write('\n')

    # Plot the elbow
    plt.plot(k, distortions, 'bx-')
    plt.xlabel('k')
    plt.ylabel('Distortion')
    plt.title('The Elbow Method showing the optimal k')
    plt.show()

 

二、轮廓系数(Silhouette Coefficient)

在实际应用中,由于Kmean一般作为数据预处理,或者用于辅助分聚类贴标签。所以k一般不会设置很大。可以通过枚举,令k从2到一个固定值如10,在每个k值上重复运行数次kmeans(避免局部最优解),并计算当前k的平均轮廓系数,最后选取轮廓系数最大的值对应的k作为最终的集群数目。
轮廓系数取值范围为[-1,1],取值越接近1则说明聚类性能越好,相反,取值越接近-1则说明聚类性能越差。
    • a:某个样本与其所在簇内其他样本的平均距离
    • b:某个样本与其他簇样本的平均距离

def silhouette_score_method(data2vec):
    scores = []
    K = range(2, 31)
    best_k = None
    best_score = -1
    for k in tqdm(K):
        clf = KMeans(n_clusters=k,
                     n_init=20,
                     init='k-means++', n_jobs=multiprocessing.cpu_count() - 1)  # n_init选择质心的次数,返回最好的结果
        km = clf.fit(data2vec)
        print('Fit over, begin to compute silhouette_score.')
        labels = km.labels_
        score = metrics.silhouette_score(data2vec, labels, metric='cosine')
        scores.append(score)
        if score > best_score:
            best_k = k
            best_score = score
    print('Best k:', str(best_k), 'Best score:', str(best_score))
    with open('result_silhouette_score.txt', 'w') as f:
        for k in K:
            f.write(str(k) + ' ')
        f.write('\n')
        for score in scores:
            f.write(str(score) + ' ')
        f.write('\n')
        f.write('Best k: ' + str(best_k) + ' Best score: ' + str(best_score) + '\n')

三、Reference

文本聚类

一. 划分法(基于划分的聚类算法)

k-means(k的选取,大规模文本计算距离复杂度高)

大样本采取Mini Batch K-Means算法

二. 层次法(基于层次的聚类算法)

  • 自底向上(合并聚类)
    • 将语料库中的任一数据都当作一个新的簇,计算所有簇相互之间的相似度,然后将相似度最大的两个簇进行合并,重复这个步骤直到达到某个终止条件,因此合并聚类方法也被称为由下而上的方法。
  • 自顶向下(分裂聚类)
    • 先将数据集中所有的对象都归为同一簇,并将不断地对原来的簇进行划分从而得到更小的簇,直到满足最初设定的某个终止条件。
  • 优缺点
    • 优点
      1. 适用于发现任意形状的簇;
      2. 适用于任意形式的相似度或距离表示形式;
      3. 聚类粒度的灵活性。
    •  缺点
      1. 算法终止的条件很模糊,难以精确表达并控制算法的停止;
      2. 一旦聚类结果形成,一般不再重新构建层次结构来提高聚类的性能;
      3. 难以处理大规模数据,也不能适应动态数据集的处理。

三. DBSCAN(密度聚类)

  • 由密度可达关系导出的最大密度相连的样本集合,即为我们最终聚类的一个类别,或者说一个簇
  • 先从数据集w中找到任意一个对象q,并查找w中关于R和最小下限数MinPts的从q密度到达的所有对象。如果q是核心对象,也就是说,q半径为R的领域中包含的对象数不少于MinPts,则根据算法可以找到一个关于参数R和MinPts的类。如果q是一个边界点,即q半径为R的领域包含的对象数小于MinPts,则没有对象从q密度到达,q被暂时标注为噪声点。然后,DBSCAN处理数据集W中的下一个对象。

四. Single-pass(增量聚类)

其顺序处理文本,以第一篇文档为种子,建立一个新主题。之后再进行新进入文档与已有主题的相似度,将该文档加入到与它相似度最大的且大于一定阈值的主题中。如果与所有已有话题相似度都小于阈值,则以该文档为聚类种子,建立新的主题类别。适合大规模文本聚类

五.BIRCH聚类算法原理

适合于数据量大,类别数K也比较多的情况

  • 1) 将所有的样本依次读入,在内存中建立一颗CF Tree, 建立的方法略。
  • 2)(可选)将第一步建立的CF Tree进行筛选,去除一些异常CF节点,这些节点一般里面的样本点很少。对于一些超球体距离非常近的元组进行合并
  • 3)(可选)利用其它的一些聚类算法比如K-Means对所有的CF元组进行聚类,得到一颗比较好的CF Tree.这一步的主要目的是消除由于样本读入顺序导致的不合理的树结构,以及一些由于节点CF个数限制导致的树结构分裂。
  • 4)(可选)利用第三步生成的CF Tree的所有CF节点的质心,作为初始质心点,对所有的样本点按距离远近进行聚类。这样进一步减少了由于CF Tree的一些限制导致的聚类不合理的情况。