机器学习之K表示聚类_成都软件开发

技术支持

技术支持分类

机器学习之K表示聚类

作者：成都软件开发
发表时间：2019-03-24 19:54
来源：未知

我们给出了一组项目数据，包括某些特征和这些特征的值（如矢量）。任务是将这些项目分组。为此，我们将使用kMeans算法; 无监督学习算法。

概观

（如果您将项目视为n维空间中的点，则会有所帮助）。该算法将项目分类为k组相似性。为了计算这种相似性，我们将使用欧氏距离作为测量值。

算法的工作原理如下：

首先，我们随机地初始化k个点，称为均值。

我们将每个项目分类为其最接近的平均值，并更新平均值的坐标，这是迄今为止分类的项目的平均值。

我们在给定次数的迭代中重复该过程，最后，我们有了我们的集群。

上面提到的“点”称为均值，因为它们包含分类在其中的项目的平均值。要初始化这些方法，我们有很多选择。一种直观的方法是初始化数据集中随机项的均值。另一种方法是在数据集边界之间的随机值初始化均值（如果对于特征x，项目具有[0,3]中的值，我们将使用[0,3]处的x值初始化均值）。

以上算法的伪代码：

初始化k表示随机值

对于给定的迭代次数：

迭代项目：

找到最接近项目的平均值

将项目指定为均值

更新意思

读数据

我们接收输入作为文本文件（'data.txt'）。每行代表一个项目，它包含用逗号分隔的数值（每个特征一个）。您可以在此处找到示例数据集。

我们将从文件中读取数据，并将其保存到列表中。列表的每个元素都是另一个包含要素项目值的列表。我们使用以下函数执行此操作：

filter_none

编辑

play_arrow

brightness_4

def ReadData(fileName):

# Read the file, splitting by lines

f = open(fileName, 'r');

lines = f.read().splitlines();

f.close();

items = [];

for i in range(1, len(lines)):

line = lines[i].split(',');

itemFeatures = [];

for j in range(len(line)-1):

v = float(line[j]); # Convert feature value to float

itemFeatures.append(v); # Add feature value to dict

items.append(itemFeatures);

shuffle(items);

return items;

初始化手段

我们想要在项目的特征值范围内初始化每个均值的值。为此，我们需要找到每个特征的最小值和最大值。我们通过以下功能实现这一目标：

filter_none

编辑

play_arrow

brightness_4

def FindColMinMax(items):

n = len(items[0]);

minima = [sys.maxint for i in range(n)];

maxima = [-sys.maxint -1 for i in range(n)];

for item in items:

for f in range(len(item)):

if (item[f] < minima[f]):

minima[f] = item[f];

if (item[f] > maxima[f]):

maxima[f] = item[f];

return minima,maxima;

变量minima，maxima是分别包含项目的最小值和最大值的列表。我们在上述两个列表中的相应最小值和最大值之间随机初始化每个均值的特征值：

filter_none

编辑

play_arrow

brightness_4

def InitializeMeans(items, k, cMin, cMax):

# Initialize means to random numbers between

# the min and max of each column/feature

f = len(items[0]); # number of features

means = [[0 for i in range(f)] for j in range(k)];

for mean in means:

for i in range(len(mean)):

# Set value to a random float

# (adding +-1 to avoid a wide placement of a mean)

mean[i] = uniform(cMin[i]+1, cMax[i]-1);

return means;

欧几里德距离

我们将使用欧氏距离作为我们数据集的相似度量标准（注意：根据您的项目，您可以使用其他相似性度量标准）。

filter_none

编辑

play_arrow

brightness_4

def EuclideanDistance(x, y):

S = 0; # The sum of the squared differences of the elements

for i in range(len(x)):

S += math.pow(x[i]-y[i], 2);

return math.sqrt(S); #The square root of the sum

更新手段

要更新均值，我们需要为均值/集群中的所有项找到其特征的平均值。我们可以通过添加所有值然后除以项目数来实现，或者我们可以使用更优雅的解决方案。我们将通过执行以下操作来计算新的平均值，而无需重新添加所有值：

m =（m *（n-1）+ x）/ n

其中m是要素的平均值，n是群集中的项目数，x是添加项目的要素值。我们为每个功能执行上述操作以获得新的平均值。

filter_none

编辑

play_arrow

brightness_4

def UpdateMean(n,mean,item):

for i in range(len(mean)):

m = mean[i];

m = (m*(n-1)+item[i])/float(n);

mean[i] = round(m, 3);

return mean;

分类项目

现在我们需要编写一个函数来将项目分类到一个组/集群。对于给定的项目，我们将找到它与每个均值的相似性，我们将该项目归类为最接近的项目。

filter_none

编辑

play_arrow

brightness_4

def Classify(means,item):

# Classify item to the mean with minimum distance

minimum = sys.maxint;

index = -1;

for i in range(len(means)):

# Find distance from item to mean

dis = EuclideanDistance(item, means[i]);

if (dis < minimum):

minimum = dis;

index = i;

return index;

寻找手段

为了实际找到方法，我们将遍历所有项目，将它们分类到最近的集群并更新集群的均值。我们将重复该过程一定数量的迭代。如果在两次迭代之间没有项目更改分类，我们会停止该过程，因为算法已找到最佳解决方案。

以下函数将输入k（所需簇的数量），项目和最大迭代次数作为输入，并返回均值和簇。的项的分类存储在数组属于关联和项目的群集中的号被存储在clusterSizes。

filter_none

编辑

play_arrow

brightness_4

def CalculateMeans(k,items,maxIterations=100000):

# Find the minima and maxima for columns

cMin, cMax = FindColMinMax(items);

# Initialize means at random points

means = InitializeMeans(items,k,cMin,cMax);

# Initialize clusters, the array to hold

# the number of items in a class

clusterSizes= [0 for i in range(len(means))];

# An array to hold the cluster an item is in

belongsTo = [0 for i in range(len(items))];

# Calculate means

for e in range(maxIterations):

# If no change of cluster occurs, halt

noChange = True;

for i in range(len(items)):

item = items[i];

# Classify item into a cluster and update the

# corresponding means.

index = Classify(means,item);

clusterSizes[index] += 1;

cSize = clusterSizes[index];

means[index] = UpdateMean(cSize,means[index],item);

# Item changed cluster

if(index != belongsTo[i]):

noChange = False;

belongsTo[i] = index;

# Nothing changed, return

if (noChange):

break;

return means;

找到群集

最后，我们希望找到集群，给定方法。我们将遍历所有项目，我们将每个项目分类到最近的集群。

filter_none

编辑

play_arrow

brightness_4

def FindClusters(means,items):

clusters = [[] for i in range(len(means))]; # Init clusters

for item in items:

# Classify item into a cluster

index = Classify(means,item);

# Add item to cluster

clusters[index].append(item);

return clusters;

您可以在我的GitHub上找到整个代码，以及示例数据集和绘图功能。谢谢阅读。

本文由Antonis Maronikolakis提供。如果你喜欢GeeksforGeeks并愿意贡献，你也可以用写一篇文章contribute.geeksforgeeks.org或邮寄你的文章contribute@geeksforgeeks.org。查看出现在GeeksforGeeks主页上的文章，并帮助其他Geeks。