在

之前的文章

中，我介紹了如何通過實施名為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)，這也是非常有名的技術，并且有一些有趣的應用。