聚类
聚类是无监督学习中应用最广泛的算法。聚类会将数据集中的样本划分为若干个不同的子集，每个子集称为一个簇。
原型聚类
原型聚类假设聚类结构能通过一组原型刻画。通常情况下，该类算法先对原型进行初始化，然后对原型进行迭代更新求解。
k均值算法（k-means）
该算法的目的是最小化每个簇中每个样本到对应原型的距离。
但是直接求解的话会是一个NP难问题，较难求解，因此我们仍然采用迭代更新的贪心算法来求解可能的最近似解。值得注意的是，这样并不一定能求得最优解。
其算法大致思想如下：
- 初始化簇的数目K和一组原型向量（从样本中随机选择K个）
- 迭代每个样本和原型向量，为每个样本找到其距离最近的簇，并将其划为到对应的簇中。
- 重新计算每个簇对应的原型向量
- 检查新的原型向量和原来的原型向量是否相等，如果全部更新就停止迭代，即找到了最近似解。
python代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
"""
Created on Tue Aug 10 15:17:10 2021
@author: mw530
"""
import numpy as np
import pandas as pd
class ProBasedClusterin:
clusterNum = 3
data = None
dataLen = 0
clusterVector = []
clusterSplit = []
def __init__(self, data, clusterNum = 3):
self.clusterNum = clusterNum
self.data = data
self.dataLen = data.shape[0]
randArray = self.uniqueRandInt(clusterNum, 0, self.data.shape[0])
for i in range(clusterNum):
self.clusterVector.append(data[randArray[i]])
self.clusterSplit.append([])
def uniqueRandInt(self, num, low, high):
randArray = []
currNum = 0
while currNum < num:
randInt = np.random.randint(low, high)
if randInt not in randArray:
randArray.append(randInt)
currNum += 1
return randArray
def eucDistance(self, x, y):
return np.sqrt(np.sum((x - y)**2))
def train(self):
vectorChangeNum = -1
cycle = 0
while vectorChangeNum != 0:
cycle += 1
vectorChangeNum = 0
for i in range(self.clusterNum):
self.clusterSplit[i] = []
for i in range(self.dataLen):
minDis = 9999999
clusterIndex = -1
for j in range(self.clusterNum):
dis = self.eucDistance(self.data[i], self.clusterVector[j])
if(dis < minDis):
minDis = dis
clusterIndex = j
self.clusterSplit[clusterIndex].append(self.data[i])
print("##############################")
for i in range(self.clusterNum):
vector = np.mean(self.clusterSplit[i], axis=0)
if not (vector == self.clusterVector[i]).all():
vectorChangeNum += 1
self.clusterVector[i] = vector
print("第", cycle, "次遍历", "有", vectorChangeNum, "个原型向量不同")
if vectorChangeNum == 0:
print("找到最佳原型向量，共循环", cycle, "次")
return self.clusterSplit
def loadData(name):
path = './data/' + name
file = open(path, 'r')
csv = pd.read_csv(file)
arr = np.array(csv)
return arr
data = loadData('cetics_game.csv')
clustering = ProBasedClusterin(data)
clusterSplit = clustering.train()
|
学习向量量化（Learning Vector Quantization）
该算法仍然属于原型聚类，因此与K均值相似。也是试图使用一组原型向量来刻画聚类结构。但是该算法假设每个样本有一个标记，学习算法的过程会利用样本的这些监督信息来辅助聚类。
其算法大致思想如下:
- 初始化学习率 μ，原型向量的个数K，K个原型向量（从样本中随机选择）
- 从样本集随机选择一个样本x，迭代每个原型向量，找到距离x最近的原型向量p。
- 根据公式p = p ± μ * (x - p) 更新该原型向量。（如果x与p标记相同为＋，否则为-）
注意该算法的迭代一般就人为确定循环次数。
python代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
"""
Created on Tue Aug 10 18:34:25 2021
@author: mw530
"""
import numpy as np
import pandas as pd
class LearningVectorQuan:
protoVecNum = 0
eTa = 0.5
data = None
dataLen = 0
labels =None
protoVector = []
protoLabels = []
cycleNum = 1000
def __init__(self, data, labels, protoVecNum = 3, eTa = 0.5, cycleNum = 1000):
self.protoVecNum = protoVecNum
self.eTa = eTa
self.cycleNum = cycleNum
self.data = data
self.labels = labels
self.dataLen = self.data.shape[0]
randInt = self.uniqueRandInt(self.protoVecNum, 0, self.dataLen - 1)
for i in randInt:
self.protoVector.append(self.data[i])
self.protoLabels.append(self.labels[i])
def uniqueRandInt(self, num, low, high):
randArray = []
currNum = 0
while currNum < num:
randInt = np.random.randint(low, high)
if randInt not in randArray:
randArray.append(randInt)
currNum += 1
return randArray
def eucDistance(self, x, y):
return np.sqrt(np.sum((x - y)**2))
def train(self):
for i in range(self.cycleNum):
randIndex = np.random.randint(0, self.dataLen - 1)
randData = self.data[randIndex]
randLabel = self.labels[randIndex][0]
minIndex = -1
minDis = 9999999
for j in range(self.protoVecNum):
dis = self.eucDistance(randData, self.protoVector[j])
if dis < minDis:
minDis = dis
minIndex = j
if randLabel == self.labels[minIndex]:
self.protoVector[minIndex] = self.protoVector[minIndex] + self.eTa * (randData - self.protoVector[minIndex])
else:
self.protoVector[minIndex] = self.protoVector[minIndex] - self.eTa * (randData - self.protoVector[minIndex])
return self.protoVector
def loadData(name):
path = './data/' + name
file = open(path, 'r')
csv = pd.read_csv(file)
arr = np.array(csv)
return arr[:, :-1], arr[:, -1:]
data, labels = loadData('cetics_game.csv')
clustering = LearningVectorQuan(data, labels)
clusterSplit = clustering.train()
print(np.array(clusterSplit).shape)
|
高斯混合聚类（高斯分布即正态分布）
与以上两种算法不同，该算法使用的概率模型来表达聚类原型。
密度聚类
该算法亦称为“基于密度的聚类”，此类算法假设聚类结构能够通过样本分布的紧密程度确定。并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。
DBSCAN是一种著名的密度聚类算法，它基于一组“邻域”参数（ε，MinPts）来刻画样本分布的紧密程度。给定数据集D，有一下几个概念需要了解。
- ε-邻域：对于xi∈D，其ε-邻域包括样本集D中与xi距离不大于ε的所有样本。
- 核心对象：若xi的ε-邻域中至少包含MinPts个样本，则xi为一个核心对象。
- 密度直达：若xi位于xj的ε-邻域中，且xj是一个核心对象，则称xi由xj密度直达。
- 密度可达：对于xi和xj，若存在样本序列p1, p2, p3, … , pn，其中p1 = xi, pn = xj, 且pi+1由pi密度直达，则称xj由xi密度直达。
- 密度相连：对xi与xj，若存在xk使得xi与xj均由xk密度可达，则称xi与xj密度相连。
该算法的核心思想如下：
- 算法先根据给定的邻域参数（ε， MinPts）找出所有的核心对象
- 以任一核心对象为出发点，找出由其密度可达的样本生成聚类簇，直到所有核心对象均被访问过。
层次聚类
层次聚类（hierarchical clustering）试图在不同层次上对数据集进行划分，从而形成树状的聚类结构。数据集的划分可以采用自底向上的聚类策略，也可以采用自顶而下的分拆策略。
AGNES是以这种采用自底向上聚类策略的层次聚类算法。
其算法思想如下：
- 它先将数据集中的每个样本看作一个初始聚类簇。
- 然后再算法运行的每一步中找出距离最近的两个聚类进行合并，该过程不断重复，直到达到预设的聚类簇个数。
注意：以上的代码都是自己手写的，可能会有不足。
