机器学习笔记（3）

2023-12-16 16:15| 来源: 网络整理| 查看: 265

聚类分析是一种无监督机器学习（训练样本的标记信息是未知的）算法，它的目标是将相似的对象归到同一个簇中，将不相似的对象归到不同的簇中。如果要使用聚类分析算法对一堆文本分类，关键要解决这几个问题：

如何衡量两个对象是否相似算法的性能怎么度量如何确定分类的个数或聚类结束的条件选择哪种分类算法

下面就带着这几个问题，以我工作中的一个业务需求为例，来学习一下怎么对中文文本进行聚类。（此文略长，包含了理论基础、算法院里、代码实现和实验效果分析）

一. 业务需求

我在工作中遇到这样一个需求：有个铁路通信专业的业务系统，收集了一些通信设备的生产厂商信息，共4500多条。由于数据是人工录入的，非常不规范，存在数据重复、信息不规范、错别字等现象，需要对数据进行分析归类，将相同或相似的数据划到一起，再通过人工审核规范数据，最终形成规范的字典数据。

二、理论基础 1. 相似度计算欧氏距离

欧氏距离是一种常用的距离定义，指在m维空间中两个点之间的真实距离，对多维向量A=(A1，A2，……,An)，B=(B1，B2，……,Bn)，欧氏距离的计算公式如下：

余弦相似度

余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体差异的大小。相比欧氏距离度量，余弦相似度更加注重两个向量在方向上的差异，而非距离或长度上的差异。余弦值的计算公式如下：

相对于欧氏距离，余弦相似度更适合计算文本的相似度。首先将文本转换为权值向量，通过计算两个向量的夹角余弦值，就可以评估他们的相似度。余弦值的范围在[-1,1]之间，值越趋近于1，代表两个向量方向越接近；越趋近于-1，代表他们的方向越相反。为了方便聚类分析，我们将余弦值做归一化处理，将其转换到[0,1]之间，并且值越小距离越近。

2. 性能度量

在选择聚类算法之前，首先来了解什么样的聚类结果是比较好的。我们希望同一个簇内的样本尽可能相似，不同簇的样本尽可能不同，也就是说聚类结果的“簇内相似度”高且“簇间相似度”低。

考虑聚类结果的簇划分 $C={\left \{ C_{1},C_{2}, ...,C_{K}\right \}}$ ，定义：

$avg(C)=\frac{2}{(|C|(|C|-1))}\sum_{1\leq i j\leq \left | C \right |}dist(x_i,x_j)$

$diamC=max_{1\leq i j\leq \left | C \right |}dist(x_{i},x_{j})$

$d_{min} (C_i,C_j )= min_{x_i\in C_i,x_j\in C_j} dist(x_i,x_j)$

$d_{cen} (C_i,C_j )=dist(\mu _i,\mu_j)$

其中， $\mu$ 代表簇 $C$ 的中心点； $avg(C)$ 代表簇 $C$ 内样本的平均距离； $diamC$ 代表簇 $C$ 内样本间的最远距离； $d_{min} (C_i,C_j )$ 对应于簇 $C_i$ 和 $C_j$ 簇最近样本间的距离； $d_{cen} (C_i,C_j )$ 对应于簇 $C_i$ 和 $C_j$ 中心点间的距离。基于以上公式可导出下面两个常用的聚类性能度量内部指标：

DB指数（Davies-Bouldin Index，简称DBI）

$DBI=\frac{1}{k}\sum_{i=1}^{k}max_{j\neq i}\left ( \frac{avg(C_i)+avg(C_j)}{d_{cen}(C_i,C_j)} \right )$

Dumn指数（Dumn Index，简称DI）

$DI=min_{1\leqslant i\leq k}\left \{ min_{j\neq i}\left ( \frac{d_{min}(C_i,C_j)}{max_{1\leqslant l\leq k}diam(C_l)} \right ) \right \}$

DB指数的计算方法是任意两个簇内样本的平均距离之和除以两个簇的中心点距离，并取最大值，DBI的值越小，意味着簇内距离越小，同时簇间的距离越大；Dumn指数的计算方法是任意两个簇的最近样本间的距离除以簇内样本的最远距离的最大值，并取最小值，DI的值越大，意味着簇间距离大而簇内距离小。因此，DBI的值越小，同时DI的值越大，意味着聚类的效果越好。

三、聚类过程

有了相似度计算方法和性能度量这两个理论基础，下面就开始对文本分类了。

1. 分词

要对中文文本做聚类分析，首先要对文本做分词处理，例如“联想移动通信科技有限公司”，我们希望将其切分为“联想移动通信科技有限公司”。python提供专门的中文切词工具“jieba”，它可以将中文长文本划分为若干个单词。

为了提高分类的准确率，还要考虑两个干扰因素：一是英文字母大小写的影响，为此我们将英文字母统一转换为大写；二是例如 “有限”、“责任”、“股份”、“公司”等通用的词汇，我们将这样的词汇连同“（）”、“-”、“/”、“&”等符号作为停用词，将其从分词结果中去除掉，最后得到有效的词汇组合，代码和结果如下：

# 加载停用词，这里主要是排除“有限公司”一类的通用词 def loadStopWords(fileName): dataMat = [] fr = open(fileName) words = fr.read() result = jb.cut(words, cut_all=True) newWords = [] for s in result: if s not in newWords: newWords.append(s) newWords.extend([u'（', u'）', '(', ')', '/', '-', '.', '-', '&']) return newWords # 把文本分词并去除停用词，返回数组 def wordsCut(words, stopWordsFile): result = jb.cut(words) newWords = [] stopWords = loadStopWords(stopWordsFile) for s in result: if s not in stopWords: newWords.append(s) return newWords # 把样本文件做分词处理，并写文件 def fileCut(fileName, writeFile, stopWordsFile): dataMat = [] fr = open(fileName) frW = open(writeFile, 'w') for line in fr.readlines(): curLine = line.strip() curLine1 = curLine.upper() # 把字符串中的英文字母转换成大写 cutWords = wordsCut(curLine1, stopWordsFile) for i in range(len(cutWords)): frW.write(cutWords[i]) frW.write('\t') frW.write('\n') dataMat.append(cutWords) frW.close()

2. 构建词袋模型

文本被切分成单词后，需要进一步转换成向量。先将所有文本中的词汇构建成一个词条列表，其中不含重复的词条。然后对每个文本，构建一个向量，向量的维度与词条列表的维度相同，向量的值是词条列表中每个词条在该文本中出现的次数，这种模型叫做词袋模型。例如，“阿尔西集团”和“阿尔西制冷工程技术(北京)有限公司”两个文本切词后的结果是“阿尔西集团”和“阿尔西制冷工程技术北京”，它们构成的词条列表是[阿尔西, 集团, 制冷, 工程技术, 北京]，对应的词袋模型分别是[1,1,0,0,0]，[1,0,1,1,1]。

# 创建不重复的词条列表 def createVocabList(dataSet): vocabSet = set([]) for document in dataSet: vocabSet = vocabSet | set(document) return list(vocabSet) # 将文本转化为词袋模型 def bagOfWords2Vec(vocabList, inputSet): returnVec = [0] * len(vocabList) for word in inputSet: if word in vocabList: returnVec[vocabList.index(word)] += 1 else: print "the word: %s is not in my Vocabulary!" % word return returnVec 3. 权值转换

TF-IDF是一种统计方法，用来评估一个词条对于一个文件集中一份文件的重要程度。TF-IDF的主要思想是：如果某个词在一篇文章中出现的频率TF高，并且在其他文件中很少出现，则认为此词条具有很好的类别区分能力，适合用来分类。将词袋向量转换为TF-IDF权值向量，更有利于判断两个文本的相似性。

TF(词频，term frequency)：

$tf_{i,j} =\frac{n_{i,k}}{\sum_{k}n_{k,j}}$

分子是词条 $t_i$ 在文件 $d_j$ 中出现的次数，分母是文件 $d_j$ 中所有词条出现的次数之和。

IDF(逆向文件频率，inverse document frequency)：

$idf_i=log\frac{\left | D \right |}{\left |\left \{ j:t_i\in d_j \right \} \right |}$

对数内的分子是文件总数，分母是包含词条 $t_i$ 的文件数，如果该词不存在，就会导致分母为零，因此一般使用 $1+\left |\left \{ j:t_i\in d_j \right \} \right |$ 作为分母。

$tfidf_{i,j} = tf_{i,j}\times idf_i$

# 计算所有文本包含的总词数 def wordsCount(dataSet): wordsCnt = 0 for document in dataSet: wordsCnt += len(document) return wordsCnt # 计算包含某个词的文本数 def wordInFileCount(word, cutWordList): fileCnt = 0 for i in cutWordList: for j in i: if word == j: fileCnt = fileCnt + 1 else: continue return fileCnt # 计算权值,并存储为txt def calTFIDF(dataSet, writeFile): allWordsCnt = wordsCount(dataSet) # 所有文本的总词数 fileCnt = len(dataSet) # 文本数 vocabList = createVocabList(dataSet) # 词条列表 # tfidfSet = [] frW = open(writeFile, 'w') for line in dataSet: wordsBag = bagOfWords2Vec(vocabList, line) # 每行文本对应的词袋向量 lineWordsCnt = 0 for i in range(len(wordsBag)): lineWordsCnt += wordsBag[i] # 计算每个文本中包含的总词数 tfidfList = [0] * len(vocabList) for word in line: wordinfileCnt = wordInFileCount(word, dataSet) # 包含该词的文本数 wordCnt = wordsBag[vocabList.index(word)] # 该词在文本中出现的次数 tf = float(wordCnt) / lineWordsCnt idf = math.log(float(fileCnt) / (wordinfileCnt + 1)) tfidf = tf * idf tfidfList[vocabList.index(word)] = tfidf frW.write('\t'.join(map(str, tfidfList))) frW.write('\n') # tfidfSet.append(tfidfList) frW.close() 4. 计算余弦相似度

前面已经介绍过，相对欧氏距离，余弦相似度更适合文本分类，Python实现如下：

# 计算余弦距离 def gen_sim(A, B): num = float(dot(mat(A), mat(B).T)) denum = linalg.norm(A) * linalg.norm(B) if denum == 0: denum = 1 cosn = num / denum sim = 0.5 + 0.5 * cosn # 余弦值为[-1,1],归一化为[0,1],值越大相似度越大 sim = 1 - sim # 将其转化为值越小距离越近 return sim 5. 使用K-均值聚类算法分类

K-均值是将数据集划分为k个簇的算法，簇的个数k是用户给定的，每个簇通过其质心（簇中所有点的中心）来描述。K-均值算法的工作流程是：

（1）随机确定k个初始点作为质心。

（2）将数据集中的每个点找到距离最近的质心，并将其分配到该质心对应的簇中。

（3）将每个簇的质心更新为该簇中所有点的平均值。

（4）重复第（2）、（3）步骤，直到簇的分配结果不再变化。

为了评价聚类的质量，定义一种用于衡量聚类效果的指标SSE（Sum of Squared Error，误差平方和），误差是指样本到其质心的距离。SSE值越小，表示数据点越接近质心。

由于K-均值算法是随机选取质心，因此可能会收敛到局部最小值，而非全局最小值。为了克服这个问题，提出了一种二分K-均值算法。该算法的思路是将所有点作为一个簇，然后将该簇一分为二。之后选择一个能最大程度降低SSE值的簇继续进行划分，直到得到用户指定的簇数目为止。

注意：该算法需要确定簇的个数，而我的需求中分类的个数是未知的。因此，希望通过观察性能度量指标DI和DBI的变化趋势来确定一个合适k值。

性能度量指标的实现：

# 计算簇内两个样本间的最大距离 def diamM(dataSet): maxDist = 0 m = shape(dataSet)[0] if m > 1: for i in range(m): for j in range(i + 1, m): dist = gen_sim(dataSet[i, :], dataSet[j, :]) if dist > maxDist: maxDist = dist return maxDist # 计算两个簇间，样本间的最小距离 def dMin(dataSet1, dataSet2): minDist = 1 m = shape(dataSet1)[0] n = shape(dataSet2)[0] for i in range(m): for j in range(n): dist = gen_sim(dataSet1[i, :], dataSet2[j, :]) if dist < minDist: minDist = dist return minDist # 计算簇内样本间的平均距离 def avg(dataSet): m = shape(dataSet)[0] dist = 0 avgDist = 0 if m > 1: for i in range(m): for j in range(i + 1, m): dist += gen_sim(dataSet[i, :], dataSet[j, :]) avgDist = float(2 * dist) / (m * (m - 1)) return avgDist

二分K-均值算法实现：

def biKmeans(dataSet, k, distMeas=gen_sim): m = shape(dataSet)[0] clusterAssment = mat(zeros((m, 2))) SSE = [] # 用于记录每次迭代的总误差 DI = 0 # DI指数，用于衡量簇间的相似度，值越大越好 DBI = 0 dmin = 1 diam = [] diam.append(diamM(dataSet)) centroid0 = mean(dataSet, axis=0).tolist()[0] centList = [centroid0] # 创建质心列表，初始只有一个质心 for j in range(m): # 计算初始的平方误差 clusterAssment[j, 1] = distMeas(centroid0, dataSet[j, :]) ** 2 SSE.append([0, sum(clusterAssment[:, 1]), 1, 0]) while (len(centList) < k): # 聚类数小于k时 lowestSSE = inf for i in range(len(centList)): # 对每个质心循环 # 获取第i个质心对应的数据集（簇） ptsInCurrCluster = dataSet[nonzero(clusterAssment[:, 0].A == i)[0], :] # 对该簇使用k均值算法，分为2个簇 centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas) # 计算该簇的总误差 sseSplit = sum(splitClustAss[:, 1]) # 计算未分割的其他簇的总误差 sseNotSplit = sum( clusterAssment[nonzero(clusterAssment[:, 0].A != i)[0], 1]) # print "sseSplit, and notSplit: ",sseSplit,sseNotSplit if (sseSplit + sseNotSplit) < lowestSSE: # 寻找最小误差对应的簇 bestCentToSplit = i bestNewCents = centroidMat bestClustAss = splitClustAss.copy() lowestSSE = sseSplit + sseNotSplit # 更新簇的分配结果，将多分出来的簇作为最后一个簇 bestClustAss[nonzero(bestClustAss[:, 0].A == 1)[0], 0] = len( centList) # change 1 to 3,4, or whatever bestClustAss[nonzero(bestClustAss[:, 0].A == 0)[0], 0] = bestCentToSplit # 更新质心列表 centList[bestCentToSplit] = bestNewCents[0, :].tolist()[0] centList.append(bestNewCents[1, :].tolist()[0]) # 更新分类结果 clusterAssment[nonzero(clusterAssment[:, 0].A == bestCentToSplit)[0], :] = bestClustAss index = len(centList); error = sum(clusterAssment[:, 1]) # 新划分的两个簇 newDataSet1 = dataSet[ nonzero(clusterAssment[:, 0].A == bestCentToSplit)[0], :] newDataSet2 = dataSet[ nonzero(clusterAssment[:, 0].A == len(centList) - 1)[0], :] # 计算DI指数，该值越大越好 diam1 = diamM(newDataSet1) diam2 = diamM(newDataSet2) diam[bestCentToSplit] = diam1 diam.append(diam2) for l in range(len(centList) - 1): dataSetl = dataSet[nonzero(clusterAssment[:, 0].A == l)[0], :] dist = dMin(dataSetl, newDataSet2) if dist < dmin: dmin = dist DI = float(dmin) / max(diam) # 计算DBI指数，该值越小越好 maxDBI = 0 sumDBI = 0 DBI = 0 for i in range(len(centList)): for j in range(i + 1, len(centList)): dataSeti = dataSet[nonzero(clusterAssment[:, 0].A == i)[0], :] dataSetj = dataSet[nonzero(clusterAssment[:, 0].A == j)[0], :] DBIij = (avg(dataSeti) + avg(dataSetj)) / gen_sim( mat(centList[i]), mat(centList[j])) if DBIij > maxDBI: maxDBI = DBIij sumDBI += maxDBI DBI = sumDBI / len(centList) SSE.append([index, error, DI, DBI]) print '---' + getTime() + '---' print u'误差最小的簇是: ', bestCentToSplit print u'该簇的长度是: ', len(bestClustAss) print u'分为%d个簇，误差是%f' % (index, error) print u'分为%d个簇，DI值是%f,DBI值是%f' % (index, DI, DBI) return mat(centList), clusterAssment, mat(SSE)

由于计算DI和DBI值的复杂度较高，先选取500多个样本测试一下效果，得到的趋势如下图所示，然而结果并不理想，DBI值趋于不变，DI值的变化趋势也没有规律。同时，分别对500多个样本划分为200、300、420个簇，经过人工校验，被成功聚类的样本分别为111个、106个、105个。由此可以推断，K-均值算法不适合对厂商名称的分类，分析其原因可能是每个厂商名称所包含的词汇量太少。接下来我们再尝试另一种聚类算法——层次聚类。

6. 使用层次聚类算法

层次聚类试图在不同的层次对数据集进行划分，可以采用“自底向上”的聚类策略，也可以采用“自顶向下”的分拆策略。一般采用“自底向上”的策略，它的思路是先将数据集中的每个样本看作一个初始聚类簇，然后找出两个聚类最近的两个簇进行合并，不断重复该步骤，直到达到预设的聚类个数或某种条件。关键是如何计算两个簇之间的距离，每个簇都是一个集合，因此需要计算集合的某种距离即可。例如，给定簇 $C_i$ 和 $C_j$ ，可通过以下3种方式计算距离：

最小距离： $d_{min}(C_i,C_j)=min_{x\in C_i,z\in C_j}dist(x,z)$ 最大距离： $d_{max}(C_i,C_j)=max_{x\in C_i,z\in C_j}dist(x,z)$ 平均距离： $d_{avg}(C_i,C_j)=\frac{1}{\left | C_i \right |\left | C_j \right |}\sum_{x\in C_i}\sum_{z\in C_j}dist(x,z)$

最小距离由两个簇的最近样本决定，最大距离由两个簇的最远样本决定，平均距离由两个簇的所有样本决定。

接下来要考虑如何确定一个合适的聚类个数或某种结束条件，具体思路是：

（1）选定一部分测试样本，对其进行层次聚类分析。

（2）记算性能度量指标DBI和DI的变化趋势，结合人工校验，得到一个合适的聚类个数和对应的距离阈值。

（3）将此距离阈值作为聚类结束的条件，对所有样本做聚类分析。此时无需再计算DBI和DI值，计算效率可以大幅提升。

# 计算两个簇的最小距离 def distMin(dataSet1, dataSet2): minD = 1 m = shape(dataSet1)[0] n = shape(dataSet2)[0] for i in range(m): for j in range(n): dist = gen_sim(dataSet1[i], dataSet2[j]) if dist < minD: minD = dist return minD # 计算两个簇的最大距离 def distMax(dataSet1, dataSet2): maxD = 0 m = shape(dataSet1)[0] n = shape(dataSet2)[0] for i in range(m): for j in range(n): dist = gen_sim(dataSet1[i], dataSet2[j]) if dist > maxD: maxD = dist return maxD # 计算两个簇的评均距离 def distAvg(dataSet1, dataSet2): avgD = 0 sumD = 0 m = shape(dataSet1)[0] n = shape(dataSet2)[0] for i in range(m): for j in range(n): dist = gen_sim(dataSet1[i], dataSet2[j]) sumD += dist avgD = sumD / (m * n) return avgD # 找到距离最近的两个簇 def findMin(M): minDist = inf m = shape(M)[0] for i in range(m): for j in range(m): if i != j and M[i, j] < minDist: minDist = M[i, j] minI = i minJ = j return minI, minJ, minDist # 层次聚类算法 def hCluster(dataSet, k, dist, distMeas=distAvg): m = shape(dataSet)[0] clusterAssment = mat(zeros((m, 1))) performMeasure = [] M = mat(zeros((m, m))) # 距离矩阵 # 初始化聚类簇，每个样本作为一个类 for ii in range(m): clusterAssment[ii, 0] = ii for i in range(m): for j in range(i + 1, m): dataSeti = dataSet[nonzero(clusterAssment[:, 0].A == i)[0], :] dataSetj = dataSet[nonzero(clusterAssment[:, 0].A == j)[0], :] M[i, j] = distMeas(dataSeti, dataSetj) M[j, i] = M[i, j] if mod(i,10) == 0: print i q = m # 设置当前聚类个数 minDist = 0 # while (q > k): while (minDist < dist): i, j, minDist = findMin(M) # 找到距离最小的两个簇 # 把第j个簇归并到第i个簇 clusterAssment[nonzero(clusterAssment[:, 0].A == j)[0], 0] = i for l in range(j + 1, q): # 将j之后的簇重新编号 clusterAssment[nonzero(clusterAssment[:, 0].A == l)[0], 0] = l - 1 M = delete(M, j, axis=0) M = delete(M, j, axis=1) for l in range(q - 1): # 重新计算第i个簇和其他簇直接的距离 dataSeti = dataSet[nonzero(clusterAssment[:, 0].A == i)[0], :] dataSetl = dataSet[nonzero(clusterAssment[:, 0].A == l)[0], :] M[i, l] = distMeas(dataSeti, dataSetl) M[l, i] = M[i, l] DBI = DBIvalue(dataSet, clusterAssment, q) DI = DIvalue(dataSet, clusterAssment, q) performMeasure.append([q - 1, minDist, DBI, DI]) q = q - 1 print '---' + getTime() + '---' print u'当前簇的个数是：', q print u'距离最小的两个簇是第%d个和第%d个,距离是%f,DBI值是%f,DI值是%f' % ( i, j, minDist, DBI, DI) return clusterAssment, mat(performMeasure)

仍然选择K-均值聚类分析的500多个样本，对其进行层次聚类，得到的性能指标变化趋势如下：

从上图可以看出，DI值呈下降趋势，DBI值呈阶跃上升趋势，根据性能度量的规则（DBI的值越小越好；DI的值越大越好），最优值可能出现阶跃点附近，即划分为471类和445类两个点，同时结合人工校验，可以确定445类更加合理。

接下来，将k值设置为445进行层次聚类分析，发现仍有少量相似的样本被划分到不同的类。根据业务需求，为了减少后续的核实工作量，我们希望将相似的样本尽可能划分到同一类中，同时可以接受少部分不同的样本划分到同一类，我们给予k值适当的冗余，将其设置为420，再分别基于最大距离、最小距离、平均距离进行分析。

距离计算方法

聚到簇中的样本数

最佳距离

最大距离

160

0.2975

最小距离

167

0.2556

平均距离

167

0.2839

从以上分类结果看出，采用层次聚类算法对测试样本进行分类，效果明显优于K-均值聚类算法。并且，该算法可以通过学习得到距离阈值作为聚类结束的条件，从而解决了分类个数k值无法确定的问题。

为了降低个别样本对整体结果的影响，选择基于平均距离的距离分析算法，并将距离阈值设置为0.29，对4574个样本做聚类分析，最后得到3128个类，看一下部分样本的分类效果：

四、总结

对文本聚类主要有几个步骤：对文本分词、构建词袋模型、权值转换、计算余弦相似度、选取聚类算法、性能度量、确定聚类结束条件。如果文本所含的词汇量较多，并且已知分类的个数k，可以选择二分K-均值聚类算法。而层次聚类算法根据样本距离来分类，并且可以以样本距离作为分类结束的条件，比较适合k未知的情况。

代码资源下载地址（留言回复可能不及时，请您自行下载）： https://download.csdn.net/download/leaf_zizi/12073625

网盘下载链接: https://pan.baidu.com/s/1EXyaEfQ2K-JVe4mbX41c-Q 提取码: ghas（下载后记得给文章点赞哦）

参考：

周志华《机器学习》

Peter Harrington 《机器学习实战》

https://blog.csdn.net/songzhilian22/article/details/49636725/

【本文地址】

公司简介

联系我们