发布于 

Fisher算法&SVM&K-Means及其优化

fisher算法及其实现

  1. 请实现fisher算法，并采用自己随机生成2类数据（每类100个）的方式，验证自己的算法。
    参考资料:https://blog.csdn.net/pengjian444/article/details/71138003

数据生成

from sklearn.datasets import make_multilabel_classification
import numpy as np

x, y = make_multilabel_classification(n_samples=200, n_features=2,
                                      n_labels=1, n_classes=1,
                                      random_state=2)

# 根据类别分类
index1 = np.array([index for (index, value) in enumerate(y) if value == 0])  # 获取类别1的indexs
index2 = np.array([index for (index, value) in enumerate(y) if value == 1])  # 获取类别2的indexs

c_1 = x[index1]   # 类别1的所有数据(x1, x2) in X_1
c_2 = x[index2]  # 类别2的所有数据(x1, x2) in X_2

make_multilabel_classification方法参数说明
n_samples:样本的数量。
n_features：样本的特征，这里是在二维平面中的点，所以为2.
n_labels：每个实例的平均标签数。
n_classes：分类问题的分类数。
random_state：设置随机数种子，保证每次产生相同的数据。

enumerate()函数说明
enumerate()函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。

fisher算法实现

def cal_cov_and_avg(samples):
    u1 = np.mean(samples, axis=0)
    cov_m = np.zeros((samples.shape[1], samples.shape[1]))
    for s in samples:
        t = s - u1
        cov_m += t * t.reshape(2, 1)
    return cov_m, u1


def fisher(c_1, c_2):
    cov_1, u1 = cal_cov_and_avg(c_1)
    cov_2, u2 = cal_cov_and_avg(c_2)
    s_w = cov_1 + cov_2
    u, s, v = np.linalg.svd(s_w)  # 奇异值分解
    s_w_inv = np.dot(np.dot(v.T, np.linalg.inv(np.diag(s))), u.T)
    return np.dot(s_w_inv, u1 - u2)

np.mean：计算制定轴上的平均值。
np.zeros：给定形状和类型确定的数组，并用0填充。

判定类别

def judge(sample, w, c_1, c_2):
    u1 = np.mean(c_1, axis=0)
    u2 = np.mean(c_2, axis=0)
    center_1 = np.dot(w.T, u1)
    center_2 = np.dot(w.T, u2)
    pos = np.dot(w.T, sample)
    return abs(pos - center_1) < abs(pos - center_2)


w = fisher(c_1, c_2)  # 调用函数，得到参数w
out = judge(c_1[1], w, c_1, c_2)   # 判断所属的类别
# print(out)

绘图

import matplotlib.pyplot as plt

plt.scatter(c_1[:, 0], c_1[:, 1], c='#99CC99')
plt.scatter(c_2[:, 0], c_2[:, 1], c='#FFCC00')
line_x = np.arange(min(np.min(c_1[:, 0]), np.min(c_2[:, 0])),
                   max(np.max(c_1[:, 0]), np.max(c_2[:, 0])),
                   step=1)

line_y = - (w[0] * line_x) / w[1]
plt.plot(line_x, line_y)
plt.show()
<Figure size 640x480 with 1 Axes>

SVM优化对偶问题的详细推导过程

  1. 请给出SVM优化对偶问题的详细推导过程；并给出只有2维特征情况下的，对偶问题的优化求解过程（可以采用lagrange方法，也可以采用其他方法。）
    参考资料：https://zhuanlan.zhihu.com/p/49331510





SVM算法的实现

  1. 请实现SVM算法；并采用自己随机生成2类线性可分数据（每类100个）的方式验证自己的算法。
    参考资料：https://www.jb51.net/article/131580.htm
from sklearn import svm 
import numpy as np 
import matplotlib.pyplot as plt 
  
np.random.seed(0) 
x = np.r_[np.random.randn(100,2)-[2,2],np.random.randn(100,2)+[2,2]] #正态分布来产生数字,20行2列*2 
y = [0]*100+[1]*100 #100个class0，100个class1 
  
clf = svm.SVC(kernel='linear') 
clf.fit(x,y) 
  
w = clf.coef_[0] #获取w 
a = -w[0]/w[1] #斜率 
#画图划线 
xx = np.linspace(-5,5) #(-5,5)之间x的值 
yy = a*xx-(clf.intercept_[0])/w[1] #xx带入y，截距 
  
#画出与点相切的线 
b = clf.support_vectors_[0] 
yy_down = a*xx+(b[1]-a*b[0]) 
b = clf.support_vectors_[-1] 
yy_up = a*xx+(b[1]-a*b[0]) 
  
print("W:",w) 
print("a:",a) 
  
print("support_vectors_:",clf.support_vectors_) 
print("clf.coef_:",clf.coef_) 
  
plt.figure(figsize=(8,4)) 
plt.plot(xx,yy) 
plt.plot(xx,yy_down) 
plt.plot(xx,yy_up) 
plt.scatter(clf.support_vectors_[:,0],clf.support_vectors_[:,1],s=80) 
plt.scatter(x[:,0],x[:,1],c=y,cmap=plt.cm.Paired) #[:，0]列切片，第0列 
  
plt.axis('tight') 
  
plt.show()
W: [0.95070185 1.15607502]
a: -0.8223530762163854
support_vectors_: [[-0.51174781 -0.10411082]
 [ 0.16323595 -0.66347205]
 [ 2.39904635 -0.77259276]
 [ 0.66574153  0.65328249]
 [-0.25556423  0.97749316]]
clf.coef_: [[0.95070185 1.15607502]]

png

k-means算法的实现

  1. 请实现k-means的算法；并采用自己随机生成3类数据（每类100个）的方式，验证自己的算法。
    参考资料1:https://cloud.tencent.com/developer/article/1465020
    参考资料2:https://blog.csdn.net/weixin_42029738/article/details/81978038 
'''
    K-Means clustering algorithms

'''

print(__doc__)

import time

import numpy as np
import matplotlib.pyplot as plt

from sklearn.cluster import MiniBatchKMeans, KMeans
from sklearn.metrics.pairwise import pairwise_distances_argmin
from sklearn.datasets.samples_generator import make_blobs

# #############################################################################
# Generate sample data
np.random.seed(0)

batch_size = 45
centers = [[1, 1], [-1, -1], [1, -1]] # 初始化3个中心
n_clusters = len(centers) # 聚类的数目为3
# 产生10000组二维数据，以上面三个点为中心，以(-10,10)为边界，数据集的标准差是0.7
X, labels_true = make_blobs(n_samples=10000, centers=centers, cluster_std=0.7)

# #############################################################################
# Compute clustering with Means

k_means = KMeans(init='k-means++', n_clusters=3, n_init=10)
t0 = time.time()
k_means.fit(X)
# 使用k-means对300组数据集训练算法的时间消耗
t_batch = time.time() - t0

# #############################################################################
# Plot result

fig = plt.figure(figsize=(8, 3))
fig.subplots_adjust(left=0.02, right=0.98, bottom=0.05, top=0.9)
colors = ['#4EACC5', '#FF9C34', '#4E9A06']

# We want to have the same colors for the same cluster from the
# MiniBatchKMeans and the KMeans algorithm. Let's pair the cluster centers per
# closest one.
k_means_cluster_centers = np.sort(k_means.cluster_centers_, axis=0)
k_means_labels = pairwise_distances_argmin(X, k_means_cluster_centers)

# KMeans
ax = fig.add_subplot(1, 3, 1)
for k, col in zip(range(n_clusters), colors):
    my_members = k_means_labels == k
    cluster_center = k_means_cluster_centers[k]
    ax.plot(X[my_members, 0], X[my_members, 1], 'w',
            markerfacecolor=col, marker='.')
    ax.plot(cluster_center[0], cluster_center[1], 'o', markerfacecolor=col,
            markeredgecolor='k', markersize=6)
ax.set_title('KMeans')
ax.set_xticks(())
ax.set_yticks(())
plt.text(-3.5, 1.8,  'train time: %.2fs\ninertia: %f' % (
    t_batch, k_means.inertia_))


plt.show()
    K-Means clustering algorithms

png

k-means算法的改进

  1. 请给出三种k-means算法在大数据量时的改进方法，并分析改进的结果。
    改进方法包括：
    1. k-means++（改变中心点的选取方法）
    2. elkan K-Means（减少不必要的距离计算）
    3. ISODATA算法（在运行过程中根据实际情况调整聚类中心数k）
    4. Mini Batch k-means算法（采用部分样本，舍弃一些精确度大大加快收敛速度）

其中1和4改进方法给出了源码和对比。

k-means++（改变中心点的选择方法）

参考资料1:https://blog.csdn.net/github_39261590/article/details/76910689
参考资料2:https://www.cnblogs.com/yszd/p/9672885.html
k-means++算法选择初始seeds的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远。

算法步骤：

  1. 从输入的数据点集合中随机选择一个点作为第一个聚类中心
  2. 对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)
  3. 选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大
  4. 重复2和3直到k个聚类中心被选出来
  5. 利用这k个初始的聚类中心来运行标准的k-means算法
import numpy as np
import matplotlib.pyplot as plt
import sklearn.datasets as ds
import matplotlib.colors
from sklearn.cluster import KMeans
from sklearn.cluster import MiniBatchKMeans

def expand(a, b):
    d = (b - a) * 0.1
    return a-b, b+d

if __name__ == "__main__":
    N = 400
    centers = 4
    data, y = ds.make_blobs(N, n_features=2, centers=centers, random_state=2)
    data2, y2 = ds.make_blobs(N, n_features=2, centers=centers, cluster_std=(1, 2.5, 0.5, 2), random_state=2)
    # 按行拼接numpy数组
    data3 = np.vstack((data[y == 0][:], data[y == 1][:50], data[y == 2][:20], data[y == 3][:5]))
    y3 = np.array([0] * 100 + [1] * 50 + [2] * 20 + [3] * 5)
    cls = KMeans(n_clusters=4, init='k-means++')
    y_hat = cls.fit_predict(data)
    y2_hat = cls.fit_predict(data2)
    y3_hat = cls.fit_predict(data3)
    
    m = np.array(((1, 1),(1, 3)))
    data_r = data.dot(m)
    y_r_hat = cls.fit_predict(data_r)
    
    matplotlib.rcParams['font.sans-serif'] = [u'SimHei']
    matplotlib.rcParams['axes.unicode_minus'] = False
    cm = matplotlib.colors.ListedColormap(list('rgbm'))
    plt.figure(figsize=(9, 10), facecolor='w')
    plt.subplot(421)
    plt.title(u'原始数据')
    plt.scatter(data[:, 0], data[:, 1], c=y, s=30, cmap=cm, edgecolors='none')
    x1_min, x2_min = np.min(data, axis=0)
    x1_max, x2_max = np.max(data, axis=0)
    x1_min, x1_max = expand(x1_min, x1_max)
    x2_min, x2_max = expand(x2_min, x2_max)
    plt.xlim((x1_min, x1_max))
    plt.ylim((x2_min, x2_max))
    plt.grid(True)

    plt.subplot(422)
    plt.title(u'KMeans++聚类')
    plt.scatter(data[:, 0], data[:, 1], c=y_hat, s=30, cmap=cm, edgecolors='none')    
    plt.xlim((x1_min, x1_max))
    plt.ylim((x2_min, x2_max))
    plt.grid(True)

png

elkan k-means算法

参考资料:https://blog.csdn.net/u014465639/article/details/71342072
elkan K-Means利用了两边之和大于等于第三边,以及两边之差小于第三边的三角形性质，来减少距离的计算。
第一种规律是对于一个样本点和两个质心。如果我们预先计算出了这两个质心之间的距离，则如果计算发现,我们立即就可以知道。此时我们不需要再计算,也就是说省了一步距离计算。
第二种规律是对于一个样本点和两个质心。我们可以得到。这个从三角形的性质也很容易得到。
利用上边的两个规律，elkan K-Means比起传统的K-Means迭代速度有很大的提高。但是如果我们的样本的特征是稀疏的，有缺失值的话，这个方法就不使用了，此时某些距离无法计算，则不能使用该算法。

ISODATA算法

参考资料1:https://blog.csdn.net/houston11235/article/details/8511379
参考资料2:https://www.cnblogs.com/huadongw/p/4101422.html
k-means 的一个缺点就是必须指定聚类的个数，这个有些时候并不太行得通。于是就要求最好这个类别的个数也可以改变，这就形成了 isodata 方法，通过设定一些类别分裂和合并的条件，在聚类的过程中自动增减类别的数目。当然这也带来了一个问题，就是这个条件有时候并不那么好给出。当然 isodata 在很多情况下还是可以得到比较靠谱的结果。

Mini Batch k-means（用一部分样本做传统的k-means，舍弃一部分精确度大大提高收敛速度）

参考资料1:https://cloud.tencent.com/developer/article/1465020
Mini Batch KMeans算法是一种能尽量保持聚类准确性下但能大幅度降低计算时间的聚类模型，采用小批量的数据子集减少计算时间，同时仍试图优化目标函数，这里所谓的Mini Batch是指每次训练算法时随机抽取的数据子集，采用这些随机选取的数据进行训练，大大的减少了计算的时间，减少的KMeans算法的收敛时间，但要比标准算法略差一点，建议当样本量大于一万做聚类时，就需要考虑选用Mini Batch KMeans算法。 

'''
    Comparison of the K-Means and MiniBatchKMeans clustering algorithms

'''

print(__doc__)

import time

import numpy as np
import matplotlib.pyplot as plt

from sklearn.cluster import MiniBatchKMeans, KMeans
from sklearn.metrics.pairwise import pairwise_distances_argmin
from sklearn.datasets.samples_generator import make_blobs

# #############################################################################
# Generate sample data
np.random.seed(0)

batch_size = 45
centers = [[1, 1], [-1, -1], [1, -1]] # 初始化3个中心
n_clusters = len(centers) # 聚类的数目为3
# 产生10000组二维数据，以上面三个点为中心，以(-10,10)为边界，数据集的标准差是0.7
X, labels_true = make_blobs(n_samples=10000, centers=centers, cluster_std=0.7)

# #############################################################################
# Compute clustering with Means

k_means = KMeans(init='k-means++', n_clusters=3, n_init=10)
t0 = time.time()
k_means.fit(X)
# 使用k-means对300组数据集训练算法的时间消耗
t_batch = time.time() - t0

# #############################################################################
# Compute clustering with MiniBatchKMeans

mbk = MiniBatchKMeans(init='k-means++', n_clusters=3, batch_size=batch_size,
                      n_init=10, max_no_improvement=10, verbose=0)
t0 = time.time()
mbk.fit(X)
# 使用MiniBatchKMeans对300组数据集训练算法的时间消耗
t_mini_batch = time.time() - t0

# #############################################################################
# Plot result

fig = plt.figure(figsize=(8, 3))
fig.subplots_adjust(left=0.02, right=0.98, bottom=0.05, top=0.9)
colors = ['#4EACC5', '#FF9C34', '#4E9A06']

# We want to have the same colors for the same cluster from the
# MiniBatchKMeans and the KMeans algorithm. Let's pair the cluster centers per
# closest one.
k_means_cluster_centers = np.sort(k_means.cluster_centers_, axis=0)
mbk_means_cluster_centers = np.sort(mbk.cluster_centers_, axis=0)
k_means_labels = pairwise_distances_argmin(X, k_means_cluster_centers)
mbk_means_labels = pairwise_distances_argmin(X, mbk_means_cluster_centers)
order = pairwise_distances_argmin(k_means_cluster_centers,
                                  mbk_means_cluster_centers)

# KMeans
ax = fig.add_subplot(1, 3, 1)
for k, col in zip(range(n_clusters), colors):
    my_members = k_means_labels == k
    cluster_center = k_means_cluster_centers[k]
    ax.plot(X[my_members, 0], X[my_members, 1], 'w',
            markerfacecolor=col, marker='.')
    ax.plot(cluster_center[0], cluster_center[1], 'o', markerfacecolor=col,
            markeredgecolor='k', markersize=6)
ax.set_title('KMeans')
ax.set_xticks(())
ax.set_yticks(())
plt.text(-3.5, 1.8,  'train time: %.2fs\ninertia: %f' % (
    t_batch, k_means.inertia_))

# MiniBatchKMeans
ax = fig.add_subplot(1, 3, 2)
for k, col in zip(range(n_clusters), colors):
    my_members = mbk_means_labels == order[k]
    cluster_center = mbk_means_cluster_centers[order[k]]
    ax.plot(X[my_members, 0], X[my_members, 1], 'w',
            markerfacecolor=col, marker='.')
    ax.plot(cluster_center[0], cluster_center[1], 'o', markerfacecolor=col,
            markeredgecolor='k', markersize=6)
ax.set_title('MiniBatchKMeans')
ax.set_xticks(())
ax.set_yticks(())
plt.text(-3.5, 1.8, 'train time: %.2fs\ninertia: %f' %
         (t_mini_batch, mbk.inertia_))

# Initialise the different array to all False
different = (mbk_means_labels == 4)
ax = fig.add_subplot(1, 3, 3)

for k in range(n_clusters):
    different += ((k_means_labels == k) != (mbk_means_labels == order[k]))

identic = np.logical_not(different)
ax.plot(X[identic, 0], X[identic, 1], 'w',
        markerfacecolor='#bbbbbb', marker='.')
ax.plot(X[different, 0], X[different, 1], 'w',
        markerfacecolor='m', marker='.')
ax.set_title('Difference')
ax.set_xticks(())
ax.set_yticks(())

plt.show()
    Comparison of the K-Means and MiniBatchKMeans clustering algorithms

png

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧