基本概念

• DBSCAN:Density-Based Spatial Clustering of Applications with Noise (具有噪声的基于密度的聚类方法）
• 核心对象：若某个点内的密度达到算法设定的阈值则为核心点
• ∈-邻域的距离阈值：设定的半径r
• 直接密度可达：若点p在点q的r邻域内，且q是核心点则p-q直接密度可达
• 密度可达：若有一个点的序列$q_0,q_1,...,q_k$，对任意$q_i,q_{i-1}$直接密度可达,那么称$q_0,q_k$密度可达。即直接密度可达的‘传播’。
• 密度相连：若从核心点p出发，点q和点k都是密度可达的。那么点q和点k是密度相连的。(不要求q/k必须是核心点)
• 边界点：属于某个类的非核心点
• 噪声点：不属于任何一个类簇的点，从任何一个核心点出发都是密度不可达的。

参数选择

• 半径∈：可以根据K距离设定，即寻找突变点。

• K距离：给定数据集P = {p(i);i=0,1,...,n},计算点p(i)到集合D的子集S中所有点之间的距离d，按照距离从小到大排序,d(k)即K距离

  例如点s到其他点的距离数组$d_k$={0.1,0.11,0.12,0.3,0.5....}(已排序)，发现前三个距离相差不大，第四个距离0.3发生突变，那么半径取d(3)=0.12,MinPts取3

• MinPts：K-距离中的K值，一般从小开始取

优缺点

优点：

• 可以处理任意形状的簇
• 不需要指定簇的个数
• 擅长找到离群点，用于异常检测任务

缺点：

• 高维数据处理困难(可以寻找降维方法)
• 半径r和MinPts难以确定
• 算法效率慢

算法流程

伪代码如下,类似宽度优先搜索进行簇的传播:

bool visited[n];
memset(visited,false,sizeof visited);
while(some point is unvisited){
    choose p randomly which is unvisited;
    if(p ∈-field has more that MinPts points){
        create a new cluster C;
        N = {q in p ∈-field};
        for(auto &q:N){
            if(visited[q]==false){
                visited[q] = true;
                if(q ∈-field has more that MinPts points){
                    add {k in q ∈-field} to N;
                }
                add q to cluster C;
            }
        }
    }else{
        add p to noise;
    }
}

可视化

Visualizing DBSCAN Clustering (naftaliharris.com)

sklearn

from sklearn.cluster import DBSCAN
dbscan = DBSCAN(eps=0.5,min_sample=5)
dbscan.fit(X)    # train
dbscan.label_   # label label=-1 means noise
descan.core_sample_indices_ # 核心样本在原始训练集中的位置

聚类概念

• 属于无监督学习(无标签)
• 顾名思义，就是将相似的东西分到一组
• 难点在于如何评估聚类效果以及调整参数

基本概念

• K代表最后需要得到的簇个数(比如二分类K=2)
• 一个簇的质心计算：采用均值，即每个特征向量取平均值
• 距离度量：经常使用欧几里得距离和余弦相似度(高维特征最好先执行一次标准化)
• 优化目标：实现$min\sum_{i=1}^{k}\sum_{x∈C_i}dist(C_i,x)^2$

优缺点

优点：

• 算法简单、快速
• 适合常规数据集(就是一坨一坨的那种，没有特定形状)

缺点：

• K值难以确定(一般是遍历K值取Inertia的拐点)
• 算法复杂度与样本呈线性关系(一次迭代)
• 很难发现任意形状的簇，比如二维特征的样本，一个圆环套一个球的形状KMeans就很难检测出来。

算法流程

• 首先随机选取K个样本作为K个簇的中心(在KMeans++中，使用最大距离进行初始化)

  • KMeans++逐个选取K个簇中心，且离其它簇中心越远的样本点越有可能被选为下一个簇中心
• 将每个样本分配到K个簇中，具体选择哪个簇取决于该样本和K个簇的距离，选择距离最近的簇(分配样本)
• 此时所有样本都分配到对应的簇，在每个簇中更新簇中心。新的簇中心采用简单的均值计算(更新簇中心)
• 回到第二步再次分配样本，直到达到迭代次数上限或损失指标小于某个阈值(损失指标有inertia/轮廓系数)

KMeans代码实现

import numpy as np
class KMeans:
    def __init__(self,data,num_clusters):
        self.data = data
        self.num_clusters = num_clusters
        
    def train(self,max_iterations):
        # 1.choose k centers
        centroids = KMeans.centroids_init(self.data,self.num_clusters)
        # 2.begin train
        num_examples = self.data.shape[0]
        closest_centroids_ids = np.empty((num_examples,1))
        for _ in range(max_iterations):
            # 3.get closest center id
            closest_centroids_ids = KMeans.centroids_find_closest(self.data,centroids)
            # 4.update k centers
            centroids = KMeans.centroids_compute(self.data,closest_centroids_ids,self.num_clusters)
        return centroids,closest_centroids_ids
    
    @staticmethod
    def centroids_init(self,data,num_clusters):
        num_examples = data.shape[0]
        random_ids = np.random.permutation(num_examples)
        centroids = data[random_ids[:num_clusters],:]
        return centroids
    
    @staticmethod
    def centroids_find_closest(self,data,entroids):
        num_examples = data.shape[0]
        num_centroids = centroids.shape[0]
        closest_centroids_ids = np.zeros((num_examlpes,1))
        for example_index in range(num_examples):
            distance = np.zeros(num_centroids,1)
            for centroid_index in range(num_centroids):
                distance_diff = data[example_index,:] - centroids[centroid_index,:]
                distance[centroid_index] = np.sum(distance_diff**2)
            closest_centroids_ids[example_index] = np.argmin(distance)
        return closest_centroids_ids
    
    @staticmethod
    def centroids_compute(self.data,closest_centroids_ids,self.num_clusters):
        num_features = data.shape[1]
        centroids = np.zeros((num_clusters,num_features))
        for centroid_id in range(num_clusters):
            closest_ids = closest_centroids_ids == centroid_id
            centroids[centroid_ids] = np.mean(data[closest_ids.flatten(),:],axis=0)
        return centroids

sklearn

接下来介绍sklearn库中的KMeans实现.

文档见sklearn.cluster.KMeans — scikit-learn 1.2.2 documentation

Attributes

__init__

• n_clusters : 簇个数K
• random_state : 随机数种子
• init : K个簇中心的初始化方式
• n_init : 算法执行次数,取结果最好的一次
• max_iter : 单次算法迭代次数(分配簇/更新簇)

from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=2,random_state=0,init='k-means++',n_init=10,max_iter=300)

fit

kmeans.fit(X) # input X
kmeans.cluster_centers_ # center coordinate
kmeans.label_ # every sample's label
kmeans.inertia # loss

pred

kmeans.predict(New_X)
kmeans.label_

tranform

Transform(): Method using these calculated parameters apply the transformation to a particular dataset.

返回值shape : (num_examples,num_clusters) 即每个样本和每个类的距离 通过这个方法也可以得到predict结果(argmin)

from sklearn.preprocessing import StandardScaler
sc = StandardScaler()
sc.fit_tranform(X_train)
sc.tranform(X_test) # 一定是tranform 保证train和test使用同一个转化标准

可视化

# draw cluster points
def plot_data(feature,snr,label):
    df = pd.DataFrame(dict(x=snr, y=feature, color=label))
    fig, ax = plt.subplots()
    colors = {0:'red', 1:'blue'}
    ax.scatter(df['x'], df['y'], c=df['color'].apply(lambda x: colors[x]))
    plt.show()

# draw cluster centers
def plot_centriods(snr,centroids,weights=None,circle_color='g',cross_color='k'):
    if weights is not None:
        centroids = centroids[weights>weights.max()/10]
    plt.scatter(snr,centroids[:],
               marker='o',s=30,linewidths=8,
               color=circle_color,zorder=10,alpha=0.9)
    plt.scatter(snr,centroids[:],
               marker='x',s=50,linewidths=50,
               color=circle_color,zorder=11,alpha=1)

评估指标

inertia指标

inertia : 每个样本距离质心的距离

score方法的结果是inertia的负值(绝对值越大分数越小)

kmeans.inertia_
X_dist = kmeans.transform(X)
np.sum(X_dist[np.arange(len(X_dist)),kmeans.labels_]**2) # inertia计算
kmeans.score(X) == -1*kmeans.inertia_

轮廓系数

某个样本的轮廓系数定义为:

$$ s = \frac {disMean_{out} - disMean_{in}}{max(disMean_{out}-disMean_{in})} $$

其中$disMean_{in}$为该点与本类其他点的平均距离，$disMean_{out}$为该点与非本类点的平均距离。该值取值范围为[−1,1]， 越接近1则说明分类越优秀。在sklearn中函数 silhouette_score() 计算所有点的平均轮廓系数，而silhouette_samples()返回每个点的轮廓系数。

K值选取(拐点法)

kmeans_per_k = [KMeans(n_clusters=k).fit(X) for k in range(1,10)]
inertias = [model.inertia_ for model in kmeans_per_k]
# draw fig
plt.figure(figsize=(8,4))
plt.plot(range(1,10),inertias,'bo-')
plt.show()

半监督学习

KMeans也可以用于半监督学习。

比如在一个少样本训练场景下，相比于随机选取50个训练样本打标加入训练这种方式，可以先使用聚类挑出50个簇中心，每个簇选取一个样本作为典型样本；用这些样本打标训练，最后测试出来的acc会更高。除此之外，还可以通过标签传播(同一个簇内的标签一致)的方式扩大训练集。