本科毕业设计（论文）
外文翻译
作者：John V. Guttag
国籍：英国伦敦
出处：Introduction to Computation and Programming Using Python with Application to Understanding Data. Cambridge, MA : The MIT Press, [2017],Page 383-402.
聚类
无监督学习包括在未标记的数据中发现隐藏的结构,最常用的无监督机器学习技术是聚类。
聚类可以定义为将对象组织到组中的过程,其成员在某种程度上相似。 一个关键问题是定义的含义“相似。”考虑图23.1中的图，图中显示了13个人的身高、体重和衬衫颜色。
图23.1衬衫的高度、重量和种类
如果我们把人按身高分组，有两个明显的分类——用虚线水平线分隔。如果我们按体重将人们放在一起，有两个明显不同的分类——由实垂直线分隔。如果我们根据人们的衬衫来划分人群，那么还有第三个分类——由斜线虚线分隔。顺便说一下，注意最后一个除法不是线性的。也就是说，我们不能用一条直线来区分衬衫的颜色。
聚类是一个优化问题。我们的目标是找到一组簇来优化一个目标函数，它受一些约束条件的约束。给定一个距离度量，可以用来决定两个例子之间的距离有多近，我们需要定义一个目标函数，使相同集群中的例子之间的距离最小化，即，以尽量减少集群内示例之间的差异。
我们称之为方差，其中一个度量标准是：单个集群c内的示例彼此之间的差异有多大
variability
其中均值(c)为聚类中所有样本特征向量的均值，一组向量的均值按分量计算，添加相应的元素，并将结果除以向量的数量。如果vl和v2是数字数组，那么表达式(v1 v2)/2的值就是它们的欧几里得均值。
我们所说的方差与第15章中提出的方差概念非常相似。不同之处在于，方差并不是由集群的大小标准化的，因此，根据这个度量，具有更多点的集群可能看起来凝聚力更差。如果要比较两个不同大小集群的一致性，需要将每个集群的方差除以集群的大小。
单个集群中方差的定义c可以扩展为定义一组集群的不同度量C。
注意，由于我们不将方差除以集群的大小，一个大的不相干集群比一个小的不相干集群增加了差异性（C）的值，这是通过设计实现的。
那么，寻找一组簇的优化问题是否使得差异性(C)最小化?不完全是。通过将每个示例放在自己的集群中，可以很容易地将其最小化。我们需要添加一些约束，例如，我们可以对集群之间的最小距离施加约束，或者要求集群的最大数量为k。
一般来说，解决这个优化问题在计算上对最有趣的问题是不允许的。因此，人们依赖提供近似解的贪婪算法。在第23.2节中，我们提出了一个这样的算法，k-均值聚类。首先，我们将介绍一些对实现该算法（以及其他集群算法）有用的抽象概念。
23.1类集群
类示例将用于构建集群化的示例。与每个示例关联的是名称、特征向量和可选标签。距离方法返回两个例子之间的欧几里得距离。
图23.2类示例
class Example(object):
def __init__(self, name, features, label = None):
#Assumes features is an array of floats
self.name = name
self.features = features
self.label = label
def dimensionality(self):
return len(self.features)
def getFeatures(self):
return self.features[:]
def getLabel(self):
return self.label
def getName(self):
return self.name
def distance(self, other):
return minkowskiDist(self.features, other.getFeatures(), 2)
def __str__(self):
return self.name : str(self.features) :
str(self.label)
类簇，如图23.3所示，稍微复杂一些，簇是一组示例。聚类中两个有趣的方法是计算质心和方差，将簇的质心视为其质心。计算质心的方法返回一个例子，其特征向量等于该示例特征向量的欧几里得平均值。在类簇中，该方法的方差提供了集群一致性的度量。
图23.3分类群
class Cluster(object):
def __init__(self, examples):
'''Assumes examples a non- empty list of Examples'''
self.examples = examples
self.centroid = self.computeCentroid()
def update(self, examples):
'''Assume examples is a non- empty list of Examples
Replace examples; return amount centroid has changed'''
oldCentroid = self.centroid
self.examples = examples
self.centroid = self.computeCentroid()
return oldCentroid.distance(self.centroid)
def computeCentroid(self):
vals = pylab.array([0.0]*self.examples[0].dimensionality())
for e in self.examples: #compute mean
vals = e.getFeatures()
centroid = Example(centroid, vals/len(self.examples))
return centroid
def getCentroid(self):
return self.centroid
def variability(self):
totDist = 0.0
for e in self.examples:
totDist = (e.distance(self.centroid))**2
return totDist
def members(self):
for e in self.examples:
yield e
def __str__(self):
names = []
for e in self.examples:
names.append(e.getName())
names.sort()
result = Cluster with centroid
str(self.centroid.getFeatures()) contains:
for e in names:
result = result e ,
return result[: -2] #remove trailing comma and space
23.2 K-means聚类
K-means聚类可能是最广泛使用的聚类方法，其目标是将一组示例划分为k个集群，以便
bull;每个示例都位于其质心与该示例最近的质心的集群中；
bull;集群的差异性被最小化。
不幸的是，在大型数据集中找到这个问题的最优解决方案在计算上非常困难。幸运的是，有一个有效的贪婪算法可以用来找到一个有用的近似，它由伪代码描述：
随机选择k个样本作为簇的初始质点，而真正的：
1.通过将每个示例分配给最近的质心来创建k个集群；
2.计算k个新的质点通过平均每个集群中的例子；
3.如果没有一个质心与前一个迭代不同，返回当前集群
步骤1的复杂度为O(k*n*d)，其中k为集群的数量，n为示例的数量，d为计算一对示例之间距离所需的时间。步骤2的复杂度为O(n)，步骤3的复杂度为O(k)。因此，单个迭代的复杂度为O(k*n*d)。如果用Minkowski距离比较例子，d在特征向量长度上是线性的。当然，整个算法的复杂度取决于迭代次数。这并不容易描述，但只要说它通常很小就足够了。
k-means算法的一个问题是，返回的值依赖于随机选择的质心的初始集。如果选择了一组不合适的初始质心，算法可能会陷入局部最优，而不是全局最优。在实践中，这个问题通常通过使用随机选择的初始中心多次运行k-means来解决。然后选择簇间差异最小的解。
图23.4包含一个函数trykmeans，它多次调用kmeans(参见图23.5)，并选择差异最小的结果。如果试验失败是因为kmeans生成了一个空的集群，因此引发了异常，trykmeans只是再次尝试——假设kmeans最终会选择一组成功收敛的初始质心。
图23.4寻找最佳k均值聚类
def dissimilarity(clusters):
totDist = 0.0
for c in clusters:
totDist = c.variability()
return totDist
def trykmeans(examples, numClusters, numTrials, verbose = False):
'''Calls kmeans numTrials times and returns the result with the lowest dissimilarity'''
best = kmeans(examples, numClusters, verbose)
minDissimilarity = dissimilarity(best)
trial = 1
while trial lt; numTrials:
try:
clusters = kmeans(examples, numClusters, verbose)
except ValueError:
continue #If failed, try again
currDissimilarity = dissimilarity(clusters)
if currDissimilarity lt; minDissimilarity:
best = clusters
minDissimilarity = currDissimilarity
trial = 1
return best
图23.5包含了描述k-means的伪代码的Python转换。唯一的问题是，如果任何迭代创建一个没有成员的集群，那么它会引发异常。生成空集群的情况很少，它不能在第一次迭代中发生，但是可以在随后的迭代中发生。它通常是由于选择了太大的k或初始质心的不恰当选择。将空集群视为错误是Matlab使用的选项之一。另一种方法是创建一个包含单个点的新的集群——离质心最远的点。在其他集群中，我们选择将其作为一个错误来处理，以保持实现相对简单。
图23.5 k-means聚类
def kmeans(examples, k, verbose = False):
#Get k randomly chosen initial centroids, create c
剩余内容已隐藏，支付完成后下载完整资料
英语原文共 20 页，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[272170]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
