Mark Chang's Blog

Machine Learning, Deep Learning and Python

Brown Clustering

Introduction

Clustering 是一種非監督式的機器學習方法。所謂非監督式的學習方法,即是不需要事先提供人工標記好的語料庫給機器學習的演算法。可以直接從未標示的語料庫中,根據既有的特徵來做分類。

例如,可以根據某字的前面或後面有哪些字,來決定哪些字屬於同一類。給一語料庫如下:

The dog runs.

A dog jumps.

The dog jumps.

A cat runs.

The cat jumps.

The cat runs.

根據這些例句,可以把 catdog 歸在同一類,因為它們前面的字是 thea ,同理,也可以把 runjump 歸在同一類。

Defining the Formulation

現在來定義一下,進行這種分類所需要的數學公式。

假設總共有 個字彙, ,和一個分類函數 中的單字分類成 類,

例如, 被分類到類別 ,則

給定語料庫中的句子 ,則可以計算這個句子出現的機率,為:

其中, 為,在類別 中,出現 的機率。

為,若此字的類別為 ,則前一個字的類別為 的機率。

根據先前例子中的語料庫,假設已經分類完成,分類 如下:

並且,可計算出 的機率。 例如, 的機率為:

其中,the 在語料庫中出現的次數。 而 的機率為:

其中, 為,類別為 的字,出現在類別為 的字後面的機會。

給定語料庫中的句子 The dog runs ,那麼可以算出此句的機率為:

其中,把第一個字 the 的前一個字,歸類為第 類,即可求出

再給一個分類,分類 ,這次隨便分,把 thedog 分成一類,把 acat 分成一類,再把 runjump 分成一類,分類如下:

給定語料庫中的句子 The dog runs ,那麼可以算出此句的機率為:

從以上例子得知,用語料庫的句子 The dog runs 來算機率,分類 得出的機率比分類 高。若要得到較理想的分類,可以用語料庫的句子算出的機率,做最佳化,機率較高者,為較理想的分類。

至於,把語料庫中 個單字 分組成 個類別的過程如何?

首先,把 個單字個別分成 組。

再從這些組中挑兩組合併起來,使其得出機率為最大值。合併完後,共有 組。

再來,從這些 組中,再挑兩組合併,以此類推,直到剩下 組。

由於此種演算法的時間複雜度相當高,為[Brown et al., 1992] 提出的 hierarchical clustering 的概念,可有效降低時間複雜度,有興趣者請看延伸閱讀。

Implementation

首先,建立一個程式檔,命名為 bcluster.py

bcluster.py
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
W_CORPUS = [
  ['the','dog','run'], ['a','dog','jump'],
  ['the','dog','jump'], ['a','cat','run'],
  ['the','cat','jump'], ['the','cat','run'],
]

def word_count(c):
  wcount = {}
  for s in c:
    for w in s:
      wcount.update({w:wcount.get(w,0) + 1.0})
  return wcount

def choose_merge(v, w_corpus, w_count):
  max_p, max_v = 0.0, []
  for i in range(len(v)):
    for j in range(i+1,len(v)):
      s1 = [x for x in v]
      s2 = [ s1.pop(i)+s1.pop(j-1) ]+[x for x in s1]
      p = calculate_prob(s2, w_corpus, w_count)
      if p > max_p:
        max_p, max_v = p, s2
  return max_v

def calculate_prob(v, w_corpus, w_count):
  w_class = { w:str(i) for i,s1 in enumerate(['0']+v) for w in s1}
  c_corpus = [[w_class.get(w) for w in s] for s in w_corpus]
  c_count = word_count(c_corpus)
  gran_count = word_count([["_".join(s[i:i+2]) for i in range(len(s))] for s in c_corpus])
  p = 1.0;
  for s in w_corpus:
    for i in range(1,len(s)):
      p = p*e(s[i], w_class, w_count, c_count)*q(s[i], s[i-1], w_class, c_count, gran_count)
  return p

def e(w, w_class, w_count, c_count):
  return w_count[w] / c_count[w_class[w]]

def q(w, wp, w_class, c_count, gran_count):
  return gran_count["%s_%s"%(w_class[wp],w_class[w])] / c_count[w_class[w]]

def bcluster(k, corpus):
  w_count = word_count(corpus)
  w_corpus = [ ['0']+ s for s in corpus]
  v = [[w] for w in w_count.keys()]
  while len(v) > k:
  	print v
    v = choose_merge(v, w_corpus, w_count)
  return v

其中,W_CORPUS 為語料庫,bcluster(k, corpus) 為主要執行 cluster 的函數,參數 k 為總共要分成幾組。

到 python interactive mode 載入模組

1
>>> from bcluster import bcluster,W_CORPUS

根據語料庫中的文字,分成三組,程式印出逐漸將6個字分成3組的過程,最後一行為最終結果:

1
2
3
4
5
6
>>> from bcluster import bcluster,W_CORPUS
>>> bcluster(3,W_CORPUS)
[['a'], ['jump'], ['run'], ['the'], ['dog'], ['cat']]
[['a', 'the'], ['jump'], ['run'], ['dog'], ['cat']]
[['dog', 'cat'], ['a', 'the'], ['jump'], ['run']]
[['jump', 'run'], ['dog', 'cat'], ['a', 'the']]

Reference

本文參考至coursera線上課程

Michael Collins. Natural Language Processing

https://www.coursera.org/course/nlangp

Brown Clustering 出處:

Brown et al. Class-Based n-gram Models of Natural Language, 1992

Comments