    \documentclass[japanese]{jnlp_1.4}
\usepackage{jnlpbbl_1.2}
\usepackage[dvips]{graphicx}
\usepackage{amsmath}
\usepackage{hangcaption_jnlp}
\usepackage{udline}
\setulminsep{1.2ex}{0.2ex}
\let\underline
\usepackage{array}


\Volume{17}
\Number{1}
\Month{January}
\Year{2010}

\received{2009}{4}{30}
\revised{2009}{6}{24}
\rerevised{2009}{9}{15}
\accepted{2009}{10}{2}

\setcounter{page}{77}

\jtitle{文字列を特徴量とし反復度を用いたテキスト分類}
\jauthor{尾上　　徹\affiref{ICS-Toyohasi} \and 平田　勝大\affiref{ICS-Toyohasi} \and 岡部　正幸\affiref{IMC-Toyohasi} \and 梅村　恭司\affiref{ICS-Toyohasi}}
\jabstract{
テキスト分類における特徴抽出とは，分類結果を改善するためにテキストの特徴たる単語または文字列を取捨選択する手続きである．ドキュメントセットのすべての部分文字列の数は，通常は非常に膨大であるため，部分文字列を特徴として使用するとき，この操作は重要な役割を果たす．

本研究では，部分文字列の特徴抽出の方法に焦点を当て，反復度と呼ばれる統計量を使って特徴抽出する方法を提案する．反復度は，高確率でドキュメントに二度以上出現する文字列は文書のキーワードであるはずだという仮定に基づく統計量であり，この反復度の性質は，テキスト分類にも有効であると考える．実験では，Zhangら(Zhang 
et al. 2006)によって提案された，条件付確率を用いることで分布が類似した文字列をまとめるという手法（以下，条件付確率の方法と記す）と我々の提案する手法の比較を行う．結果の評価には適合率と再現率に基づくF値を用いることとした．ニュース記事とスパムメールの分類実験の結果，我々の提案する反復度を用いた特徴抽出法を用いると，条件付確率の方法を用いるのに比べて，ニュース記事の分類では分類結果を平均79.65{\%}から平均83.39{\%}に改善し，スパムメールの分類では分類結果を平均90.23{\%}から平均93.15{\%}に改善した．提案手法である反復度を用いる特徴抽出法はZhangらの提案する条件付確率を用いる特徴抽出法に比べて，ニュース分類記事の分類では平均3.74{\%}，スパムメールの分類では平均2.93{\%}だけ結果を改善しており，その両方の実験において結果に有意差があることを確認した．

また，反復度を用いる特徴抽出方法を用いると，単語を特徴集合とする方法を用いる場合と比べて，ニュース記事の分類では分類の結果を平均83.88{\%}から平均83.39{\%}と平均0.49{\%}低下させることとなったものの，スパムメールの分類では分類の結果を平均92.11{\%}から平均93.15{\%}と平均1.04{\%}改善した．ニュース記事の分類においては反復度を用いる特徴抽出方法と単語を特徴集合とする方法に有意差は本実験では認められず，スパムメールの分類の結果においては有意差があることを確認した．

この結果が得られた要因について考察すると，条件付確率の方法を用いたほうは一見しただけでは何の部分文字列かわからないほど短い文字列を抽出する傾向にあることが分かった．これは不特定多数の文字列の一部として出現しやすいことを意味しており，文書の特徴になりえないような文字列がこれを含んでいたとき，分類結果がその文字列の影響を受けることを意味する．それに対して反復度で抽出した部分文字列は短い文字列もあるものの，長い文字列や間に空白が挟まった単語をつなぐ部分文字列も捉えているため，特定のものをさす文字列の部分文字列であるといえる．このような何を指しているのかわかりやすいある程度長い部分文字列と，間に空白を挟んだ単語と単語を結ぶような形の部分文字列が分類結果を改善していると考えられる．
}
\jkeywords{テキストマイニング，テキスト分類，機械学習，特徴選択}

\etitle{Extracting String Features with Adaptation for Text Classification}
\eauthor{Toru Onoe\affiref{ICS-Toyohasi} \and Katsuhiro Hirata\affiref{ICS-Toyohasi} \and Masayuki Okabe\affiref{IMC-Toyohasi} \and Kyoji Umemura\affiref{ICS-Toyohasi}} 
\eabstract{
Feature selection for text classification is a procedure that categorizes 
words or strings to improve the classification performance. This operation 
is especially important when we use substrings as a feature because the 
number of substrings in a given data set is usually quite large.

In this paper, we focus on the substring feature selection technique and 
describe a method that uses a statistic score called ``adaptation'' as a 
measure for the selection. Adaptation works on the assumption that strings 
appearing more than twice in a document have a high probability of being 
keywords; we expect this feature to be an effective tool for text 
classification. We compared our method with a state-of-the-art method 
proposed by Zhang et al. that identifies a substring feature set by removing 
redundant substrings that are similar in terms of statistical distribution. 
We evaluate the classification results by F-measure that is a harmonic mean 
of precision and recall. An experiment on news classification demonstrated 
that our method outperformed Zhang's by 3.74{\%} (it improves Zhang's result 
from 79.65{\%} to 83.39{\%}) on average based on the classification results. 
In addition, an experiment on spam classification demonstrated that our 
method outperformed Zhang's by 2.93{\%} (it improves the Zhang's result from 
90.23{\%} to 93.15{\%}). We verified existence of significant difference 
between the results in each experiment.

An experiment on news classification shows that our method is worse than a 
method of using word for feature by 0.49{\%} (although there is no 
significant difference) on average based on the classification results. In 
addition, an experiment on spam classification demonstrated that our method 
outperformed the word method by 1.04{\%} (our method improves its result 
from 92.11{\%} to 93.15{\%}). We verified that there is a significant 
difference between the results in spam classification experiment.

Zhang's method tends to extract substrings that are so short it is difficult 
to understand the original phrases from which they are extracted. This 
degrades classification performance because such a substring can be a part 
of many different words, some or most of which are unrelated to the original 
substring. Our method, on the other hand, avoids this pitfall because it 
selects substrings containing a limited number of original words. Selecting 
substrings in such a manner is the key advantage of our method. 
}
\ekeywords{Text Mining, Text Classification, Machine Learning, Feature Selection}

\headauthor{尾上，平田，岡部，梅村}
\headtitle{文字列を特徴量とし反復度を用いたテキスト分類}


\affilabel{ICS-Toyohasi}{豊橋技術科学大学情報工学系}{Information and Computer Science, Toyohashi University of Technology}
\affilabel{IMC-Toyohasi}{豊橋技術科学大学情報メディア基盤センター}{Information and Media Center, Toyohashi University of Technology}


\begin{document}
\maketitle

\section{はじめに}

テキスト分類学習は，スパムメールの除去，Webコンテンツのフィルタリング，ニュースの自動分類など様々な応用分野をもつ重要な技術である．

一般の分類学習と同様に，テキスト分類学習においても特徴集合の選択は学習性能を決定する重要な要素である．通常，英文であればスペースによって区切られた語，日本語文であれば形態素解析によって分割された語を特徴として用いることが多いが，このような方法では二語が連接していることの情報が欠落するので，分類に役立つ熟語・複合語などの情報を取りこぼす可能性が高い．このため，この情報についてはあきらめるか辞書から得るかしなければならない．さらにこの情報を利用する場合は言語モデルの利用やstring 
kernelなどの特殊なカーネルを利用することにより学習アルゴリズム側で連接を考慮するといった対応を行う必要が生じる．

一方，特徴選択の方法として文を文字列と見なし，全ての部分文字列を考慮することで，連接を特徴選択の際に取り込もうとするアプローチがある．このアプローチでは，熟語・複合語を取り込むための辞書や連接を考慮した学習アルゴリズムを使用する必要がないという利点があるが，部分文字列数のオーダーはテキストデータの全文字数の2乗のオーダーという非常に大きな値となってしまうため，取捨選択してサイズを縮小する必要がある．部分文字列を考慮した特徴選択の代表的なものに，Zhangらが提案した方法がある(Zhang et al. 2006)．彼らはsuffix 
treeを利用して，出現分布が同一または類似している文字列を一つにまとめることによって特徴集合のサイズを縮小する方法を提案した．そして，この選択方法による特徴集合とサポートベクターマシンを利用したテキスト分類実験において，連接や文字列を考慮した他の代表的な方法よりも高い性能を与えることを示した．

これに対して，本研究ではすべての部分文字列を考慮する点は同じものの，反復度と呼ばれる統計量を利用して，Zhangらの方法と異なる部分文字列の選択方法を提案する．反復度は文書内で繰り返される文字列は文書内容を特徴づける上で重要な語であるという仮定に基づく統計量であり，これまでキーワード抽出などに利用されている(Takeda and Umemura 2002)．Zhangらの方法は部分文字列の出現分布が類似したものを一つにまとめるという操作のみを行い，選択した部分文字列の文書内容を特徴づける上での重要性は学習アルゴリズムによって決めるというアプローチであるといえるが，反復度では特徴選択時にも部分文字列の重要性を考慮しており，分類に寄与しない特徴を予め取り除く効果が期待できる．本研究では，この反復度を用いた部分文字列からの特徴選択の効果を，ニュース記事を用いた分類実験，スパムメールのデータセットを用いた分類実験において検証する．そして，ニュース記事の分類実験では，提案手法である反復度を用いた特徴抽出方法がZhangらの特徴抽出方法よりも優れた結果を示し，単語を特徴集合とする方法との間には有意差が認められなかったことを報告する．一方，スパムメールの分類実験において提案手法はZhangらの方法，単語を特徴集合とする方法よりも優れた結果を示し，有意差が確認されたことを報告する．

以下，2章ではZhangらの方法について詳しく説明する．また3章では本研究で利用する反復度と交差検定によるパラメータの設定方法について説明する．4章では実験方法と実験結果について述べ，5章でその結果について考察し，6章でまとめを行う．


\section{Zhangらの特徴選択方法}

ここではテキスト分類における特徴選択の先行研究として，Zhangらが提案した方法について詳しく説明する．

テキスト分類に用いる機械学習アルゴリズムの多くは，学習の際のデータ表現に文書ベクトルを用いるが，通常このベクトルの値として，以下のtf値，df値を元に計算したtfidfと呼ばれる値が使用される．

\begin{itemize}
\item tf(t, d): 文字列tが文書dに出現する頻度
\item df(t, D): コーパスD中で文字列tが出現する文書数
\item tfidf(t, d): tfidf(t, d) = tf(t, d) $\cdot$ log($\vert $D$\vert $/df(t, D)) \\
{\kern-0.5zw}（$\vert $D$\vert $はコーパスDの文書数を表す）
\end{itemize}

Zhangらは，膨大な部分文字列を削り込むために出現分布が同一または類似している文字列をまとめ，上で述べた値に違いのあるものをなるべく特徴として選択するというアプローチを採用した．ここで，出現分布が同一または類似している文字列とは，ある文字列のコーパス中におけるすべての出現場所をリストにしたとき，そのリストが別の文字列が持つ出現場所リストと等しいまたは類似している文字列のことを指す．

出現分布が同一な文字列はtf値とdf値について同じ値を持つため，学習において区別する必要はなく，ひとつの特徴としてまとめてしまう．具体的な手続きとしては，出現場所のリストが等しい文字列のうち，最も文字列長が短い文字列のみを代表文字列として選択する．また，出現場所のリストが厳密に等しくなくても類似していれば，そのような文字列のtf値，df値にも大きな違いは生じないため，これらの文字列をひとつの特徴にまとめても分類結果に余り影響を与えることなく，特徴集合を減らすことができると考えられる．

ただし出現場所の類似性の判定には基準が必要なので，Zhangらは類似した文字列を取り除くための条件を以下のようにした．

\begin{enumerate}
\item コーパス中である文字列の次に現れる文字の種類がb種類未満の文字列は特徴集合から取り除く．
\item ある文字列 (S$_{1}$) が現れたとき，この文字列から始まる文字列 (S$_{2}$) が出現する条件付確率P(S$_{2}\vert $ S$_{1})$がp以上であるならば，後者の文字列を特徴集合から取り除く．
\item ある文字列(S$_{3}$) が現れたとき，この文字列で終わる文字列 (S$_{4}$) が出現する条件付確率P(S$_{4}\vert $S$_{3})$がq以上であるならば，特徴集合から後者の文字列を取り除く．
\end{enumerate}

また，コーパス中で出現頻度が極端に多い文字列，少ない文字列は分類に寄与しないと考え，最小頻度l未満の文字列，最大頻度h以上の文字列は特徴集合から除く．

以上の処理により，特徴集合の大きさを，全部分文字列を特徴集合とした場合に比べ大幅に小さくすることができる．これらの処理を行うには5つのパラメータl, 
h, b, 
pおよびqを決定する必要があるが，これらは学習文書における交差検定法によって推定する．Zhangらは以上の処理をsuffix 
treeを用いて効率的に行う方法を提案し，英語，中国語およびギリシャ語のコーパスを用いてテキスト分類の実験を行ったところ，これまでに提案されてきた主な文字列ベースのテキスト分類手法，例えば，言語モデルを利用した生成アプローチ(Peng 2004)やstring kernel を利用した識別アプローチ(Lodhi 2001)などの方法よりも優れた性能を示したと報告している．



\section{提案手法}


\subsection{反復度による特徴量抽出}

本研究では，出現分布が同一または類似した文字列をまとめることに加え，ある文書に偏って出現する文字列をテキスト分類の重要な特徴として残すことを考え，Zhang 
らが用いた手法の条件 (1), (2), (3)の代わりに反復度と呼ばれる統計量を用いることによって文字列を選択する方法を提案する．

反復度 adapt(t, D)は，語tが出現した文書のうち，2回以上繰り返し出現している文書の割合を示す統計量で以下のように定義される．
\[
 \text{adapt} (t,D) = \frac{\text{df}_{2}(t,D)}{\text{df}(t,D)}
\]

ここで，df$_{2}$(t, D)はコーパスD中の文書で，文字列tが2 
回以上出現する文書数を表す．



表 1は，ある英文中における反復度の変化の様子を示したものである．ただし，「{\_}」は空白を表す．この例では，「natural{\_}gas{\_}」に1文字追加して「natural{\_}gas{\_}s」となったときに反復度が急激に減少している様子が示されている．表 
1に見られるように，反復度はある境界を境にそれまでほぼ一定だった値が急激に減少する統計量であり，df 
/ $\vert $D$\vert 
$で計算される出現確率とは異なり，意味的に一塊の語の境界で減少することが多いことから，キーワードの自動抽出(Takeda and Umemura 2002)などに利用されている．表 
1の例においても，「natural{\_}gas{\_}」で語が区切られることは，その意味を考えると妥当であるといえる．提案する方法では，出現分布が等しい文字列をその代表文字列だけにまとめることはZhangらと同じであるが，2章で説明した (1), (2), (3)の条件の代わりに，以下の条件を用いる．

\begin{itemize}
\item 反復度が最小反復度a未満の文字列は特徴集合から取り除く
\end{itemize}

\begin{table}[t]
\caption{語の境界における反復度の変化}
\input{05table01.txt}
\end{table}


Zhangらの (1), (2), (3) の条件を用いていないため，出現分布が類似していてもひとつにまとめず別の特徴として扱う．ただし，出現分布が等しい文字列はひとつの特徴にまとめるため，表 
1のような1文字ずつ増加させたような文字列が必ず選ばれるわけではなく，単語中の語幹や連語単位の文字列などを特徴集合に含めることができる(平田 他 2007)．表1の例では，「nat」と「natu」の 2 
つ，「natural{\_}」，「natural{\_}g」，「natural{\_}ga」の3つは出現場所のリストが等しく，統計量も同じなので，それぞれ「nat」と「natural{\_}」だけを特徴として選択する．また，「natural{\_}gas」のような連語も特徴として選択される．


\subsection{交差検定法によるパラメータの設定}

提案手法では，最小頻度l，最大頻度h といったパラメータに加え，最小反復度a 
を決定する必要があるが，本研究ではZhangらと同じく交差検定法によって推定する．交差検定法とは，未知のデータに対するモデルのパラメータを推定する方法のひとつである．本研究で用いる4分割交差検定法は，学習文書を4つのブロックに分割し，それぞれのブロックをテスト文書とし，テストに使用していない残りのブロックを学習文書に使用する．この4回のテキスト分類において最も分類性能が良くなるパラメータを最適なパラメータとして推定する．以上のように，パラメータの推定のテスト文書に学習文書とは別の文書を使用し，元の学習文書のすべての文書を順にテスト文書として使用することで，過学習を防ぐパラメータを決定することができ，学習における汎化性能の向上が期待される．



\section{実験}

実験は，ニュースのトピック分類とSpam分類の2種類のタスクについて行い，それぞれのタスクについて，関連研究の手法の分類結果と反復度による特徴集合を用いた場合の分類結果の比較を行う．


\subsection{ニュースのトピック分類実験}

この実験には，Reuters-21578\footnote{
	http://www.daviddlewis.com/resources/testcollections/reuters21578/}と
20newsgroups\footnote{
	http://people.csail.mit.edu/jrennie/20Newsgroups/}の
2つの英語コーパスを使用し，各文書には前処理として，アルファベット以外の文字を空白に変換し，2文字以上空白が続く場合は空白1文字に変換するという処理を行う．

テキスト分類に適用可能な分類学習器は数多くあるが，本実験では特徴選択方法の比較を行うので，適切と考えられる分類学習器について実験を行った．分類学習器にはZhangらの先行研究と同じく線形カーネルを利用したSVMを用いる．線形カーネルを利用したSVMの識別関数は次式のように表される．
\[
 f(\mathbf{x})= \sum^{d}_{j=1} w_{j} x_{j} + b
\]
ここで，\textbf{x}は識別対象となる文書ベクトル，x$_{j}$は\textbf{x}の要素jの値，w$_{j}$は重みベクトル\textbf{w}の要素jの値，dは\textbf{x}の要素数，bはバイアス項である．\textbf{w}とbは学習によって決定される．

我々の提案手法では，\textbf{x}の要素集合として，反復度によって特徴選択した文字列集合を用いる．また，比較対象として，2章の先行研究において説明した条件付確率によって特徴選択した文字列集合を\textbf{x}の要素集合とした方法をベースラインに用いる．また，単語を特徴集合とする方法との比較として，最小出現頻度lと最大出現頻度hで選択した単語集合を\textbf{x}の要素集合とした方法とも比較する．x$_{j}$の値は3手法ともtfidfによって計算された値を用いる．tfidfの計算式は2章で記述した式を用いる．

実際のSVMの学習には，SVMツールのひとつであるSVMlight\footnote{ 
http://svmlight.joachims.org/}を使用し，すべてデフォルトのパラメータで学習を行う．複数トピックの分類に対しては，ターゲットとするトピックに属する文書を正例，そのトピックに属さない文書を負例とした2クラスによる学習を各トピックについて行う．結果の評価には次の3つの尺度を利用する．
{\allowdisplaybreaks
\begin{align*}
\text{適合率} & =\frac{\text{トピックに属すると分類した文書の正解文書数}}
	{\text{トピックに属すると分類した文書数}}  \\[1zw]
\text{再現率} & = \frac{\text{トピックに属すると分類した文書の正解文書数}}
	{\text{コーパス中の正解文書数}} \\[1zw]
\text{F値} & = \frac{2 \times \text{適合率} \times \text{再現率}}
	{\text{適合率} + \text{再現率}}
\end{align*}
}


\subsubsection{Reuters-21578}

Reuters-21578は，英語のテキスト分類の標準的なコーパスであり，先行研究でも用いられている．このコーパスのうち，「ModApte」学習・テストセットを使用し，本文のうちTITLEタグとBODYタグのついた文書を使用する．さらに，Reuter-21578の文書に含まれるトピックのうちの文書数の多い上位10トピックについてテキスト分類を行う．ただし，各文書は複数のトピックに属することがあり，その場合，正例として使用される文書は負例として同時に使用しないこととした．分類は，ひとつの文書が各トピックに対して属するか属さないかをSVMを用いて判定することによって行う．学習には，学習用文書セットの全9,603文書を使用し，テストには学習文書とは異なるテストセットの全3,299文書を使用する．表2に学習セットおよびテストセットにおける上位10トピックの正例の文書数を示す．後述の実験において，正例の文書数が少ないときに提案方法が優位であることを述べるために，このデータを示した．このコーパスに対して，次の3つの特徴集合を用いた場合のテキスト分類を行い，その結果を比較する．


\begin{table}[b]
\caption{学習セットの文書数}
\input{05table02.txt}
\end{table}

\begin{itemize}
\item 反復度：提案手法である，反復度を用い文字列を選択した特徴集合
\item 条件付確率：Zhangら(Zhang and Lee 2006)が提案した条件付確率を用いて文字列を選択した特徴集合．ベースラインとして用いる．
\item 単語：スペースを区切りとした単語からなる特徴集合
\end{itemize}

また，各特徴集合のパラメータ設定と選択された特徴数を以下に示す．

\begin{itemize}
\item 反復度：l=80, h=8000, a=0.3（3章参照）として7,099文字列が選択された．
\item 条件付確率：l=80, h=8000, b=8, p=0.8, q=0.8（2章参照）として8,438文字列が選択された．
\item 単語：l=10, h=8000として6,581単語が選択された．
\end{itemize}

条件付確率による手法のパラメータは先行研究と同様のパラメータを使用し，反復度のパラメータおよび単語の特徴選択のパラメータは学習用文書セットでの4分割交差検定法においてF値の平均が最も良くなる値を調べ決定している．ただし，文字列を特徴集合とする場合は，空白で始まる文字列は特徴集合からは除く．これは，英語の単語が空白で区切られているためである．以上の実験結果を図1, 図2, 図3, 表3に示す．


\begin{figure}[b]
\begin{center}
\includegraphics{17-1ia5f1.eps}
\end{center}
 \caption{適合率}
\end{figure}
\begin{figure}[b]
\begin{center}
\includegraphics{17-1ia5f2.eps}
\end{center}
 \caption{再現率}
\end{figure}

図1および図2に注目して文字列に対する特徴選択を比較すると，トピック上位3つのearn, 
acqおよびmoney-fxについては条件付確率による特徴集合を用いたトピック分類との差が適合率，再現率ともにほとんどないが，これら以外の7トピックについては，反復度による特徴集合を用いたトピック分類の方が結果が良くなり，特に再現率が大きく改善された．図3，表3のF値でも同様に，上位3トピックのearn, 
acqおよびmoney-fxでは条件付確率を用いた場合と比べてF値はあまり変わらないが，これら以外のトピックでは反復度を用いた方が改善された．

\begin{figure}[t]
\begin{center}
\includegraphics{17-1ia5f3.eps}
\end{center}
 \caption{F 値}
\end{figure}
\begin{table}[t]
\caption{F値}
\input{05table03.txt}
\end{table}

10個のトピックの内，反復度が優れた結果を出したものは8個であり，劣った結果であってもF値は0.20{\%}しか差が出ない．一方，マクロ平均ではF値に3.74{\%}の差があり，反復度の方が良い性能を示した．マイクロ平均ではF値に約1.39{\%}の差があり，反復度の方が良い性能を示した．ただし，このコーパスにおいてはearnとacqで全体の約65{\%}のドキュメントがあり，文書数が偏っている．これはこのテストセットに特殊なケースであり，カテゴリごとの平均で比較する方が実際の性能を反映すると考えられる．単語を特徴集合とした方法と比較すると，図3，表3のように，結果の優劣はトピック毎に異なる．10トピック中6トピックについては反復度による方法の方が，F値が良くなるという結果になった．F値のマクロ平均は反復度による方法と単語による方法を比較するとほぼ等しくなった．



\subsubsection{20newsgroups}

20newsgroupsは20のトピックに属する文書からなる．分類は，Reuters-21578と同様にひとつの文書が各トピックに属するか属さないかをSVMを用いて判定することによって行う．このコーパスには，学習文書11,314とテスト文書7,532文書が含まれており，トピック間での文書数の違いはあまりない．実験では，文書中のFrom，Subjectおよびニュース本文の文書から特徴に使用する部分文字列を選択し，テキスト分類を行う．この実験における，各特徴集合のパラメータ設定と選択された特徴数は以下の通りである．

\begin{itemize}
\item 反復度：l=100, h=200000, a=0.1として69,653文字列が選択された．
\item 条件付確率：l=100, h=200000, b=8, p=0.8, q=0.8として24,732文字列が選択された．
\item 単語：l=5, h=10000として26,573単語が選択された．
\end{itemize}

l, h, aのパラメータは学習文書での4分割交差検定法によって再設定した．ただし，このコーパスにおいてもReuters-21578と同様に，先頭が空白で始まる文字列は特徴として用いる文字列から除外した．また，学習時に負例の文書数が正例と比べ非常に多いことがSVMのモデルに大きな影響を与えてしまったため，正例と負例の判定エラーに対するコスト比の値を文書数の比に近い値である20に設定し学習を行う．以上の条件において20のトピックに分類した結果，F値のマクロ平均は反復度による方法で76.05{\%}，条件付確率による方法で74.75{\%}，単語による方法で76.71{\%}となった．このように，このコーパスにおいても反復度による特徴選択の方が条件付確率による特徴選択よりも良い性能を示した．トピックごとの比較では，20トピック中10トピックにおいて反復度による方法が単語よりも良くなるという結果になった．しかしながら，その差はほとんどないといえる．


\subsection{Spam分類実験}

本実験ではTREC 2006 Spam Corpus\footnote{ 
http://trec.nist.gov/data/spam.html}をコーパスとして用いた．このコーパスはSpam分類のために作られたもので，コーパスにはヘッダ情報が含まれ，一般的な英語文章とは異なる構造をしているという特徴がある．コーパスの資料には正確な定義はないが，コーパス作成者が主観的に有用なテキストをHam，それ以外をSpamとしたものと考えられる．これを用いた実験で分類精度が向上すれば，実際のSpam分類においても分類精度が向上すると考えられる．


\subsubsection{実験方法}

トレーニングデータとしてSpam, Ham 
それぞれ100個，分類対象（テストデータ）として，Spam, Ham 
それぞれ200個をランダムに選ぶ．記号，マルチバイト文字は前処理段階でカットし，分類に用いない．このようにして20個の文書セットを構成し，この文書セットそれぞれに対して以下の分類実験を行う．

まず，学習データから次の3つの特徴集合を構成する．

\begin{itemize}
\item 反復度を用いて特徴選択した文字列からなる特徴集合 (AS) 
\item 条件付確率を用いて特徴選択した文字列からなる特徴集合 (CS)
\item スペースを区切りとした単語からなる特徴集合 (WS)
\end{itemize}

各手法のパラメータは文書セットごとに交差検定により設定する．ただし，条件付確率による手法のパラメータは先行研究(Zhang 
et al. 
2006)と同様の値を用いることとする．また，反復度による手法のパラメータl, hは条件付き確率と同様の値に設定する．テキストの学習分類は4.1節と同様に行い，評価も4.1節と同様にF値を用いて行うこととする．


\subsubsection{実験結果}

4.2.1節で述べたようにトレーニング，テストデータのセットを20個作り，それぞれに対して，特徴集合としてAS, CS, WSそれぞれを用いて分類を行う．このようにして得られた分類結果を表 
4に示す．表 4において，このF値は (SpamのF値+HamのF値) / 2 として得た平均値である．表 
5には各文書セットに対する反復度の手法のパラメータaと，単語の手法のパラメータlを示す．ここで，反復度の手法のパラメータはaを交差検定で求め，l, hはl=80, h=8000で固定し，条件付確率の手法のパラメータはl=80, h=8000, b=8, p=0.8, q=0.8で固定する．また，単語の手法のパラメータlは交差検定で求め，hはh=8000で固定とした．これは，h=8000を設定すると各文書セットで良い分類結果を示し，その付近で変化させても分類結果に影響がなかったためである．表では固定されたパラメータについては表記を省略したが，本文中に記したパラメータを使った．


表 4を見ると，文書セットを変えたときには平均的に反復度が優れた分類結果を示し，条件付確率がもっとも悪い結果を示していることがわかる．反復度を用いた結果は単語を用いた結果より平均1.04{\%}，条件付確率を用いた結果より平均2.93{\%}だけF値が高い．表から，全20の文書セットすべての分類結果において，反復度を用いた方が条件付き確率を用いるよりも良い分類結果を示していることが分かる．このことから，反復度を用いて選択した文字列を特徴集合とするのは条件付確率を用いる方法と比較して有効であると考えられる．反復度を用いる方法と単語を用いる方法のF値を比較すると，20回の分類実験のうち，反復度が単語よりも良い結果となったのが16回で，悪い結果となったのが3回，同じ値となったのが1回であった．この結果について符号検定を行い，両手法のF値の間に有意な差があるかどうかを考える．まず，帰無仮説H$_{0}$と対立仮説H$_{1}$を以下に示すように定める．

\begin{table}[t]
\caption{各手法の平均 F 値}
\input{05table04.txt}
\end{table}
\begin{table}[t]
\caption{設定したパラメータ}
\input{05table05.txt}
\vspace{-0.5\baselineskip}
\end{table}

\begin{itemize}
\item H$_{0}$：反復度を用いる方法と単語を用いる方法のF値の間に差がない．
\item H$_{1}$：反復度を用いる方法は単語を用いる方法のF値の間に差がある．
\end{itemize}

両手法の結果が同じ値となった場合，単語を用いる方法の方が優れていると見なすと，
\pagebreak
両手法のF値の分布が等しいという仮定の下で単語を用いる方法の結果が20回の内4回反復度よりも良くなる確率は，
\[
 \frac{1}{2^{20}}({}_{20}C_{4} + {}_{20}C_{3} + {}_{20}C_{2} + {}_{20}C_{1} + 1) 
	= 0.0059089 \cdots < 0.01
\]
となるため，有意水準1{\%}で帰無仮説は棄却され，対立仮説が採択される．このことから，反復度を用いる方法は単語を用いる手法よりもF値において有意な差があると考えることができる．表 
5をみると，単語の手法のパラメータlはほとんどが10以下で，まれに大きな値をとることがわかる．また，反復度の手法のパラメータaは0.2から0.4程度の値をとることがわかる．


\section{考察}


\subsection{ニュースのトピック分類}

まず，文字列に対する2つの特徴選択方法，提案手法である反復度による方法とベースラインである条件付確率による方法を比較する．4.1節の実験において，学習文書とテスト文書に同じ文書集合を用いてみると，F値のマクロ平均は，反復度を用いた方法では92.87{\%}，条件付確率を用いた方法では95.17{\%}となり，条件付確率による特徴集合の方が全体的にF値が高くなる．学習文書とテスト文書に異なる文書集合を用いる本来の評価では，4.1節で説明したように反復度による特徴集合の方がF値が高いことから，条件付確率を用いた特徴集合では，反復度を用いた場合に比べ，過学習してしまう傾向があると考えられる． 

ここで，各手法で選択された文字列を比較すると，共通して選択されたのは1,400文字列で，特徴集合全体に比べて小さい．2つの手法で選択される文字列の差を直感的に理解しやすい例をこの文字列から一つ示す．トピックのひとつであるshipに注目し，このトピックに含まれる学習文書を見るとトピック名である「ship」という単語が含まれていることがわかった．それぞれの手法で選択された文字列のうちこの単語に関連する文字列を表 
6に示す．

\begin{table}[b]
\caption{特徴文字列}
\input{05table06.txt}
\end{table}

条件付確率による特徴選択に比べて，反復度による特徴選択では，直前に現れる単語の最後の1文字加えた文字列や統計的には類似している文字列が追加で選択されている．これらのうち共通していない2文字列を特徴集合から取り除いて実験を行ったところ，shipの分類結果が75.68{\%}から73.10{\%}に減少した．これは，shipに含まれる文書中の「foreign 
ships」や「own 
shipping」のような文字列の特徴をテキスト分類に使用したためだと考えられる．連語そのものを検出しているとはいえないが，連語の情報を利用できていることが示唆される．

また，単語を特徴集合とする方法に比べ，提案手法は同等の性能を示したものの有意差は認められなかった．しかしながら，提案手法は区切り文字のないデータにおいて，単語抽出を行うための事前処理が必要なく，また上記の連語などのような情報を損なうことのないといった利点がある．


\subsection{Spam分類}

実験結果から，部分文字列を特徴集合とする2つの方法を比較すると，反復度で特徴選択した場合の方が，分類結果が良いことがわかる．そこで，ここでは両者の特徴集合を比較し，どのような文字列によりこの差が生まれたのかについて考察する．

この考察のために，4.2.1節で生成した20の文書セットの内の一つに相当する別の文書セット1個を生成した．これ一つについて分類を行い，反復度と条件付確率それぞれによる特徴集合を取り出す．さらに反復度について，特徴集合のうちサポートベクトルとして使用された文字列を抽出する．この分類実験の結果として表 
7に示すデータが得られた．


\begin{table}[b]
\begin{minipage}[t]{105pt}
\caption{手法ごとのF値}
\input{05table07.txt}
\end{minipage}
\hfill
\begin{minipage}[t]{280pt}
\caption{文字列集合の記号との対応と大きさ}
\input{05table08.txt}
\end{minipage}
\end{table}

このとき，各手法のパラメータは次のように設定した．

\begin{itemize}
\item 反復度：l=80, h=8000, a=0.3
\item 条件付確率：l=80, h=8000, b=8, p=0.8, q=0.8
\end{itemize}

ここで，表 
8のように記号を定義する．ISはASにあってCSにはない文字列の集合であるため，この文字列の中に条件付確率を用いた場合に比べて分類結果を改善する原因となった文字列が含まれていると考えられる．ISがどれほど分類に寄与しているかと，たとえばどのような文字列が寄与しているかを調べるため以下の2つの実験（[実験1]，[実験2]）を行い，その結果を用いて考察する．

\noindent
\textbf{[実験1]}

ここでは，$\text{AS}-\text{IS}$ を特徴集合として分類を行う．この分類の結果として表 
9の実験1-aに示されるF値を得た．結果を見ると，反復度で特徴抽出した場合よりも7.00{\%}，条件付確率で特徴抽出した場合よりも2.00{\%}だけF値が下がっていることがわかる．このことから，ISの文字列はF値を7.00{\%}上昇させることがわかる．また，このときのF値がCSで分類したときよりも下がっていることから，反復度では捉えることができなかったが条件付確率では捉えることができた分類に役立つ文字列があったことがわかる．ただし，ISのうち実際に分類に使われるものは 
IS$\cap $SV（大きさは1628）であるから，IS$\cap 
$SVをASから取り除いた場合とISを取り除いた場合の結果は同じである．

\noindent
\textbf{[実験2]}

 実験1からIS$\cap 
$SVが分類結果を改善しているということがわかった．ここでは，実際にどのような文字列が分類に寄与しているのかについて調べる．

まず，考察のために作成した文書セットの分類において反復度が選んだ特徴集合 (AS) の内サポートベクトルとして用いられた部分文字列 (SV) の重みw$_{j}$（4.1節参照）を計算する．そして，w$_{j}$が大きいほど分類に寄与していると考え，その上位50の文字列をとりだす．その集合とISの積をとり，それをASから取り除いて分類を行う．この結果として表 
9の実験2-aに示されるF値を得た．この結果を見ると，反復度で特徴抽出した場合よりも2.50{\%}だけF値が下がっていることがわかる．この50個の文字列を調べると，message{\_}idという文字列の一部と推測できる部分文字列12個が含まれていることが分かった．これはたとえば表 
10に示されるような文字列である．ここで「 {\_} 」は空白を意味することとする．

\begin{table}[b]
\hfill\begin{minipage}[t]{100pt}
\caption{条件ごとのF値}
\input{05table09.txt}
\end{minipage}
\hfill
\begin{minipage}[t]{210pt}
\caption{見つかったmessage{\_}idの部分文字列の一部}
\input{05table10.txt}
\end{minipage}
\hfill
\end{table}


ただし，この12個の部分文字列はすべてCSに含まれていないことが分かった．これらをASから取り除いて分類するとF値は表 
9の実験2-bに示される値となった．このように，これを除去することで F 値が下がるという結果から，明らかにこれらの部分文字列は分類に役立っていることがわかる．

SV全体からmessage{\_}idの部分文字列を探したところ26個見つかり，ISとの積をとると16個の文字列が得られた．この16個の文字列をASから取り除き分類するとF値は表 
9の実験2-cに示される値となった．この結果からも，message{\_}idの部分文字列群は役立っていることが示唆される．ここで，CSにも含まれている10個のmessage{\_}idの部分文字列を除去した場合，F値は変化しなかった．よって，CSに含まれない16個の部分文字列はCSに含まれる10個の部分文字列をカバーするといえる．

 このmessage{\_}idという文字列がコーパスのSpam, Hamメールのうちどれぐらい含まれるのかを調べたところ，Spamメールの約81.9{\%}，Hamメールの約99.9{\%}にこれが含まれていることがわかった．よってこれが含まれていないとほぼSpamと断定できる文字列であるということがわかり，これは分類に有用であるということは直感的に理解できる．

message{\_}idという文字列の一部がCSにも含まれており（26個中10個），CSに含まれない16個の部分文字列をASから取り除き分類すると分類結果が悪くなることは先に述べた．ではなぜ10個の文字列はCSに含まれない16個をカバーできなかったのか，それらの文字列の違いについてここでは考える．考察のために，表 
11に反復度，条件付確率それぞれの手法が捉えたmessage{\_}idの部分文字列を示す．

\begin{table}[t]
\caption{反復度と条件付確率の特徴集合の比較}
\input{05table11.txt}
\end{table}

表 11を見ると，条件付確率の手法を用いたほうは一見しただけでは何の部分文字列かわからないほど短い文字列である．これは別の意図しない文字列に対しても分類結果が引きずられやすい，つまり文字列message{\_}idを意図してmeを選択してもmemberやmeatなどの別の文字の部分文字列と解釈される可能性があるということである．それに対して反復度で抽出した部分文字列は短い文字列もあるが，かなり長い文字列も捉えており，age{\_}iなど間に空白が挟まった形も捉えているため，不特定多数の文字列の一部となりえない特定のものをさす文字列の部分文字列であるといえる．このような何を指しているのかわかりやすいある程度長い部分文字列と，間に空白を挟んだ単語と単語を結ぶような形の部分文字列が分類結果を改善していると考えられる．


\section{まとめ}

文字列によるテキスト分類において，条件付確率を用いて文書の特徴集合を選択する代わりに，反復度を用いて特徴選択を行い，ニュース記事のコーパスであるReuters-21578，20newsgroupsと，スパムメールのコーパスであるTREC 
2006 Spam 
Corpusのテキスト分類の結果の比較を行った．反復度によって特徴選択した特徴集合を用いると条件付確率による特徴集合を用いた場合に比べて，ニュース記事の分類では平均79.65{\%}から平均83.39{\%}と，平均3.74{\%}だけテキスト分類の結果を改善することを報告し，スパムメールの分類では分類結果を平均90.23{\%}から平均93.15{\%}と平均2.93{\%}だけ結果を改善することを報告した．このとき，その両方の実験において，提案する反復度を用いる手法と条件付確率を用いるZhangら手法の間に有意差があることを確認した．

また，本実験では提案手法である反復度を用いて特徴集合を選択する方法と単語を特徴集合とする方法との比較についてもZhangらの手法との比較と同様にして行った．Reuters-21578，20newsgroupsを用いたニュース記事の分類においては両手法の間に有意差は確認できなかった．しかし，TREC 
2006 Spam 
Corpusを用いたスパムメールの分類においては，反復度による特徴抽出法を用いると，単語を特徴集合とする場合に比べて分類結果を，平均92.11{\%}から平均93.15{\%}と平均1.04{\%}だけ改善するということを報告した．そして，このとき危険率1{\%}の検定を行い両手法の間に有意差があるということを確認した．この結果の一つの要因として，反復度を用いて抽出される部分文字列に，条件付き確率を用いる手法で抽出される部分文字列に比べて別の部分文字列と解釈されにくい部分文字列や，単語による方法では抽出できない単語と単語を結ぶような文字列が含まれていると言うことが考えられる．よって，本研究は意味ある結果となったといえる．


\acknowledgment

この研究は，住友電工情報システムとの共同研究の成果です．データの解析には，戦略的情報通信開発推進制度(SCOPE)の課題「実空間情報処理のためのインターユビキタスネットワークの研究」の成果の分析技術を利用しました．

また，多くの有益なご指摘を頂いた査読者の方々に感謝致します．


\bibliographystyle{jnlpbbl_1.4}
\begin{thebibliography}{}


\item
Manning, C. and Schutze H. (1999). ``Foundations of Statistical Natural 
Language Processing.'' MIT Press, Cambridge.

\item
Zhang, D. and Lee, W. S. (2006). ``Extracting Key-Substing-Group Features for 
Text Classification.'' In \textit{Proceedings of the 12th ACM SIGKDD international 
Conference on Knowledge Discovery and Data Mining}, pp.~474--483.

\item
Peng, F., Shuurmans D., and Wang, S. (2004). ``Augmenting Naive Bayes text 
classifier with statistical language models.'' \textit{Information Retrieval}, 
\textbf{7} (3-4), pp.~317--345.

\item
Lodhi, H., Saunders, C., Shawe-Taylor, J., Cristianini, N., and Watkins, C. 
(2001). ``Text Classification Using String Kernels.'' \textit{Journal of Machine 
Learning Research (JMLR)}, pp.~419--444.

\item
Goodman, J. (2001). ``A bit progress in language modeling, extended version.'' 
Technical report, Microsoft Research, pp.~403--434.

\item
Church, K. W. (2000). ``Empirical Estimates of Adaptation: The chance of Two 
Noriegas is closer to p/2 than p2.'' In \textit{Proceedings of 18th International 
Conference on Computational Linguistics}, \textbf{1}, pp.~180--186.

\item
Cristianini, N. and Shawe-Taylor, J. (2000). ``An Introduction to Support Vector 
Machines.'' Cambridge University Press, Camridge.

\item
Dumais, S., Platt, J., Hecherman, D., and Sahami, M. (1998). ``Inductive learning 
algorithms and representations for text categorization.'' In \textit{Proceedings of 
the 7th ACM International Conference on Information and Knowledge 
Management}, pp.~148--155.

\item
Mitchell, T. (1997). ``Machine Learning.'' McGraw Hill, international edition.

\item
Geng, Xiubo, Liu, Tie-Yan, Qin, Tao, and Li, Hang (2007). ``Feature Selection for 
Ranking.'' \textit{SIGIR '07: Proceedings of the 30th annual international ACM SIGIR 
conference on Research and development in information retrieval}, pp.~407--414.

\item
Takeda, Y. and Umemura K. (2002). ``Selecting indexing strings using 
adaptation.'' \textit{Proceedings of the 25th Annual International ACM SIGIR 
Conference on Research and Development in Information Retrieval}, pp.~11--15.

\item
Yiming, Yang and Pedersen, Jan O. (1997). ``A comparative study on feature 
selection in text categorization.'' \textit{Proceedings of ICML-97 14th 
International Conference on Machine Learning}, pp.~412--420.

\item
平田勝大, 岡部正幸, 梅村恭司 (2007). 文字列を特徴量とし反復度を用いたテキスト分類. 
情報処理学会研究会報告, \textbf{76}, pp.~121--126.

\end{thebibliography}


\clearpage

\appendix

表 4には文書セットごとの各手法の平均F値を示した．表 12には文書セットごとの各手法のSpam，HamそれぞれのF値を示す．

\begin{table}[h]
\caption{表 12 各手法のSpam，HamそれぞれのF値}
\input{05table12.txt}
\end{table}


\begin{biography}
\bioauthor{尾上　　徹}{
2009年豊橋技術科学大学工学部情報工学課程卒業．
同年，同大学院入学，現在に至る．
}
\bioauthor{平田　勝大}{
2009年豊橋技術科学大学大学院工学部情報工学専攻修士課程修了．
同年，NTTデータ（株）入社．
}
\bioauthor{岡部　正幸}{
2001年 
東京工業大学大学院総合理工学研究科知能システム科学専攻博士課程修了．博士（工学）．同年 
科学技術振興機構(CREST)研究員，
2003年 豊橋技術科学大学情報メディア基盤センター助教．
知的情報検索の研究に従事．人工知能学会会員．
}
\bioauthor{梅村　恭司}{
1983年東京大学大学院工学系研究系情報工学専攻修士課程修了．
博士（工学）．同年，日本電信電話公社電気通信研究所入所．
1995年豊橋技術科学大学工学部情報工学系助教授，2003年教授．
自然言語処理，システムプログラム，記号処理の研究に従事．
ACM，ソフトウェア科学会，電子情報通信学会，計量国語学会各会員．
}

\end{biography}









\biodate


\end{document}

