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

Question

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

我已经阅读了不同的算法，如 k-modes、ROCK、LIMBO，但是我想构建一个我的算法并将准确性和成本与其他算法进行比较。

我有 (m) 个训练集和 (n=22) 个特征

方法

我的方法很简单：

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

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

矩阵创建：

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

首先，您计算 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.

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（没有太多工作要做，您只需要以稍微不同的方式定义 jaccard 函数，即添加类型声明局部变量）。类似于：

cpdef double jaccard(set set1, set set2):
    cdef long intersection_len, union_len # or consider int 
    intersection_len = set1.intersection(set2)
    union_len = len(set1) + len(set2) - intersection_len
    return intersection_len / union_len

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

P.S。您可以使用 numpy 数组而不是 sets，因为它们提供了与 C/C++ 中的运行类似的交集方法，但是两个数组的交集大约需要 O (n^2) 时间，而两个哈希表（set 对象）的交集需要 O(n) 时间，前提是冲突率接近于零。

Answer 2

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

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

如果您尝试尽可能多地使用 numpy，您可能能够显着加快您的代码速度。或者，如果您改用 Cython。

考虑使用基于距离的聚类算法：

，而不是对抗质心

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

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

Clustering Categorical data using jaccard similarity

cluster-analysis

machine-learning

data-mining

k-means

python-2.7

方法

矩阵创建：

问题陈述：