Clustering本文转载自公众号《读芯》（ID：AI_Discovery）分析是一种无监督的学习方法，将数据点分成几个特定的??组或组，从而在某种意义上让数据点在同一组中具有相似的属性，不同组中的数据点具有不同的属性。聚类分析包括许多基于不同距离度量的不同方法。例如。K-means（点间距离）、Affinitypropagation（图间距离）、meanshift（点间距离）、DBSCAN（最近点间距离）、Gaussianmixture（马哈拉诺比斯中心距离）、谱聚类（图间距离）、等。2014年，DBSCAN算法在领先的数据挖掘会议ACMSIGKDD（授予在理论和实践中受到广泛关注的算法）中获得testoftime奖。所有的聚类方法都采用相同的方法，即先计算相似度，然后利用相似度将数据点聚类成组或簇。本文将重点介绍基于密度的噪声聚类(DBSCAN)。当您已经拥有K均值聚类时，为什么还需要像DBSCAN这样基于密度的聚类算法？K均值聚类可以将松散相关的观察聚类在一起。每个观察最终都会成为某个集群的一部分，即使这些观察在向量空间中相距很远。由于聚类依赖于聚类元素的方式，因此每个数据点都在形成聚类中发挥作用。数据点的细微变化可能会影响聚类结果。由于簇的形成方式，这个问题在DBSCAN中大大减少了。这通常没什么大不了的，除非你有一些形状奇怪的数据。使用K-means的另一个困难是需要指定要使用的簇数(“k”)。在许多情况下，事先并不知道什么是合理的k值。DBSCAN的优点是您不必指定要使用它的集群的数量。所需要的只是一个计算值之间距离的函数，以及一些将某些距离限定为“接近”的指令。在各种不同的分布中，DBSCAN也产生了比K-means更合理的结果。下图说明了这一事实：Density-basedclusteringalgorithmsDensity-basedclustering是一种无监督学习方法，其基础是数据空间中的聚类是连续的高点密度区域，由连续的低点密度区域等分隔开来类-集群分离以识别数据中的独特组/集群。Density-basedclusteringwithnoise（DBSCAN）是一种基于密度聚类的基本算法。它可以从大量数据中发现不同形状和大小的聚类，其中包含噪声和异常值。DBSCAN算法使用以下两个参数：eps(ε)：用于在任何点的邻域内定位点的距离度量。minPts：聚集在一起的最小点数（阈值），这样一个区域就被定义为密集的。如果您探索称为密度可达性和密度连通性的两个概念，就可以理解这些参数。密度方面的可达性表明，如果一个点与另一个点的距离在一定距离(eps)以内，则该点可以到达另一个点。连通性涉及基于传递性的链接方法，以确定一个点是否位于特定的集群中。例如，如果p->r->s->t->q，则p和q可以连通，其中a->b表示b在a的邻域内。DBSCAN聚类完成后，会产生三类点：核心点（Core）——这个点表示在距离n的范围内至少有m个点。边界点（Border）——这个点表示距离n处至少有一个核心。噪声点（Noise）——它既不是核心点也不是边界点。并且它在距自身n距离内的点数少于m。DBSCAN聚类算法的步骤算法通过在数据集中任意选择一个点来运行（直到访问完所有点）。如果在该点的“ε”半径内至少有“minPoint”个点，则所有这些点都被认为属于同一个簇。通过为每个邻域参数估计递归重复邻域计算来扩展聚类每个数据挖掘任务都有一个参数问题。每个参数都以特定方式影响算法。DBSCAN需要参数ε和minPts。ε：ε的值可以使用k-distancemap来选择，它表示到k=minPts-1的最近邻的距离，从最大值到最小值排序。当此图显示“弯头”时，ε的值是好的：如果ε选得太小，很大一部分数据将无法聚类；如果ε的值太高，集群将合并并且大多数对象将在类中的同一集群中。一般来说，较小的ε值是可取的，根据经验，只有一小部分点应该在这个距离内。距离函数：距离函数的选择与ε的选择密切相关，对结果有显着影响。一般来说，在选择参数ε之前，首先要为数据集确定一个合理的相似性度量。该参数没有估计，但是需要适当地为数据集选择距离函数。minPts：根据经验，最小的minPts可以由数据集中的维数D得出，即minPts≥D+1。minPts=1的低值是没有意义的，因为此时每个点本身已经是一个簇。当minPts≤2时，结果将与具有单链接度量的层次聚类相同，树状图在高度ε处被切割。因此，必须至少选择3个minPts。然而，对于嘈杂的数据集，较大的值通常更好，并且会产生更显着的聚类。根据经验，可以使用minPts=2dim，但对于非常大的数据、嘈杂的数据或包含许多重复项的数据，可能需要选择更大的值。使用sklearnpython实现DBSCAN首先使用DBSCAN聚类球形数据。首先生成750个带有相应标签的球形训练数据点。然后对训练数据的特征进行归一化，最后应用sklearn库中的DBSCAN。聚类球形数据中的DBSCAN黑色数据点代表上述结果中的异常值。接下来，使用DBSCAN对非球形数据进行聚类。importnumpyasnpimportmatplotlib.pyplotaspltfromsklearnimportmetricsfromsklearn.datasetsimportmake_circlesfromsklearn.preprocessingimportStandardScalerfromsklearn.clusterimportDBSCANX,y=make_circles(n_samples=750,factor=0.3,noise=0.1)X=StandardScaler().fit_transform(X)y_pred=DBSCAN=0.3,eps).(X)plt.scatter(X[:,0],X[:,1],c=y_pred)print('Numberofclusters:{}'.format(len(set(y_pred[np.where(y_pred!=-1)]))))print('同质性:{}'.format(metrics.homogeneity_score(y,y_pred)))print('完整性:{}'.format(metrics.completeness_score(y,y_pred)))print("V-measure:%0.3f"%metrics.v_measure_score(labels_true,labels))print("AdjustedRandIndex:%0.3f"%metrics.adjusted_rand_score(labels_true,labels))print("AdjustedMutualInformation:%0.3f"%metrics.adjusted_mutual_info_score(labels_true,labels))print("SilhouetteCoefficient:%0.3f"%metrics.silhouette_score(X,labels))聚类非球形数据中的DBSCAN绝对是完美的。如果与K-means比较，它会给出一个完全错误的输出，如：K-means聚类结果DBSCAN聚类算法的复杂性平均情况：与最佳/最坏情况相同，取决??于数据和算法完成。最佳情况：如果使用索引系统存储数据集，使得邻域查询以对数时间执行，则可以获得O(nlogn)的平均运行时间复杂度。最坏情况：如果不使用索引结构或退化数据（例如，距离小于ε的所有点），最坏情况下的运行时间复杂度仍为O(n2)。基于密度的聚类算法可以学习任意形状的聚类，而水平集树算法可以学习密度变化很大的数据集中的聚类。来源：unsplash但需要指出的是，与参数聚类算法（如K-means）相比，这些算法有些难以调整。DBSCAN或水平集树的epsilon参数在推理上不如K-means的聚类参数直观，这使得为这些算法选择好的初始参数值变得??更加困难。
