一、問題描述
本文是對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中不再重複處理。
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) > \
and token not in keywords:
filtered_tokens.append(token)
# stems = [SnowballStemmer("english").stem(token) for token in filtered_tokens]
return filtered_tokens
在代碼中，前後單詞的聯系并不是太大，是以在特征的選擇上隻選取不重複單詞，并不對多個單詞組合成複雜特征，是以ngram_range采用了預設的參數。
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衡量。
是以第一步是要通過多少疊代，确定應該降到多少維是合适的。
print("Dimensionality reduction:")
start = time()
n_explained_variances = []
for n_components in range(, , ):
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 * )))
print("done in %fs" % (time() - start))
plt.plot(range(, , ), n_explained_variances)
如上圖所示，x軸代表次元，y軸代表Explained variance。可以發現選擇800維是一個合适的值。
降維的話，可以用如下的代碼将次元降低到800維：
print("Dimensionality reduction:")
start = time()
svd = TruncatedSVD()
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 * )))
print("done in %fs" % (time() - start))
5. 聚類方法
通過對scikit-learn聚類方法的分析，在資料的平整性、特征大小、類的數目和訓練集的評估下，選擇K-Means和MiniBatchKMeans（作為測試，可以提高K-Means的速度，但不能提高聚類的效果）作為聚類的方法。
K-Means的一個難點是在于K的取值上，我也是通過疊代的方式，來尋找最佳的K值。通過對100到1000範圍内步長為100的疊代，通過輪廓系數來對K進行粗略的選擇，如果想要提高估計的準确性，可以在确定一個大緻的範圍後，減少疊代的區間和步長再次進行選擇。
print("KMeans:")
start = time()
k_silhouette_scores = []
for k in range(, , ):
km = KMeans(n_clusters=k,
# init='k-means++',
# init='random',
n_init=)
# 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=)
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(, , ), k_silhouette_scores)
上圖所示，x軸表示K的大小，y軸表示輪廓系數的大小。通過分析，最終我選擇了K=500對我們的資料進行訓練。
print("KMeans:")
start = time()
k =
count = []
km = KMeans(n_clusters=k,
# init='k-means++',
# init='random',
n_init=)
km.fit(tfidf_matrix)
print("Top terms per cluster:")
clusters = km.labels_.tolist()
order_centroids = km.cluster_centers_.argsort()[:, ::-]
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, :]:
print(' %s' % functions[ind], end='\n')
print()
print("done in %0.3fs" % (time() - start))
fig = plt.figure(figsize=(,))
plt.bar(left = range(k), height = count, width = )
在K-Means聚類後，每個類中函數的多少可以表示為下圖，x軸表示類，y軸表示函數數量。
三、定位與結果
1. Query
因為沒有降維，是以對Query來說，比較簡單，可以将要Query的内容通過TfidfVectorizer，使用語料庫的特征詞典來向量化。之後可以通過訓練出來的K-Means進行預測。本程式中使用的是有150條Query記錄的檔案來對150條Query文本做預測。
print("query vectorizion:")
start = time()
query_vectorizer= TfidfVectorizer(stop_words='english',
tokenizer=token_filter,
ngram_range=(, ),
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條預測的結果。
2. 精确率
通過上圖發現在本次的運作結果中，第一條Query是被分到第158（Python中索引從0開始）類中，下面我們将第158個類的結果與第一條的good_set取交集，然後進行模型精确率的計算。
因為K-means算法的随機性，預測結果的精确率不會是一個一成不變的值，會因每次執行的K-Means的結果而變化。通過多次實驗，發現精确率在5%到10%之間。
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: 機器學習課作業，精确率的計算上存在問題。
四、其它代碼
這一章主要是前面沒有提及的一些程式部分。
%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")
keywords = open(keywords_file).read().split()
print(keywords)
五、參考文獻
- http://scikit-learn.org/dev/modules/clustering.html#clustering
- http://scikit-learn.org/dev/auto_examples/text/document_clustering.html#example-text-document-clustering-py