本文阐述了理解机器学习算法内部工作原理的重要性，以及它在实现和评估方面的不同之处。

机器学习工程师经常会发现，他们总是需要为手头的问题选择正确的算法。通常情况下是这样做的：首先，他们需要了解他们提供解决方案的问题的结构。然后，他们研究手头的数据集。经过初步观察后得到关键结论，最终，他们为任务选择正确的算法。

确定适用于手头数据集的最佳算法似乎是一项普通的工作。通常在这种情况下，工程师们会试图走捷径。如果任务有 0-1 标签，那么只需应用逻辑回归就可以了，对吗？不对！我们应该意识到这些捷径，并时刻提醒自己，尽管某些算法可以很好地解决特定问题，但是，为解决问题选择最佳算法时，却没有什么诀窍。然而，工程师们应该始终讨论并考虑算法的复杂性和运行时分析。

算法的运行时分析不仅对理解算法的内部工作至关重要，而且还可以产生更为成功的实现。

在本文中，我将描述一种情况，在这一情况下，忽略算法的运行时分析，K 表示聚类，这些都是会让工程师浪费大量的时间和精力的东西。

什么是 K 均值聚类

K 均值聚类（K-means clustering）是目前最流行、最容易实现的无监督机器学习算法之一。它也是一种易于理解的机器学习算法。

通常情况下，无监督机器学习算法仅使用特征向量对输入数据集中做出推理（Inferences）。因此，这些算法适用于没有标签数据的数据集。当人们想从大量结构化和非结构化数据中提取价值或洞见时，它们也非常有用。K 均值聚类是其中一种探索性数据分析技术，其目标是提取数据点的子群（subgroup），以使同一聚类中的数据点在定义的特征方面非常相似。

K 均值聚类的工作原理

K 均值聚类算法是从随机选择的第一组数据点开始，这些数据点被用作质心（Centroid）的初始种子。然后，该算法执行迭代计算，将其余的数据点分配给最近邻的聚类。当根据定义的距离函数执行这些计算时，质心的位置将会更新。在以下任一情况下，它都会停止对聚类中心的优化：

质心的位置是稳定的，即，它们的值的变化不超过预定义的阈值。
该算法超过了最大迭代次数。

因此，该算法的复杂度为：

O(n * K * I * d)
n : number of points
K : number of clusters
I : number of iterations
d : number of attributes

K 均值算法示例问题

我将分享一段 K 均值聚类算法任务的代码段。我唯一目的在于为读者演示一个示例，在这个实例中，如果不能理解运行时的复杂性，那么将会导致对算法的评估很差劲。需要说明的是，我所采取的步骤并没有针对算法进行优化，也就是说，为了取得更好的结果，你可以对数据进行预处理并获得更好的聚类。所涉及的步骤概述如下：

导入库，并读取数据集。在这个示例中，我导入相关的库并读书数据集，这些数据集已经下载到本地文件夹中。
预处理。在这一步中，我丢弃了字符串类型的列，而只关注数值特性。由于 K 均值聚类算法计算数据点之间的距离，所以它适用于数值列。
应用主成分分析法进行降维。在应用 K 均值聚类算法之前，最好先对数据集进行降维，因为在高维空间中，距离度量的效果并不是很好。
计算轮廓分数。K 均值聚类算法并不能直接应用。它涉及到寻找聚类最佳数量的问题。轮廓分数（Silhouette score）是可以用来确定聚类最佳数量的技术之一。如果不能理解轮廓分数分析所涉及的计算的复杂性，将会得到较差的实现效果。
其他解决方案。在本文中，我列出了一些可供选择的解决方案，以找到聚类的最佳数量。在运行时复杂性方面，它们与轮廓分数相比，更具优势。

你可以重现这个问题来亲自尝试。数据集的地址为：https://www.kaggle.com/sobhanmoosavi/us-accidents。

第一步：导入库并读取数据库

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.pyplot import figure
from sklearn.cluster import KMeans
from sklearn import metrics
df = pd.read_csv(file)

第二步：预处理

#Remove columns that have almost all of its value as None
df.drop(['End_Lat','End_Lng','Number','Wind_Chill(F)','Precipitation(in)'],inplace = True,axis=1)
#Change type of boolean columns to integer
for column in df.columns.values:
    if df[column].dtype == bool:
        df[column] = df[column].astype(int)
def handleMissingData(data): 
  for column in data.columns.values:
    if column not in ['ID'] and data[column].isna().sum():
      if data[column].dtype == int or data[column].dtype == float:
        data[column].fillna(data[column].mean(),inplace=True)
      else:
        data[column].fillna(data[column].mode()[0],inplace=True)
handleMissingData(df)
df = df[['Amenity','Crossing','Junction','No_Exit','Railway','Station','Stop','Traffic_Signal']]

handleMissingData(df)
df = df[['Amenity','Crossing','Junction','No_Exit','Railway','Station','Stop','Traffic_Signal']]

我们只根据与路径有关的特征对数据点进行聚类，以便进行说明。

第三步：应用主成分分析进行降维

import matplotlib.pyplot as plt
from matplotlib.pyplot import figure
from sklearn.decomposition import PCA
data_points = df[df.columns.values].values
numberOfPCAComponent = 3
pcaComponents = []
for i in range(numberOfPCAComponent):
    pcaComponents.append("PCA"+"_"+str(i+1))
component_pos = np.arange(len(pcaComponents))
sklearn_pca = PCA(n_components=numberOfPCAComponent)
sklearn_pca1 = PCA()
sklearn_pca1.fit(data_points)
data_points = sklearn_pca.fit_transform(data_points)
explained_variance = sklearn_pca.explained_variance_ratio_  
print(explained_variance,"explained_variance")
plt.bar(component_pos, explained_variance, align='center', alpha=0.5)
plt.xticks(component_pos, pcaComponents)
plt.ylabel('Explained Variance')
plt.title('Principle Components')
plt.show()
plt.savefig('explained_variance.png')
plt.plot(range(0,8), sklearn_pca1.explained_variance_, 'bx-')
plt.xlabel('pca component')
plt.ylabel('explained variances')
plt.title('Elbow Method For Optimal Number of PCA Component')
plt.show()
plt.savefig('elbow_method_optimal_number_pca.png')
pickle.dump(sklearn_pca,open("pca_stage_semi-supervised.pkl","wb"))

看起来 3 是最佳的。

第四步：计算轮廓得分

确定最佳聚类数目有许多指标和方法。但我会集中讨论其中的几个。轮廓得分就是这些指标度量之一。它使用每个实例的平均聚类内距离和平均最近邻聚类距离来计算的。它计算每个样本和相应聚类中其余样本之间的距离。因此，它的运行时复杂度为 O(n²)。如果无法执行运行时分析的话，你可能需要等待数小时（如果不是数天）才能完成对大型数据集的分析。由于当前数据集有数百万行，解决方法可以是使用更简单的指标度量，如惯性或对数据集应用随机采样。我将阐述这两种方法。

备选解决方案

肘部法则

该方法使用惯性或聚类内平方和作为输入。它描述了惯性值随聚类数量的增加而减小的情况。“肘部”（Elbow，曲线上的拐点）就是一个很好的指示点，在该点上惯性值的减小并不会发生明显的变化。使用这种技术的优点是，聚类内平方和在计算上不像轮廓得分那样昂贵，并且已经作为度量包含在算法中。

%%timeit 
from sklearn.cluster import KMeans
from sklearn import metrics
Sum_of_squared_distances = []
K = range(2,6)
for k in K:
    km = KMeans(n_clusters=k,random_state=5)
    km = km.fit(data_points)
    Sum_of_squared_distances.append(km.inertia_)

上面这段代码的挂钟时间是：

27.9 s ± 247 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

随机降采样

降采样允许你可以处理更小的数据集。这样做的好处是，算法完成所需的时间大为减少。如此一来，分析人员就能够更快地进行工作。缺点是降采样如果随机进行的话，可能无法代表原始数据集。因此，任何涉及降采样数据集的分析都可能导致不准确的结果。但是，你始终可以采取预防措施来确保降采样的数据集代表原始数据集。

%%timeit
from sklearn.cluster import KMeans
from sklearn import metrics
#apply k means clustering and measure silhouette score 
kmeans = KMeans(n_clusters=4,random_state=5).fit(data_points)
metrics.silhouette_score(data_points,kmeans.labels_,metric='euclidean',sample_size=100000)

上面代码段的挂钟时间为：

3min 25s ± 640 ms per loop (mean ± std. dev. of 2 runs, 1 loop each)

结语

在本文中，我试图强调理解机器学习算法复杂性的重要性。算法的运行时分析不仅对于特定任务中的算法选择至关重要，而且对算法的成功实现也很重要。这也是大多数雇主在数据科学领域中寻找的关键技能之一。因此，进行运行时分析并理解算法的复杂性，一直就是很好的实践。

作者介绍：

Baran Köseoğlu，软件开发人员，数据科学家。对机器学习、人工智能和数据科学感兴趣。著有《Towards Data Science》一书。

原文链接：

https://towardsdatascience.com/importance-of-understanding-the-complexity-of-a-machine-learning-algorithm-9d0532685982

创作场景

工程师要理解机器学习算法的复杂性