龙空技术网

改进的人工蜂群算法解决聚类问题(在Python中的分步实现)

林小婵的店 1691

前言:

而今小伙伴们对“人工鱼群算法的应用领域”都比较看重,兄弟们都想要了解一些“人工鱼群算法的应用领域”的相关内容。那么小编在网络上收集了一些关于“人工鱼群算法的应用领域””的相关知识,希望咱们能喜欢,你们一起来学习一下吧!

在之前的文章中,我介绍了如何通过实施名为Artificial Bee Colony(ABC)的群集智能(SI)算法来解决现实世界中的优化问题。

现在是时候让我们掌握一些真实的数据并解释我们如何使用我们的ABC算法的Python实现来执行群集任务。但在此之前,让我们深入了解一下聚类问题。

聚类问题

聚类问题是一个未明确定义的NP难题,其基本思想是在数据中发现隐藏的模式。关于什么是集群没有一个正式的定义,但它与分组元素的想法相关联,以便我们可以区分不同组中的元素。

有不同的算法族以不同的方式定义聚类问题。定义聚类问题的经典方法,在文献中经常见到,是将其减少为一个数学问题,即找到原始数据的k分区。

找到一个集合S的k分区,被定义为找到S的k个子集,它服从两个规则:

这些子集中的任何不同的交集都等于空集合。所有k 个子集的并集等于S.

基本上,在这个分区聚类过程结束时,我们希望找到原始数据集的不同子集,以这种方式,没有实例将属于多个组。这可以在下面的图像中说明:

左边是原始数据,右边是k = 2的分区数据

k = 2时可以使用质心如何执行数据分区的示例

我们如何拆分数据以执行上图中所示的分区?那么,聚类过程的输出是一组质心。质心基本上是每个组的代表性实体,所以如果我们想要对数据进行k分割,那么我们将有k个 质心。

质心也是由我们的数据定义的搜索空间上的点,并且由于每个质心定义了一个组,每个数据点将被分配到距离它最近的质心。

修改聚类的人工蜂群

那么,现在我们知道什么是聚类问题,我们如何修改原来的ABC算法来执行这样的任务?猜猜看,我们没有!是的,这就是你刚刚阅读的内容,我们根本不需要修改我们的ABC实施。我们唯一要做的就是查看聚类问题并将其转化为优化任务!但我们怎么做到这一点?

正如我们在前面的文章中看到的那样,一个明确定义的优化问题需要一个搜索空间,一个集合的维度输入决策变量和一个目标函数。如果我们将人工菌落中的每只蜜蜂看作是我们聚类问题的整体解决方案,那么每只蜜蜂都可以代表一组完整的候选质心!如果我们工作的一个d维空间,我们要执行的k分区上我们的数据,那么每个蜂将是一个ķ · d维向量!

现在我们已经定义了如何表示我们的输入决策变量,我们只需要弄清楚如何定义我们的搜索空间的边界以及我们的目标函数是什么。

我们的搜索空间的边界很容易,我们可以用[0,1]区间对我们整个数据集进行规范化,并将我们的目标函数定义为边界从0到1.完成,就是这样。现在我们来看一个更复杂的部分:如何定义我们的目标函数?

在分区聚类方法中,我们希望最大化两个不同组之间的距离,并最小化组内的距离。文献中使用了几个目标函数,但是最为人熟知的方法是所谓的平方和(Sum of Squared Errors,SSE)。

这个公式意味着什么?那么,误差平方总和(SSE)是一个聚类度量,其背后的想法非常简单。它基本上是一个数值,它计算我们数据中每个实例到其最接近质心的平方距离。我们的优化任务的目标是尽量减少这个功能。

我们可以使用我们以前的目标函数框架来实现误差平方和,Python代码如下所示:

@add_metaclass(ABCMeta)

class PartitionalClusteringObjectiveFunction(ObjectiveFunction):

def __init__(self, dim, n_clusters, data):

super(PartitionalClusteringObjectiveFunction, self)\

.__init__('PartitionalClusteringObjectiveFunction', dim, 0.0, 1.0)

self.n_clusters = n_clusters

self.centroids = {}

self.data = data

def decode(self, x):

centroids = x.reshape(self.n_clusters, self.dim)

self.centroids = dict(enumerate(centroids))

@abstractmethod

def evaluate(self, x):

pass

class SumOfSquaredErrors(PartitionalClusteringObjectiveFunction):

def __init__(self, dim, n_clusters, data):

super(SumOfSquaredErrors, self).__init__(dim, n_clusters, data)

self.name = 'SumOfSquaredErrors'

def evaluate(self, x):

self.decode(x)

clusters = {key: [] for key in self.centroids.keys()}

for instance in self.data:

distances = [np.linalg.norm(self.centroids[idx] - instance)

for idx in self.centroids]

clusters[np.argmin(distances)].append(instance)

sum_of_squared_errors = 0.0

for idx in self.centroids:

distances = [np.linalg.norm(self.centroids[idx] - instance)

for instance in clusters[idx]]

sum_of_squared_errors += sum(np.power(distances, 2))

return sum_of_squared_errors

实践一些真实的数据

现在是时候把我们的手放在一些真实的数据上,并测试我们的ABC算法可以执行的聚类算法。对于这个研究案例,我们将使用着名的Iris数据集。

这是一个最初的四维数据集,其中包含三种植物的特征。为了可视化目的,我们将仅使用该数据集的两个维度。我们来检查一下这个数据集的第二维和第四维之间的关系:

import matplotlib.pyplot as plt

from abc import ABC

from objection_function import SumOfSquaredErrors

from sklearn.datasets import load_iris

from sklearn.preprocessing import MinMaxScaler

data = MinMaxScaler().fit_transform(load_iris()['data'][:, [1,3]])

plt.figure(figsize=(9,8))

plt.scatter(data[:,0], data[:,1], s=50, edgecolor='w', alpha=0.5)

plt.title('Original Data')

以上Python代码的输出可以在下面看到:

原始数据分布

由于我们将使用这些数据作为基准测试,因此我们已经知道它的最佳划分是什么,它是由三种花的原始分布给出的。我们可以用下面的Python代码可视化Iris数据集的原始最优分区

colors = ['r', 'g', 'y']

target = load_iris()['target']

plt.figure(figsize=(9,8))

for instance, tgt in zip(data, target):

plt.scatter(instance[0], instance[1], s=50,

edgecolor='w', alpha=0.5, color=colors[tgt])

plt.title('Original Groups')

以下分布图

我们数据集中的原始组

现在我们知道这个样本数据的原始最优分区是什么,现在该知道我们的ABC算法是否能够为这个问题找到一个非常接近的解决方案。我们将使用我们的平方和目误差标函数,并将分区数设置为3。

由于初始化是随机的,因此很可能生成的质心的顺序与类的顺序不匹配。因此,当绘制ABC算法的输出时,组的颜色可能不匹配。这并不重要,我们实际将会看到的是对应分区组的外观。

objective_function = SumOfSquaredErrors(dim=6, n_clusters=3, data=data)

optimizer = ABC(obj_function=objective_function, colony_size=30,

n_iter=300, max_trials=100)

optimizer.optimize()

def decode_centroids(centroids, n_clusters, data):

return centroids.reshape(n_clusters, data.shape[1])

centroids = dict(enumerate(decode_centroids(optimizer.optimal_solution.pos,

n_clusters=3, data=data)))

def assign_centroid(centroids, point):

distances = [np.linalg.norm(point - centroids[idx]) for idx in centroids]

return np.argmin(distances)

custom_tgt = []

for instance in data:

custom_tgt.append(assign_centroid(centroids, instance))

colors = ['r', 'g', 'y']

plt.figure(figsize=(9,8))

for instance, tgt in zip(data, custom_tgt):

plt.scatter(instance[0], instance[1], s=50, edgecolor='w',

alpha=0.5, color=colors[tgt])

for centroid in centroids:

plt.scatter(centroids[centroid][0], centroids[centroid][1],

color='k', marker='x', lw=5, s=500)

plt.title('Partitioned Data found by ABC')

我们的Python代码的输出可以在下面看到

The partition of our dataset found by the ABC algo

如果我们看看原始分区和我们ABC算法生成的分区,我们可以看到它能够找到一个真正关闭最优分区的分区。这证明了用于聚类的“修改”ABC算法有多强大。我们还可以通过查看我们的ABC算法的optimality_tracking属性来了解优化过程的流程:

itr = range(len(optimizer.optimality_tracking))

val = optimizer.optimality_tracking

plt.figure(figsize=(10, 9))

plt.plot(itr, val)

plt.title('Sum of Squared Errors')

plt.ylabel('Fitness')

plt.xlabel('Iteration')

正如所料,ABC算法在最小化SSE目标函数方面非常有效。我们可以看到,群智能拥有解决优化问题的一些强大机制,适应这些算法解决现实问题只是我们如何将这些问题减少到优化任务的问题。

下一步是什么 ?

我们已经通过实施人工蜂群算法简单介绍了群智能,以及如何使用它来解决一些有趣的问题,如优化实际功能以及如何“修改”ABC算法以解决群集问题。

这些算法有大量的应用,如图像分割、人工神经网络训练、数字图像处理和模式识别、蛋白质结构预测等。还有一些其他强大的群体智能(SI)算法,如粒子群优化(PSO)和鱼群搜索(FSS),这也是非常有名的技术,并且有一些有趣的应用。

标签: #人工鱼群算法的应用领域 #人工蜂群算法原理 #psopython #人工蜂群算法聚类 #人工鱼群算法程序