基于K-Means的Feature Location

一、问题描述

本文是对jEdit4.3的特征定位(Feature Location)。采用的核心算法是K-Means算法。通过Python3的scikit-learn、matplotlib、numpy进行实现。

K-means算法是硬聚类算法,是典型的基于原型的目标函数聚类方法的代表,它是数据点到原型的某种距离作为优化的目标函数,利用函数求极值的方法得到迭代运算的调整规则。K-means算法以欧式距离作为相似度测度,它是求对应某一初始聚类中心向量V最优分类,使得评价指标J最小。算法采用误差平方和准则函数作为聚类准则函数。

因为在K-Means算法中,K的选取是非常重要的。在程序的分析过程中,我通过多次迭代的方式,通过轮廓系数作为判断聚类结果的指标,然后找出合适的K值(即jEdit4.3的功能点数量),具体过程见分析与设计章节。

轮廓系数(Silhouette Coefficient)结合了聚类的凝聚度(Cohesion)和分离度(Separation),用于评估聚类的效果。该值处于-1~1之间,值越大,表示聚类效果越好。

二、分析与设计

在这一部分,我按流程的先后对用到的模型、算法、参数选择进行详细的阐述。

1. 词袋模型

词袋,即Bag of words。信息检索中,Bag of words model假定对于一个文本,忽略其词序和语法,句法,将其仅仅看做是一个词集合,或者说是词的一个组合,文本中每个词的出现都是独立的,不依赖于其他词是否出现,或者说当这篇文章的作者在任意一个位置选择一个词汇都不受前面句子的影响而独立选择的。

词袋模型是在自然语言处理和信息检索中的一种简单假设。在这种模型中,文本被看作是无序的词汇集合,忽略语法甚至是单词的顺序。

2. 向量化

在sklearn中提供了TfidfVectorizer和 HashingVectorizer的向量化方式。通过TfidfVectorizer可以将文本转成TF-IDF矩阵,即文本的特征向量。

TF-IDF是一种统计方法,用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加,但同时会随着它在语料库中出现的频率成反比下降。

  • 因为HashingVectorizer是一个无状态模型,不提供IDF权重,如果采用HashingVectorizer的方式,可以通过pipeline的方式添加IDF权重。

  • TfidfVectorizer可以直接生成TF-IDF矩阵,因为后面要做特征定位,所以直接采用TfidfVectorizer的方式更为简单。

3. 特征

尽管TfidfVectorizer中已经提供了默认的tokenizer方法,但并不能完全满足我们的要求。

  • 因为在jEdit4.3的语料库中,像长度小于2、数字等通常是没有什么意义的,对文本聚类没有太大的意义,我们可以在自定义的tokenizer中去掉。

  • 尽管在TF-IDF中会对每个文档中都出现的单词降低其权重,但考虑到不同函数中出现的关键字的多少也有不同,我考虑到将Java语言的关键字统一去掉。

  • 因为jEdit4.3的语料库已经提取过词干,所以我们没有继续提取。

  • 因为可以通过TfidfVectorizer参数的设置来去除停词,所以在自定义的tokenizer中不再重复处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
def token_filter(text):
"""
Return filtered tokens
:param text: text to split into tokens
"""
tokens = [word for word in nltk.word_tokenize(text)]
filtered_tokens = []
for token in tokens:
if re.search('^\D\w*', token) and len(token) > 2 \
and token not in keywords:
filtered_tokens.append(token)
# stems = [SnowballStemmer("english").stem(token) for token in filtered_tokens]
return filtered_tokens

在代码中,前后单词的联系并不是太大,所以在特征的选择上只选取不重复单词,并不对多个单词组合成复杂特征,因此ngram_range采用了默认的参数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
print("Extracting features:")
start = time()
# hasher = HashingVectorizer(stop_words='english',
# non_negative=True,
# norm=None,
# tokenizer=token_filter)
# vectorizer = make_pipeline(hasher, TfidfTransformer())
# vectorizer = HashingVectorizer(stop_words='english',
# norm='l2',
# tokenizer=token_filter)
vectorizer = TfidfVectorizer(stop_words='english',
tokenizer=token_filter,
# ngram_range=(1, 2),
norm='l2')
file = open(corpus_file)
tfidf_matrix = vectorizer.fit_transform(file)
file.close()
print(tfidf_matrix.shape)
print("done in %fs" % (time() - start))

4. 降维

关于降维,通过实验的结果发现,降维并不能提高聚类的准确率。尽管降维的一个重要的作用是减少矩阵的大小,提高后续的效率。但因为特征只选取了3000维左右,并且通过降维后会提高后续Query的复杂性,因此在最终方案的选择上,并没有降维处理。但作为分析过程,在此附上降维的分析过程。

  • 因为TF-IDF矩阵是一个稀疏矩阵,在降维的方法上可以使用sklearn.decomposition 中的TruncatedSVD。

  • 衡量降维后保存的原信息的多少可以通过Explained variance衡量。

因此第一步是要通过多少迭代,确定应该降到多少维是合适的。

1
2
3
4
5
6
7
8
9
10
11
12
13
print("Dimensionality reduction:")
start = time()
n_explained_variances = []
for n_components in range(500, 1500, 100):
svd = TruncatedSVD(n_components)
lsa = make_pipeline(svd, Normalizer(copy=False))
lsa_matrix = lsa.fit_transform(tfidf_matrix)
explained_variance = svd.explained_variance_ratio_.sum()
n_explained_variances.append(explained_variance)
print("Explained variance of the SVD step: {}%".format(int(explained_variance * 100)))
print("done in %fs" % (time() - start))
plt.plot(range(500, 1500, 100), n_explained_variances)

1

如上图所示,x轴代表维度,y轴代表Explained variance。可以发现选择800维是一个合适的值。
降维的话,可以用如下的代码将维度降低到800维:

1
2
3
4
5
6
7
8
9
print("Dimensionality reduction:")
start = time()
svd = TruncatedSVD(800)
lsa = make_pipeline(svd, Normalizer(copy=False))
lsa_matrix = lsa.fit_transform(tfidf_matrix)
explained_variance = svd.explained_variance_ratio_.sum()
print("Explained variance of the SVD step: {}%".format(int(explained_variance * 100)))
print("done in %fs" % (time() - start))

5. 聚类方法

通过对[scikit-learn聚类][1]方法的分析,在数据的平整性、特征大小、类的数目和训练集的评估下,选择K-Means和MiniBatchKMeans(作为测试,可以提高K-Means的速度,但不能提高聚类的效果)作为聚类的方法。

2

K-Means的一个难点是在于K的取值上,我也是通过迭代的方式,来寻找最佳的K值。通过对100到1000范围内步长为100的迭代,通过轮廓系数来对K进行粗略的选择,如果想要提高估计的准确性,可以在确定一个大致的范围后,减少迭代的区间和步长再次进行选择。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
print("KMeans:")
start = time()
k_silhouette_scores = []
for k in range(100, 1000, 100):
km = KMeans(n_clusters=k,
# init='k-means++',
# init='random',
n_init=10)
# km = MiniBatchKMeans(n_clusters=k,
# init_size=1000,
# batch_size=1000,
# n_init=1)
km.fit(lsa_matrix)
silhouette_score = metrics.silhouette_score(lsa_matrix, km.labels_, sample_size=1000)
k_silhouette_scores.append(silhouette_score)
print("%d clusters: Silhouette Coefficient: %0.3f"
% (k, silhouette_score))
print("done in %0.3fs" % (time() - start))
plt.plot(range(100, 1000, 100), k_silhouette_scores)

3

上图所示,x轴表示K的大小,y轴表示轮廓系数的大小。通过分析,最终我选择了K=500对我们的数据进行训练。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
print("KMeans:")
start = time()
k = 500
count = []
km = KMeans(n_clusters=k,
# init='k-means++',
# init='random',
n_init=10)
km.fit(tfidf_matrix)
print("Top terms per cluster:")
clusters = km.labels_.tolist()
order_centroids = km.cluster_centers_.argsort()[:, ::-1]
functions = open(function_file).read().split()
for i in range(k):
count.append(clusters.count(i))
print("Cluster %d:" % i, end='')
for ind in order_centroids[i, :10]:
print(' %s' % functions[ind], end='\n')
print()
print("done in %0.3fs" % (time() - start))
fig = plt.figure(figsize=(15,4))
plt.bar(left = range(k), height = count, width = 4)

在K-Means聚类后,每个类中函数的多少可以表示为下图,x轴表示类,y轴表示函数数量。

4

三、定位与结果

1. Query

因为没有降维,所以对Query来说,比较简单,可以将要Query的内容通过TfidfVectorizer,使用语料库的特征词典来向量化。之后可以通过训练出来的K-Means进行预测。本程序中使用的是有150条Query记录的文件来对150条Query文本做预测。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
print("query vectorizion:")
start = time()
query_vectorizer= TfidfVectorizer(stop_words='english',
tokenizer=token_filter,
ngram_range=(1, 1),
norm='l2',
vocabulary=vectorizer.get_feature_names())
file = open(queries_file)
query_tfidf_matrix = query_vectorizer.fit_transform(file)
file.close()
print(query_tfidf_matrix)
print("done in %fs" % (time() - start))
query_result = km.predict(query_tfidf_matrix)
print(query_result)

如下图所示,这是150条预测的结果。

5

2. 精确率

通过上图发现在本次的运行结果中,第一条Query是被分到第158(Python中索引从0开始)类中,下面我们将第158个类的结果与第一条的good_set取交集,然后进行模型精确率的计算。
因为K-means算法的随机性,预测结果的精确率不会是一个一成不变的值,会因每次执行的K-Means的结果而变化。通过多次实验,发现精确率在5%到10%之间。

1
2
3
4
good_set = set(open(goodset_file).read().split())
print(good_set)
precision = len(set.intersection(my_set, good_set)) / len(my_set)
print(precision)

四、总结

这个问题的难点在于对语料库数据属性的认识,因为通过使用多个聚类方法,特征数量的选取,最终聚类的多少,降维的处理,或者对K-Means的结果再进行层次聚类等,都存在一个类较之其它的类有太多的数据,表现在上面K-Means聚类后的每个类对应函数多少的图上,即y轴方向上较高的那个类。所以我认为这是一种多维上的数据“聚堆”现象。并且没有找到合适的方法来解决这个问题。
另一个问题是对降维后的数据做Query时,因为Query的数据远远少于语料库的数据,所以在维度上很难与特征数据进行匹配。因为就算通过维度转换转换到同一维度上,在每一维上并不一定是有意义的,因此最终并没有使用降维算法。

PS: 机器学习课作业,精确率的计算上存在问题。

四、其它代码

这一章主要是前面没有提及的一些程序部分。

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
%matplotlib inline
from sklearn.decomposition import TruncatedSVD
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.feature_extraction.text import HashingVectorizer
from sklearn.feature_extraction.text import TfidfTransformer
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import Normalizer
from sklearn import metrics
from sklearn.cluster import KMeans, MiniBatchKMeans
import numpy as np
import matplotlib.pyplot as plt
import re
import nltk
# from nltk.stem.snowball import SnowballStemmer
import sys
import os
from time import time
base_dir = os.path.join("/Users", "Jack", "Documents", "Projects", "Python")
corpus_file = os.path.join(base_dir, "Corpus-jEdit4.3CorpusTransformedStemmed.OUT")
keywords_file = os.path.join(base_dir, "javaKeywords.txt")
function_file = os.path.join(base_dir, "Corpus-jEdit4.3.mapping")
queries_file = os.path.join(base_dir, "Queries-jEdit4.3ShortLongDescriptionCorpusTransformedStemmed.OUT")
goodset_file = os.path.join(base_dir, "GoldSet950961.txt")
1
2
keywords = open(keywords_file).read().split()
print(keywords)

五、参考文献

  1. http://scikit-learn.org/dev/modules/clustering.html#clustering
  2. http://scikit-learn.org/dev/auto_examples/text/document_clustering.html#example-text-document-clustering-py
文章目录
  1. 1. 一、问题描述
  2. 2. 二、分析与设计
    1. 2.1. 1. 词袋模型
    2. 2.2. 2. 向量化
    3. 2.3. 3. 特征
    4. 2.4. 4. 降维
    5. 2.5. 5. 聚类方法
  3. 3. 三、定位与结果
    1. 3.1. 1. Query
    2. 3.2. 2. 精确率
  4. 4. 四、总结
  5. 5. 四、其它代码
  6. 6. 五、参考文献
,