根据图表颜色对相似度矩阵进行排序

Question

我有一些文档的相似性矩阵图。 我想对该numpynd数组的矩阵值进行排序，以分组颜色，同时保持它们的相对位置（对角线黄线）和标签。

path = "C:\\Users\\user\\Desktop\\texts\\dataset"
text_files = os.listdir(path)
#print (text_files)

tfidf_vectorizer = TfidfVectorizer()
documents = [open(f, encoding="utf-8").read() for f in text_files if f.endswith('.txt')]
sparse_matrix = tfidf_vectorizer.fit_transform(documents)

labels = []
for f in text_files:
    if f.endswith('.txt'):
        labels.append(f)

pairwise_similarity = sparse_matrix * sparse_matrix.T

pairwise_similarity_array = pairwise_similarity.toarray()
 
fig, ax = plt.subplots(figsize=(20,20))
cax = ax.matshow(pairwise_similarity_array, interpolation='spline16')
ax.grid(True)
plt.title('News articles similarity matrix')
plt.xticks(range(23), labels, rotation=90);
plt.yticks(range(23), labels);
fig.colorbar(cax, ticks=[0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1])
plt.show() 

- lynx

Answer 1

这里有一种可能性。 这个想法是利用相似矩阵中的信息，如果两个元素相似，就把它们放在一起。如果两个物品相似，它们在其他方面也应该是相似的，例如颜色。 我从与所有其他元素共同点最多的元素[a]开始（这个选择有点随意），然后从剩余的元素中选择距离当前元素最近的元素[b]作为下一个元素。

import numpy as np
import matplotlib.pyplot as plt

def create_dummy_sim_mat(n):
    sm = np.random.random((n, n))
    sm = (sm + sm.T) / 2
    sm[range(n), range(n)] = 1
    return sm

def argsort_sim_mat(sm):
    idx = [np.argmax(np.sum(sm, axis=1))]  # a
    for i in range(1, len(sm)):
        sm_i = sm[idx[-1]].copy()
        sm_i[idx] = -1
        idx.append(np.argmax(sm_i))  # b
    return np.array(idx)


n = 10
sim_mat = create_dummy_sim_mat(n=n)

idx = argsort_sim_mat(sim_mat)
sim_mat2 = sim_mat[idx, :][:, idx]  # apply reordering for rows and columns

# Plot results
fig, ax = plt.subplots(1, 2)
ax[0].imshow(sim_mat)
ax[1].imshow(sim_mat2)

def ticks(_ax, ti, la):
    _ax.set_xticks(ti)
    _ax.set_yticks(ti)
    _ax.set_xticklabels(la)
    _ax.set_yticklabels(la)

ticks(_ax=ax[0], ti=range(n), la=range(n))
ticks(_ax=ax[1], ti=range(n), la=idx)

---

在meTchaikovsky的回答之后，我也在聚类相似度矩阵上测试了我的想法（见第一张图片），这种方法可行但不完美（见第二张图片）。

因为我使用两个元素之间的相似度来近似它们与所有其他元素的相似度，所以很明显这并不能完美地工作。因此，可以计算一个“二阶”相似度矩阵来代替使用初始相似度来排序元素，该矩阵测量相似度的相似程度（抱歉）。这个度量更好地描述了您感兴趣的内容。如果两行/列具有相似的颜色，则它们应该靠近彼此。将矩阵排序的算法与以前相同。

def add_cluster(sm, c=3):
    idx_cluster = np.array_split(np.random.permutation(np.arange(len(sm))), c)
    for ic in idx_cluster:
        cluster_noise = np.random.uniform(0.9, 1.0, (len(ic),)*2)
        sm[ic[np.newaxis, :], ic[:, np.newaxis]] = cluster_noise

def get_sim_mat2(sm):
    return 1 / (np.linalg.norm(sm[:, np.newaxis] - sm[np.newaxis], axis=-1) + 1/n)

sim_mat = create_dummy_sim_mat(n=100)
add_cluster(sim_mat, c=4)
sim_mat2 = get_sim_mat2(sim_mat)

idx = argsort_sim_mat(sim_mat)
idx2 = argsort_sim_mat(sim_mat2)
sim_mat_sorted = sim_mat[idx, :][:, idx]
sim_mat_sorted2 = sim_mat[idx2, :][:, idx2]

# Plot results
fig, ax = plt.subplots(1, 3)
ax[0].imshow(sim_mat)
ax[1].imshow(sim_mat_sorted)
ax[2].imshow(sim_mat_sorted2)

使用第二种方法得出的结果相当不错（见第三张图片），但我猜测也会存在这种方法无法奏效的情况，所以我希望能得到反馈。

---

编辑

我曾试图解释并用 [a] 和 [b] 将代码与思路联系起来，但显然我做得不好，所以这里有一个更详细的解释。

你有 n 个元素和一个 n x n 的相似度矩阵 sm，其中每个单元格 (i, j) 描述了元素 i 与元素 j 之间的相似程度。目标是按照一定顺序排列行 / 列，以便可以看到相似度矩阵中存在的模式。我的想法非常简单。

你从一个空列表开始，并逐个添加元素。下一个元素的标准是与当前元素的相似性。如果上一步添加了元素 i，则选择元素 argmax(sm[i, :]) 作为下一个元素，忽略已添加到列表中的元素。通过将那些元素的值设置为 -1 来忽略它们。

你可以使用函数 ticks 来重新排序标签：

labels = np.array(labels)  # make labels an numpy array, to index it with a list
ticks(_ax=ax[0], ti=range(n), la=labels[idx])

- scleronomic

---

我在CV网站上找到了这篇帖子https://stats.stackexchange.com/a/138331/198896，它提供了一个不错的解决方案 :) - meTchaikovsky

@scleronomic +1 因为很酷的梗 :D - lynx

你能解释一下 def argsort_sim_mat(sm) 这段代码的含义吗？另外，我如何重新排序标签呢？ - lynx

Answer 2

“@scleronomic的解决方案非常优雅，但它也有一个缺点，即我们无法在排序后的相关矩阵中设置聚类数。假设我们正在处理一组变量，其中一些变量之间的相关性较弱。”

import string 
import numpy as np
import pandas as pd

n_variables = 20
n_clusters = 10
n_samples = 100

np.random.seed(100)
names = list(string.ascii_lowercase)[:n_variables]
belongs_to_cluster = np.random.randint(0,n_clusters,n_variables)

latent = np.random.randn(n_clusters,n_samples)
variables = np.random.rand(n_variables,n_samples)
for ind in range(n_clusters):
    mask = belongs_to_cluster == ind
    # weakening the correlation 
    if ind % 2 == 0:variables[mask] += latent[ind]*0.1
    variables[mask] += latent[ind]

df = pd.DataFrame({key:val for key,val in zip(names,variables)})
corr_mat = np.array(df.corr())

如您所见，这些变量是按照构造分为10个簇，但是簇内索引为偶数的变量之间的相关性较弱。如果我们只想在排序后的相关矩阵中看到大约5个簇，也许需要找到另一种方法。

根据这篇文章，它是问题“{{link2:如何将相关矩阵聚类}”的被接受答案，要将相关矩阵排序成块，我们需要找到内部相关性高、簇间相关性低的块。然而，该答案提供的解决方案最适用于我们已经知道有多少个块，且更重要的是，底层块的大小相同或至少相似。因此，我通过一个新函数sort_corr_mat改进了该解决方案。

def sort_corr_mat(corr_mat,clusters_guess): 
    
    def _swap_rows(corr_mat, var1, var2):
        rs = corr_mat.copy()
        rs[var2, :],rs[var1, :]= corr_mat[var1, :],corr_mat[var2, :]
        cs = rs.copy()
        cs[:, var2],cs[:, var1] = rs[:, var1],rs[:, var2]
        return cs

    # analysis
    max_iter = 500
    best_score,current_score,best_count = -1e8,-1e8,0
    num_minimua_to_visit = 20
    
    best_corr = corr_mat
    best_ordering = np.arange(n_variables)
    for i in range(max_iter):
        for row1 in range(n_variables):
            for row2 in range(n_variables):
                if row1 == row2: continue
                option_ordering = best_ordering.copy()
                option_ordering[row1],option_ordering[row2] = best_ordering[row2],best_ordering[row1]
                option_corr = _swap_rows(best_corr,row1,row2)
                option_score = score(option_corr,n_variables,clusters_guess)

                if option_score > best_score:
                    best_corr = option_corr
                    best_ordering = option_ordering
                    best_score = option_score

        if best_score > current_score:
            best_count += 1
            current_corr = best_corr
            current_ordering = best_ordering
            current_score = best_score
            
        if best_count >= num_minimua_to_visit:
            return best_corr#,best_ordering
        
    return best_corr#,best_ordering

通过这个函数和首先构建的`corr_mat`，我将使用我的功能（右侧）与@scleronomic's solution（中间）获得的结果进行比较。

sim_mat_sorted = corr_mat[argsort_sim_mat(corr_mat), :][:, argsort_sim_mat(corr_mat)]
corr_mat_sorted = sort_corr_mat(corr_mat,clusters_guess=5)

# Plot results
fig, ax = plt.subplots(1,3,figsize=(18,6))
ax[0].imshow(corr_mat)
ax[1].imshow(sim_mat_sorted)
ax[2].imshow(corr_mat_sorted)

显然，@scleronomic的解决方案 的效果更好、更快，但我的解决方案可以更好地控制输出的模式。

- meTchaikovsky

---

@kapelnick 你好kapelnick，我刚刚意识到我在原帖中链接的被接受的解决方案可能不是最优的，我进行了改进并更新了我的帖子，希望它能有所帮助 :) - meTchaikovsky

即使您更新了评分函数，它似乎仍然相当复杂，并且对聚类数的所需知识使其不太通用。您的方法是否比我的方法更有优势？我真的很感兴趣，因为您链接的问题还提到了其他主题的链接，如“双向聚类”或“相关聚类”，所有这些对我来说似乎都很复杂，但也许我只是错过了一点。 - scleronomic

@scleronomic 您的解决方案非常优雅，但我认为它仍然有一个小缺陷，即您无法控制排序相关矩阵中聚类的数量。 - meTchaikovsky

@scleronomic 感谢你们的努力。我接受了scleronomic的答案，因为他的代码对我来说更容易实现。 - lynx

@kapelnick 没问题，我完全支持你的决定。 - meTchaikovsky