CTS矩阵算法的构建
Fred等人共协关系矩阵是一种有效的描述对象之间相似性的方法，其优势在于构造简单，但是却难以精确的描述对象之间的相似度．由此，我们选用了能得到数据点间更多相似性信息的连接三元组。
1.什么是CTS矩阵？
CTS矩阵是2010年Iam-on等提出来的一种用连接三元组方法构建的一种相似矩阵。互相关矩阵简单、易于构造，但是它只能得到少部分数据点之间的相似度，其他数据点之间的相似度都为0.为了得到更多数据点之间的相似度信息，Iam-on等人提出了一种新的基于连接的相似度矩阵构造方法：连接三元组方法。
2.CTS矩阵在聚类上的应用
该方法在聚类问题上的应用如图 1 所示, 圆形顶点代表数据点, 方形顶点代表簇集合中的簇, 如果数据点 xi ∈ Ckj , 则它们之间存在一条边. 对于簇集$x_i∈C^k_j$，则它们之间存在一条边。对于簇集合$π_2$和$π_3$来说，由于数据点$x_1$和$x_2$分别属于簇$C^2_1$和簇$C^3_1$，因此认为它们是相似的。而对于簇集合$π_1$，点$x_1$和$x_2$属于不同的簇，但如果这些簇是相似的，则它们之间也存在相似性。根据连接三元组，且簇$C^2_1$和簇$C^3_1$分别是这两个连接三元组的中心，因此，簇$C^1_1$和簇$C^1_2$是相似的，从而对簇集合$π_1$来说，$x_1$和$x_2$也是相似的。可见该方法扩充了数据点之间的相似性信息，有利于具有复杂结构的数据聚类。
3.CTS矩阵的构建
/构建CTS矩阵/
1: $W_{ij}\ \gets\ \frac{\left|X_i\cap X_j\right|}{\left|X_i\cup X_j\right|}$//计算连接簇i和簇j之间边的权重
2: $WCT_{ij}^k\ \gets\ min(w_{ik},w_{jk})$ //计算簇$i$和簇$j$之间的连接三元组的最小值
3: $WCT_{max}\ \gets max(C_i,C_j)$ //计算簇i和簇j之间的最大值
4: $Sim^{WCT}(i,j)\ \gets\frac{\sum_{k=1}^{q}{WCT}{ij}^k}{ {WCT}{max}}$ //计算簇i和簇j之间的相似度
5: $S_m\left(x_i,x_j\right)\ \gets1$,if $C(x_i)=C(x_j)$
6: $S_m\left(x_i,x_j\right)\ \gets\frac{1}{M}\sum_{m=1}^{M}{S_m(x_i,x_j)}$,else $C(x_i)≠C(x_j)$
4.python的代码
以iris的数据集为例进行使用python代码。
from sklearn.preprocessing import MinMaxScaler
from sklearn.semi_supervised import LabelPropagation
import numpy as np
import pandas as pd
def load_data():
# 文件地址
df = pd.read_csv('/Data/iris.data.csv', header=None)
x = df[df.columns[0:4]]
y = df[df.columns[-1]]
e = df.sample(frac=0.1)
x1 = e[e.columns[0:4]]
y1 = e[e.columns[-1]]
x = np.array(x)
y = np.array(y)
x1 = np.array(x1)
y1 = np.array(y1)
x = MinMaxScaler().fit_transform(x)
x1 = MinMaxScaler().fit_transform(x1)
return x, x1, y, y1
def lpa():
x, x1, y, y1 = load_data()
lpa = LabelPropagation()
lpa.fit(x1, y1)
y_pred = lpa.predict(x)
return y_pred
def relabel(E):
(n, M) = np.shape(E)
newE = np.zeros((n, M))
"""first clustering"""
ucl = np.unique(E[:, 0])
if max(E[:, 0] != len(ucl)):
for j in range(len(ucl)):
# 初始化第一个基聚类集合的类簇，打标签
newE[E[:, 0] == ucl[j], 0] = j + 1
# print(newE[E[:, 0] == ucl[j]])
# print(newE)
"""the rest of the clustering"""
for j in range(1, M):
ucl = np.unique(E[:, j])
# 进行对每个基聚类的类簇计算总和
# print(newE[:, 0:j])
# print(np.unique(newE[:, 0:j]))
prevCl = len(np.unique(newE[:, 0:j]))
for i in range(len(ucl)):
newE[E[:, j] == ucl[i], j] = prevCl + i + 1 # 进行+1操作是因为有一个是0的标签
# print(newE[E[:, j] == ucl[i], i])
no_allcl = max(np.unique(newE[:, -1]))
return newE, no_allcl
def weightCl(E):
"""
:param E:N-by-M matrix of cluster ensemble
:return:an weighted cluster matrix
"""
N = E.shape[0]
no_allcl = max(np.unique(E[:, -1]))
pc = np.zeros((N, int(no_allcl)))
for i in range(N):
for j in E[i, :]:
pc[i, int(j) - 1] = 1 # 矩阵表示数据点是否属于集群（1=y，0=n），行=数据，列=cluster
"查找每对群集的共享数据点数量==>intersect/union"
no_allcl = int(no_allcl)
wcl = np.zeros((no_allcl, no_allcl))
for i in range(no_allcl):
for j in range(i + 1, no_allcl):
tmp = sum((pc[:, i] + pc[:, j]) > 0)
if tmp > 0:
wcl[i, j] = sum((pc[:, i] + pc[:, j]) == 2) / tmp
wcl = wcl + wcl.T
return wcl
def cts(E, dc):
(n, M) = np.shape(E) # n是对象个数，M是基聚类个数
E, no_allcl = relabel(E)
wcl = weightCl(E)
# print(wcl)
no_allcl = int(no_allcl)
wCT = np.zeros((no_allcl, no_allcl))
maxCl = []
minCl = []
for i in range(M):
maxCl.append(int(max(np.unique(E[:, i]))))
minCl.append(int(min(np.unique(E[:, i]))))
for q in range(M):
for i in range(minCl[q], maxCl[q]):
Ni = wcl[i - 1, :]
aa = []
# print("i:", i-1)
# print("Ni:",Ni)
for j in range(i, maxCl[q]):
# print("j:", j)
Nj = wcl[j, :]
# print("Nj:", Nj)
for ii in range(len(Nj)):
aa.append(min(Ni[ii], Nj[ii]))
# print(aa)
wCT[i, j] = sum(aa)
# print(sum(aa))
lwCT = []
for i in range(len(wCT)):
wCT[:, i]
# print(wCT[:, i].tolist())
lwCT.append(max(wCT[:, i].tolist()))
# print(max(wCT[:, i].tolist()))
# print(lwCT)
# print(max(lwCT))
if max(lwCT) > 0:
wCT = wCT / max(lwCT)
wCT = wCT + wCT.T
for i in range(no_allcl):
wCT[i, i] = 1
S = np.zeros((n, n))
for m in range(M):
for i in range(0, n - 1):
for ii in range(i + 1, n):
if E[i, m] == E[ii, m]:
S[i, ii] = S[i, ii] + 1
else:
S[i, ii] = S[i, ii] + wCT[int(E[i, m]) - 1, int(E[ii, m]) - 1] * dc
S = S / M
S = S + S.T
for i in range(n):
S[i, i] = 1
return S
if __name__ == '__main__':
E = []
dc = 0.80 # decay factor, ranges [0,1]
for i in range(4):
E.append(list(lpa()))
E = np.array(E).T
S = cts(E, dc)
print(S)运行结果如下
[[1. 1. 1. ... 0. 0. 0. ]
[1. 1. 1. ... 0. 0. 0. ]
[1. 1. 1. ... 0. 0. 0. ]
...
[0. 0. 0. ... 1. 0.77106843 0.5393738 ]
[0. 0. 0. ... 0.77106843 1. 0.76830536]
[0. 0. 0. ... 0.5393738 0.76830536 1. ]]
