我正在尝试实现以下(分裂)聚类算法(下面是该算法的简短形式,完整的描述可用here https://dl.dropboxusercontent.com/u/540963/diana.pdf):
从样本 x, i = 1, ..., n 开始,将其视为由 n 个数据点组成的单个簇,并为所有点对定义相异矩阵 D。固定一个阈值T来决定是否分裂簇。
首先确定所有数据点对之间的距离,并选择它们之间距离 (Dmax) 最大的一对。
将 Dmax 与 T 进行比较。如果 Dmax > T,则使用所选对作为两个新簇中的第一个元素,将单个簇一分为二。剩余的 n - 2 个数据点被放入两个新簇之一。如果 D(x_i, x_l)
在第二阶段,在两个新簇之一中找到值 D(x_i, x_j),以找到簇中距离 Dmax 最大的一对。如果Dmax
输出是集群数据记录的层次结构。我恳请您提供如何实现聚类算法的建议。
EDIT 1:我附上定义距离(相关系数)的Python函数和查找数据矩阵中最大距离的函数。
# Read data from GitHub
import pandas as pd
df = pd.read_csv('https://raw.githubusercontent.com/nico/collectiveintelligence-book/master/blogdata.txt', sep = '\t', index_col = 0)
data = df.values.tolist()
data = data[1:10]
# Define correlation coefficient as distance of choice
def pearson(v1, v2):
# Simple sums
sum1 = sum(v1)
sum2 = sum(v2)
# Sums of the squares
sum1Sq = sum([pow(v, 2) for v in v1])
sum2Sq = sum([pow(v, 2) for v in v2])
# Sum of the products
pSum=sum([v1[i] * v2[i] for i in range(len(v1))])
# Calculate r (Pearson score)
num = pSum - (sum1 * sum2 / len(v1))
den = sqrt((sum1Sq - pow(sum1,2) / len(v1)) * (sum2Sq - pow(sum2, 2) / len(v1)))
if den == 0: return 0
return num / den
# Find largest distance
dist={}
max_dist = pearson(data[0], data[0])
# Loop over upper triangle of data matrix
for i in range(len(data)):
for j in range(i + 1, len(data)):
# Compute distance for each pair
dist_curr = pearson(data[i], data[j])
# Store distance in dict
dist[(i, j)] = dist_curr
# Store max distance
if dist_curr > max_dist:
max_dist = dist_curr
EDIT 2:下面粘贴的是 Dschoni 答案中的函数。
# Euclidean distance
def euclidean(x,y):
x = numpy.array(x)
y = numpy.array(y)
return numpy.sqrt(numpy.sum((x-y)**2))
# Create matrix
def dist_mat(data):
dist = {}
for i in range(len(data)):
for j in range(i + 1, len(data)):
dist[(i, j)] = euclidean(data[i], data[j])
return dist
# Returns i & k for max distance
def my_max(dict):
return max(dict)
# Sort function
list1 = []
list2 = []
def sort (rcd, i, k):
list1.append(i)
list2.append(k)
for j in range(len(rcd)):
if (euclidean(rcd[j], rcd[i]) < euclidean(rcd[j], rcd[k])):
list1.append(j)
else:
list2.append(j)
EDIT 3:当我运行 @Dschoni 提供的代码时,算法按预期工作。然后我修改了create_distance_list
函数,以便我们可以计算多元数据点之间的距离。我使用欧几里德距离。对于玩具示例,我加载iris
数据。我仅对数据集的前 50 个实例进行聚类。
import pandas as pd
df = pd.read_csv('https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data', header = None, sep = ',')
df = df.drop(4, 1)
df = df[1:50]
data = df.values.tolist()
idl=range(len(data))
dist = create_distance_list(data)
print sort(dist, idl)
结果如下:
[[24]、[17]、[4]、[7]、[40]、[13]、[14]、[15]、[26、27、38]、[3、16、
39]、[25]、[42]、[18、20、45]、[43]、[1、2、11、46]、[12、37、41]、
[5]、[21]、[22]、[10、23、28、29]、[6、34、48]、[0、8、33、36、44]、
[31]、[32]、[19]、[30]、[35]、[9、47]]
一些数据点仍然聚集在一起。我通过添加少量数据噪声来解决这个问题actual
词典中的sort
功能:
# Add small random noise
for key in actual:
actual[key] += np.random.normal(0, 0.005)
知道如何正确解决这个问题吗?