使用jaccard相似度对分类数据进行聚类

Question

我正在尝试为分类数据构建聚类算法。

我已经阅读了有关k模式，ROCK，LIMBO等不同算法的信息，但是我想构建一个我的算法并将其准确性和成本与其他算法进行比较。

我有（m）个训练集和（n = 22）个功能

方法

我的方法很简单：

• 步骤1：我计算每个训练数据之间的jaccard相似度，形成（m * m）相似度矩阵。
• 步骤2：然后，我执行一些操作以找到最佳质心，并使用简单的k均值方法找到聚类。

我在步骤1中创建的相似度矩阵将在执行k-means算法时使用

矩阵创建：

total_columns=22
for i in range(0,data_set):
    for j in range(0,data_set):
        if j>=i:
            # Calculating jaccard similarity between two data rows i and j 
            for column in data_set.columns:    
                if data_orig[column][j]==data_new[column][i]:
                    common_count=common_count+1
            probability=common_count/float(total_columns)    
            fnl_matrix[i][j] =probability  
            fnl_matrix[j][i] =probability

我的fnl_matrix（6行）的部分快照如下：

问题陈述：

我面临的问题是，当我创建（m * m）矩阵时，对于较大的数据集，我的性能会受到影响。即使对于具有8000行的较小数据集，相似度矩阵的创建也花费了难以忍受的时间。有什么办法可以调整我的代码或对矩阵做一些节省成本的事情。

Answer 1

解释Python代码很慢。真的很慢。

这就是为什么优秀的 Python 工具包包含大量 Cython 代码，甚至 C 和 Fortran 代码（例如 numpy 中的矩阵运算），并且仅使用 Python 来驱动整个过程。

如果您尝试尽可能多地numpy使用. 或者如果您使用 Cython 代替。

考虑使用基于距离的聚类算法，而不是与质心作斗争：

• 层次凝聚聚类 (HAC)，需要距离矩阵
• DBSCAN，可以在任意距离下工作。它甚至不需要距离矩阵，只需要某个阈值的相似项目列表。
• K-medoids/PAM 当然也值得一试；但通常不是很快。

Answer 2

首先，计算Jaccard的方法似乎效率很低（如果不是错误的话）。您正在使用for循环，这可能是在Python中完成工作的最慢方法。我建议您利用Python set来存储行。集提供了快速交集，因为它们是哈希表，并且所有计算都是在C / C ++中执行的，而不是在Python本身中执行的。想象一下r1，r2是两行。

r1 = set(some_row1)
r2 = set(some_row2)
intersection_len = len(r1.intersect(r2))
union_len = len(r1) + len(r2) - intersection_len
jaccard = intersection_len / union_len

集的构造非常昂贵，因此您应该首先将所有行存储为集。那你应该摆脱

for i in range(0,data_set):
    for j in range(0,data_set):

部分。使用itertools代替。假设data_set是一个行列表。

for row1, row2 in itertools.combinations(data_set, r=2):
    ...

这东西运行得快得多，并且消除了if j>=i检查的需要。这样，您将获得矩阵的上三角。让我们来概述一下最终算法。更新：添加numpy。

for row1, row2 in itertools.combinations(data_set, r=2):
    ...

而已。您已经有了矩阵。从这一点出发，您可能会考虑使用此代码块并将其移植到Cython（没有太多工作要做，您只需要以jaccard稍微不同的方式定义函数，即为局部变量添加类型声明）。就像是：

from scipy.spatial import distance
from itertools import combinations
import numpy as np


def jaccard(set1, set2):
    intersection_len = set1.intersection(set2)
    union_len = len(set1) + len(set2) - intersection_len
    return intersection_len / union_len

original_data_set = [row1, row2, row3,..., row_m]
data_set = [set(row) for row in original_data_set]

jaccard_generator = (jaccard(row1, row2) for row1, row2 in combinations(data_set, r=2))
flattened_matrix = np.fromiter(jaccard_generator, dtype=np.float64)

# since flattened_matrix is the flattened upper triangle of the matrix
# we need to expand it.
normal_matrix = distance.squareform(flattened_matrix)
# replacing zeros with ones at the diagonal. 
normal_matrix += np.identity(len(data_set))

但我不确定该编译是否正确（我的Cython经验非常有限）

PS您可以使用numpy数组而不是sets，因为它们提供了相似的交集方法，并且也可以在C / C ++中运行，但是两个数组的交集大约需要O（n ^ 2）时间，而两个哈希表（set对象）的交集如果碰撞率接近零，则需要O（n）时间。