    \documentclass[english]{jnlp_1.2c}
\usepackage[dvips]{graphicx}
\usepackage{amsmath}

\Volume{14}
\Number{1}
\Month{Jan.}
\Year{2007}
\received{2006}{6}{14}
\revised{2006}{8}{31}
\accepted{2006}{9}{24}

\setcounter{page}{163}

\etitle{Automatic F-term Classification of Japanese Patent 
	Documents Using the k-Nearest Neighborhood \\Method and the SMART Weighting}
\eauthor{Masaki Murata\affiref{NICT}  \and
	Toshiyuki Kanamaru\affiref{NICT} \and
	Tamotsu Shirado\affiref{NICT} \and
	Hitoshi Isahara\affiref{NICT}} 
\eabstract{
Patent processing is important in 
various fields such as industry, business, and law. 
We used F-terms \cite{Schellner2002_2} to classify 
patent documents using the k-nearest neighborhood method. 
Because the F-term categories are fine-grained, 
they are useful when we classify patent documents. 
We clarified the following three points
using experiments:
i) which variations of 
the k-nearest neighborhood method are the best for patent classification,
ii) which methods of calculating 
similarity are the best for patent classification, and
iii) from which regions of a patent 
terms should be extracted. 
In our experiments, we used the patent data 
used in the F-term categorization task
in the NTCIR-5 Patent Workshop \cite{Ntcir5_patent_web_2,Ntcir5_patent_2}.
We found that 
the method of adding the scores of 
k extracted documents to classify patent documents was the most effective 
among the variations of the k-nearest neighborhood method used in this study. 
We also found that 
SMART \cite{Singhal96_2,smart97_2}, which is known 
to be effective in information retrieval, 
was the most effective 
method of calculating similarity.    
Finally, when extracting terms, 
we found that 
using the abstract and claim regions together
was the best method among 
all the combinations of using
abstract, claim, and description regions.
The results were confirmed using a statistical test.
Moreover, we experimented with changing 
the amount of training data 
and found that 
we obtained better performance 
when we used more data, 
which was limited to that 
provided in the NTCIR-5 Patent Workshop. 
}
\ekeywords{F-term, Patent Classification, k-Nearest Neighborhood Method, SMART}

\headauthor{Murata et al.}
\headtitle{Automatic F-term Classification of Japanese Patent Documents}

\affilabel{NICT}{}
	{National Institute of Information and Communications Technology, 
	Independent Administrative Institution, 
	3-5 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0289, Japan}


\begin{document}

\maketitle


\section{Introduction}
\label{sec:c}

Patent processing is important in 
various fields such as industry, business, and law.
We used F-terms \cite{Schellner2002_2} to classify 
patent documents using the k-nearest neighborhood method.
Because the F-term categories are fine-grained, 
they are useful when we classify patent documents. 
``F-term'' is an abbreviation of ``file forming term'' 
and is one kind of classification for patent documents \cite{Ntcir5_patent_2}.
It is used in the Japan Patent Office \cite{JPO_2_2}.
The F-term classification system has
over 2,500 themes covering all the technological
fields of patents. Patents under each theme can be
classified from several viewpoints, such as purpose,
function, effect, etc. The collection of possible
viewpoints varies from theme to theme. Each
viewpoint defines a set of its possible elements, and a
pair of a viewpoint and an element is called an F-term.
The F-term classification system is an effective
tool for narrowing down relevant patents in searching.
In this study, we used the patent data 
used in the F-term categorization task
in the NTCIR-5 Patent Workshop \cite{Ntcir5_patent_web_2,Ntcir5_patent_2}. 
In the task, we determined the F-terms categories of input Japanese patents 
when the theme category of the patent was given. 
One patent can have
multiple F-term categories. 
For example, the published Japanese patent 2002-007044
with the theme ``5K067'' has 
F-term categories BB04, EE02, FF23, and KK17.
Determining these F-term categories was the problem we handled in this study.

We used the k-nearest neighborhood method for
the F-term classification of patent documents because
the number of such documents is very large. 
Because of this large number, using sophisticated machine learning methods
such as support vector machine \cite{SVM} and the maximum entropy method \cite{ristad97} is difficult
because these methods are complicated and 
require much time and many machine resources (memory). 
In contrast, 
the k-nearest neighborhood method is comparatively 
easy to use on a large amount of data 
because it only has to extract 
a set of data similar to the input data. 
Moreover, Yang pointed out that 
support vector machine and the k-nearest neighborhood methods 
were the best machine learning methods for the classification 
of documents \cite{Yang-sigir99_2}. 
We thus used the k-nearest neighborhood method in this study.

We answered the following three questions using
experiments:
\begin{enumerate}
\item 
Which variations of 
the k-nearest neighborhood method are the best in patent classification?

We used four variations of 
the k-nearest neighborhood method. 
We experimented to compare 
the results of these methods 
and determine which methods were the most effective.

\item 
Which methods of calculating 
similarity are the best for patent classification?

In the k-nearest neighborhood method,
we must determine how to calculate 
the similarity between input data and 
each item in a training set. 
We tested many methods of 
calculating the similarity. 
We experimented to compare 
the results of these methods 
and determine which methods were the most effective.

\item 
From which regions of a patent 
should terms be extracted?

Using our method, 
we extract terms from each patent 
and calculate the similarity between input data and 
each item in a training data set.
We therefore experimented to 
determine from
which part of a patent 
terms should be extracted.
\end{enumerate}

The automatic classification of patent documents 
has been studied previously \cite{Larkey99_2,koster-multiclassification_2,Fall03_2}.
Larkey created a tool for 
assigning US patent codes based on the k-nearest neighborhood method, 
but the overall system precision was not reported \cite{Larkey99_2}. 
Korster et al. experimented using 
patent documents in the European Patent Office
and the Winnow method \cite{koster-multiclassification_2}. 
Fall et al. experimented 
with classifying documents using
the support vector machine, 
the k-nearest neighborhood method, 
the Winnow method, 
and the simple Bayes method. 
In contrast to these previous studies, 
our study focuses on the k-nearest neighborhood method. 
We study the variations of 
the k-nearest neighborhood method 
and the methods of calculating 
similarity used in the k-nearest neighborhood method 
in patent classification. 

Briefly, 
the following are the results of this study. 
From our experiments, 
we first found that 
the method of adding the scores of 
k extracted documents 
to classify patent documents is the most effective 
among the variations of the k-nearest neighborhood method. 
We also found that 
SMART \cite{Singhal96_2,smart97_2}, which is known 
to be effective in information retrieval, 
is the most effective 
method of calculating similarity.    
Finally, when extracting terms, 
we found that 
using the abstract and claim regions together
is the best method among 
all the combinations of using
abstract, claim, and description regions.
These results were confirmed using a statistical test.

This paper is constructed as follows:
In Section \ref{sec:background}, we describe
the background of this work. 
We first explain the structure of a Japanese patent and 
the F-term classification system in Section \ref{sec:patent-exp}
We next explain our motivation for
handling the F-term categorization in Section \ref{sec:motivation}. 
We also explain the task (problem setting) 
we handled in Section \ref{sec:problem}. 
In Section \ref{sec:variation}, we describe the 
variations of the k-nearest neighborhood method. 
A patent may fall into multiple categories, and
the original k-nearest neighborhood method is not suitable for such cases. 
Therefore, we used variations of the k-nearest neighborhood method. 
In Section \ref{sec:similarity}, we describe the 
methods of calculating similarity, 
which must be defined
when we use the k-nearest neighborhood method.
In Section \ref{sec:regions}, we describe the 
regions used to extract terms from a patent. 
The regions of patents used are 
important in determining the effectiveness
of extracting terms for patent classification. 
In Section \ref{sec:experiment}, we describe our
experiments with variations of 
the k-nearest neighborhood method and methods of calculating 
similarity, 
experiment on the regions used to extract terms, and 
experiments on the amount of training data. 
In Section \ref{sec:related}, we describe
related studies, and 
in Section \ref{sec:conclusion} we 
make concluding remarks. 

\begin{table}[b]
\caption{Japanese patent structure}
\label{tab:patent_ex}
    \begin{tabular}{|l|l|l|l|} \hline
Section & Tag & Components & Examples \\
\hline
Bibliography & SDO BIJ & Publication number & 2000-004182\\
	&	& Date of publication & 07.01.2000 \\
	&	& of application &  \\
	&	& Title of invention & Separation-type portable telephone set \\
	&	& Application number & 10-167909 \\
	&	& Date of filing & 16.06.1998\\
	&	& Applicant & Matsushita Electric Ind. Co. Ltd. \\
	&	& Inventor ... & Kanazawa Kunihiko \\
\hline
Abstract & SDO ABJ & Problem to be solved & To provide a separation-type portable \\
	&	&	& telephone set that eliminates the ...         \\
	&	& Solution & Voice data are transmitted and received       \\
	&	&	& through radio waves , infrared rays, etc.,       \\
\hline
Claims & SDO CLJ & Claim 1 ... & A discrete-type cellular phone \\
	&	&	& characterized by transmitting and ...          \\
\hline
Description & SDO DEJ & Field of the Invention & This invention relates to the discrete- \\
	&	&	& type cellular phone using the ... \\
	&	& Description of the Prior Art & Conventionally, cellular phones are \\
	&	&	& used by a method that connects a ... \\
	&	& Problem(s) to be Solved by & However, also in the cellular phone \\
	&	& the Invention & that has the configuration shown in ... \\
	&	& Means for Solving the        & The discrete-type cellular phone that \\
	&	& Problem & this invention gets  to ... \\
	&	& Embodiment of the Invention & (Gestalt 1 of operation) The discrete- \\
	&	&	& type cellular phone concerning the ... \\
	&	& Effect of the Invention ... & According to the discrete-type cellular \\
	&	&	& phone that this invention gets as ... \\
\hline
Explanation & SDO EDJ & Drawing 1 ... & The block diagram of the discrete-type \\
of Drawings &	&	& cellular phone concerning the ... \\
	&	& Description of Notations & 1 Microphone (Body Built-in) ... \\
\hline
Drawings & SDO DRJ & Figure 1 ... & \\
\hline
\end{tabular}
\end{table}

\section{Background}
\label{sec:background}


\subsection{Patent structure and F-terms}
\label{sec:patent-exp}

In this section, 
we explain the Japanese patent structure and the F-terms used in this study. 

Each Japanese patent document has a sequence of normative sections:
the bibliography, abstract, 
claims, description,
explanation of drawings, and drawings, as shown in Table \ref{tab:patent_ex}.
In the patent data given at the NTCIR-5 Patent Workshop \cite{Ntcir5_patent_web_2,Ntcir5_patent_2}, 
tags for these sections such as ``SDO ABJ'' were inserted. 
The bibliography of a patent includes
the publication number, date of publication, title, inventors, etc.
The abstract contains the abstract, and
the claim contains the claims. 
In the description, 
the field of the invention, 
embodiments of the invention, etc. are given.

\begin{table}[b]
\begin{center}
    \footnotesize
\caption{Example of F-term classification system}
\label{tab:t-term-ex}
    \begin{tabular}{|l|l|l|l|l|l|l|} 
\hline
5K067 & \multicolumn{6}{c|}{Mobile radio communication systems} \\
\hline
AA & AA00                & AA01                  & AA02                  & AA03                  & AA04                  & ... \\\cline{2-7}
   & Purpose             & Measures to          & Measures relating   & Measures to         & Prevention of     & ... \\
   & and Effects         & overcome radio        & to phasing or multi-  & prevent               & unwanted              &        \\
   &                     & or transmission       & pass                  & interference or       & transmission          &        \\
   &                     & problems              &                       & jamming               &                       &        \\\hline
BB & BB00                & BB01                  & BB02                  & BB03                  & BB04                  & ... \\\cline{2-7}
   & Applications        & Telephones           & Wireless telephones & Car phones        & Cellular  phones  & ... \\\hline
CC & CC00                & CC01                  & CC02                  &                       & CC04                  & ... \\\cline{2-7}
   & Transmission        & Multiplex            & Frequency           &                       & Time-division      & ... \\
   & Systems             & systems               & multiplexing          &                       & multiplexing          &        \\\hline
DD & DD00                & DD01                  & DD02                  & DD03                  & DD04                  & ... \\\cline{2-7}
   & Transmission        & Signal types         & Frequency signals   & Serial or          & Binary signals     & ... \\
   & Signals             &                       &                       & parallel tones        & (i.e., binary code)   &        \\\hline
EE & EE00                & EE01                  & EE02                  & EE03                  & EE04                  & ... \\\cline{2-7}
   & System              & Station              & Mobile stations     & Variants that      & Use as  multiple  & ... \\
   & Configuration       & configuration         &                       & have secondary        & stations              &        \\
   &                     &                       &                       & stations              &                       &        \\\hline
... & ...                  & ...                    & ...                    & ...                    & ...                    & ... \\\hline
\end{tabular}
\end{center}
\end{table}


We next explain F-terms. 
The Japan Patent Office provides a multi-dimensional classification structure called an F-term classification system \cite{JPO_2_2,Schellner2002_2}.
An example is shown in Table \ref{tab:t-term-ex}.

In an F-term classification system, each technological field is defined as a theme corresponding to a set of ``FI'' codes (an extension of IPC).
For example, the theme denoted by ``5K067'' is the technological field of ``Mobile radio communication systems'', and this theme corresponds to the FI codes  ``H04B7/24-7/26,113@Z;H04Q7/00-7/04@Z''.
A theme is expressed by a sequence of a digit, a letter, and three digits.
There are over 2,500 themes.

Each theme has a collection of viewpoints for specifying the possible aspects of the inventions under the theme.
For example, 5K067 has ``Purpose and Effect'', ``Applications'', and ``Transmission Systems'' as viewpoints.
The collection of viewpoints varies from theme to theme.
A viewpoint is denoted by two letters.
For example, ``AA'' represents the viewpoint ``Purpose and Effect''.
Note that the naming of viewpoints is not uniform across themes, meaning that ``AA'' does not represent ``Purpose and Effect'' in other themes.

Each viewpoint has a list of possible elements.
For example, ``Purpose and Effect'' in this theme can be ``Measures to overcome radio or transmission problems'', and ``Applications'' in this theme can be ``Telephones''. 
The collection of elements varies from viewpoint to viewpoint.
An element is represented as two digits.
For example, ``Telephones'' for ``Applications'' corresponds to ``01''.
As an exception, ``00'' sometimes represents the elements not enumerated in the list of possible elements.
The ``00'' element is also used to designate the viewpoint as a whole, as shown in Table \ref{tab:t-term-ex}.


A pair of a viewpoint and an element is called an F-term.
For example, ``BB01'' is the F-term for mobile radio communication systems
whose applications are telephones.

All patents have various theme and F-term categories. 
To explain these, 
we use the published patent 2000-004182 described in Table \ref{tab:patent_ex}. 
The patent has three theme categories: 5K011, 5K027, and 5K067. 
Its F-term categories 
for these theme categories
are listed in Table \ref{tab:theme_fterm_ex}.
This patent has the F-terms AA34, AA42, BB04, and FF38 for the theme 5K067.
The fact that the patent has the F-term BB04 for the theme 5K067
means that 
the patent relates to 
mobile radio communication systems 
and its application is ``cellular phones'', as listed in Table \ref{tab:t-term-ex}. 
The patent
does not have F-terms for CC and DD viewpoints in the theme 5K067.
A patent does not generally always have F-terms for all viewpoints.


\begin{table}[t]
\caption{Theme and F-term categories for published patent 2000-004182}
\label{tab:theme_fterm_ex}
\begin{center}
\begin{tabular}{|l|l|l|} \hline
Published patent number & Theme & \multicolumn{1}{c|}{F-terms} \\\hline
2000-004182 & 5K011 & AA04, BA00, BA10, DA17, JA01, KA12\\
& 5K027 & AA13, CC08, DD11, DD14, EE03, HH03, HH16, HH20\\
& 5K067 & AA34, AA42, BB04, FF38 \\\hline
\end{tabular}
\end{center}
\end{table}


\subsection{Motivation}
\label{sec:motivation}

Because the F-term categories described in the previous section
are fine-grained,
they are useful when we classify patents. 
If we arrange the patent documents on radio transmission shown in Table \ref{tab:t-term-ex} 
into a two-dimensional table 
where the columns are
the F-terms of ``purpose'' and 
the rows are
the F-terms of ``application'', as shown in Table \ref{fig:use_fterm}, 
we can visualize 
purposes and applications of the patented inventions. 
The F-term categories are thus
useful for categorizing patents.
Another simple example that demonstrates the usefulness of F-terms 
is shown in Figure \ref{fig:lattice}.
In the example, each patent was given F-terms for problems and methods 
using automatic classification. 
The F-terms were used to make the table on the right side of the figure. 
The open circles in the table show that patents cover 
the corresponding problems and methods. 
The part in the gray oval is not covered by any patents, 
which indicates the possibility of filing promising new patents, 
that cover handling problems 4 to 7 using methods 3 to 5. 
The F-terms are useful for discovering such possibilities for patents. 
Thus, F-term categories can be very useful for categorizing patents. 
(The task organizer of the NTCIR-5 Patent Workshop \cite{Ntcir5_patent_2} 
illustrated the importance of F-term categorization in a similar way.)
Therefore, we studied F-term categorization. 

\begin{table}[t]
\begin{footnotesize}
\begin{center}
\caption{Example of visualizing purposes and applications of patented inventions
using F-terms}
\label{fig:use_fterm}
    \begin{tabular}{|l|l|l|l|l|l|l|} 
\hline
\multicolumn{1}{|l}{} & \multicolumn{1}{l|}{} & \multicolumn{5}{c|}{Purpose and Effects} \\\cline{3-7}
\multicolumn{1}{|l}{} & \multicolumn{1}{l|}{} & Measures to     & Time-related   & Improved             & Improved call         & Improved                      \\
\multicolumn{1}{|l}{} & \multicolumn{1}{l|}{} & prevent noise   & measures               & communication        & rates                         & reliability           \\
\multicolumn{1}{|l}{} & \multicolumn{1}{l|}{} &                                 &                                & quality                      &                                       &                                       \\\hline
\multicolumn{1}{|l|}{}                  & Cellular        & 2002-521863,        & 2000-295163,   & 2003-502959,         & 2000-358279,          & 2000-358279,          \\
\multicolumn{1}{|l|}{}                  & phones          & 2000-295163, ...      & 2000-341202, ... & 2003-502934, ...      & 2000-358268, ...        & 2000-358277, ...        \\\cline{2-7}
\multicolumn{1}{|l|}{}                  & Telephones  &                                 & 2000-308115    & 2000-341203,         &                                       & 2000-165318           \\
\multicolumn{1}{|l|}{Appli-}    & on trains   &                                 &                                & 2000-236204, ...       &                                       &                                       \\\cline{2-7}
\multicolumn{1}{|l|}{}                  & Cordless        & 2000-101499         & 2000-324236,   & 2000-324232,         & 2000-354108,          & 2000-102055,          \\
\multicolumn{1}{|l|}{}                  & telephones  &                                 & 2000-217145, ... & 2002-541717, ...       & 2000-308131, ...        & 2000-101693, ...        \\\cline{2-7}
\multicolumn{1}{|l|}{cations}   & Display         &                             &                                & 2000-307665,         & 2000-152303,          & 2000-165925,          \\
\multicolumn{1}{|l|}{}                  & pagers          &                             &                                & 2000-102049, ...       & 2000-049930, ...        & 2000-115844, ...        \\\cline{2-7}
\multicolumn{1}{|l|}{}                  & Telecontrol &                                 &                                &                              &                                       & 2000-258566,          \\
\multicolumn{1}{|l|}{}                  &                         &                             &                                &                              &                                       & 2000-233750, ...        \\\hline
\end{tabular}
\end{center}
\end{footnotesize}
\end{table}

    \begin{figure}[t]
  \begin{center}
            \includegraphics[height=6cm,width=13.5cm]{ntcir_paper.eps} 
    \caption{Another example of using F-terms}
    \label{fig:lattice}
  \end{center}
    \end{figure}

This study is useful 
for the following reasons:
\begin{itemize}
\item 
Our method can 
help annotators 
determine the F-term categories 
of each patent document.

\item 
Our method can 
be used for patent documents 
that have not been submitted to the patent office 
and do not have 
F-term categories or 
for other kinds of documents
that do not have 
F-term categories.
Our method can assign such documents 
to F-term categories.

\end{itemize}


\subsection{Problem setting}
\label{sec:problem}

In this section, 
we describe the problem we handled.

We participated in the F-term categorization task of the NTCIR-5 Patent Workshop \cite{Ntcir5_patent_web_2,Ntcir5_patent_2} 
because F-term categories are fine-grained and useful for classifying patents
and because we wanted to study F-term classification.

In the task, we determined the F-term categories of input Japanese patents 
when a theme category of the patent was given. 
A patent can have multiple F-term categories. 
For example, 
the published Japanese patent 2002-007044
with the theme 5K067
has F-terms BB04, EE02, FF23, and KK17\footnote{The published Japanese patent 2002-007044 
does not have F-terms for AA or CC viewpoints in the theme 5K067.
A patent does not generally always have F-terms for all viewpoints.}.
Determining the F-term categories was the problem we handled in this study.

The task involved a dry run and a formal run. 
We constructed our system using a data set in a dry run 
and tested it  using a data set in a formal run. 
In the dry run, 
we were given 1,201 patent documents to classify 
and 586,197 patent documents for training. 
In the formal run, we were given 2,562 documents to classify 
and 1,508,043 documents for training. 

In the dry run, one theme was used. 
In the formal run, five themes were used. 
These themes are shown in Table \ref{tab:theme-ex}. 
This table shows 
the theme names, the numbers of viewpoints and F-terms of the themes, 
and examples of the viewpoints 
used in the dry and formal runs. 

\begin{table}[t]
\caption{Themes used in task}
\label{tab:theme-ex}
\begin{footnotesize}
\begin{center}
    \begin{tabular}{|l|l|l|l|l|l|} \hline
                                                                & Theme & Theme name                                     & Number of  & Number of & Examples of viewpoints      \\
                                                                & code  &                                                                & viewpoints & F-terms   &                                             \\\hline
                                                Dry     & 5K067 & Mobile radio                                   & 11 & 305 & Purpose and Effects,                              \\
                                                run     &               & communication systems                  &    &         & Applications, Transmission            \\
                                                                &               &                                                                &    &         & Systems                                            \\\hline
\multicolumn{1}{|l|}{}                  & 2B022 & Cultivation of vegetables      & 9  & 95      & Target Vegetables, Main                       \\
\multicolumn{1}{|l|}{}                  &               &                                                        &    &         & Components of Culturing Media,        \\
\multicolumn{1}{|l|}{}                  &               &                                                        &    &         & Environmental Control                       \\\cline{2-6}
\multicolumn{1}{|l|}{}                  & 3G301 & Electrical control of the air  & 21 & 369 & Engine Models, General Purpose,   \\
\multicolumn{1}{|l|}{}                  &               & and fuel supply to internal    &    &         & Engine Timing Control, Main           \\
\multicolumn{1}{|l|}{}                  &               & combustion engines                     &    &         & Control Means for Fuel                      \\\cline{2-6}
\multicolumn{1}{|l|}{Formal}    & 4B064 & Manufacture of chemical                & 23 & 541 & Products Containing Oxygen,               \\
\multicolumn{1}{|l|}{}                  &               & compounds by using                     &    &         & Peptides and Proteins as the          \\
\multicolumn{1}{|l|}{run}               &               & microorganisms                                 &    &         & Product, ph as a Property           \\\cline{2-6}
\multicolumn{1}{|l|}{}                  & 5H180 & Traffic-control systems                & 11 & 215 & Structures of Systems and                 \\
\multicolumn{1}{|l|}{}                  &               &                                                                &    &         & Devices, Means of Detection,          \\
\multicolumn{1}{|l|}{}                  &               &                                                                &    &         & Parking Facilities                          \\\cline{2-6}
\multicolumn{1}{|l|}{}                  & 5J104 & Ciphering device, decoding     & 14 & 271 & Form of Telecommunication,                \\
\multicolumn{1}{|l|}{}                  &               & device and privacy                     &    &         & Generation of Random Number           \\
\multicolumn{1}{|l|}{}                  &               & communication                                  &    &         & Series, Purpose and Effect          \\\hline
\end{tabular}
\end{center}
\end{footnotesize}
\end{table}

\begin{table}[t]
\caption{Statistics of F-terms in task}
\label{tab:stat-ft-ex}
\begin{center}
\begin{tabular}{|l|l|l|r|r|r|} \hline
\multicolumn{1}{|r|}{} & \multicolumn{1}{r|}{Theme} & \multicolumn{1}{r|}{} & \multicolumn{1}{l|}{Number of} & \multicolumn{1}{l|}{Number of} & \multicolumn{1}{l|}{Average number of} \\
\multicolumn{1}{|r|}{} & \multicolumn{1}{r|}{} & \multicolumn{1}{r|}{} & \multicolumn{1}{l|}{documents} & \multicolumn{1}{l|}{F-terms} & \multicolumn{1}{l|}{F-terms per doc.} \\\hline
Dry run & 5K067 & training & 8413 & 304 & 10.08 \\
 &  & test & 1201 & 173 & 9.13 \\\hline
 & 2B022 & training & 1916 & 82 & 2.76 \\
 &  & test & 475 & 73 & 4.79 \\\cline{2-6}
 & 3G301 & training & 6699 & 369 & 19.97 \\
 &  & test & 542 & 353 & 21.13 \\\cline{2-6}
Formal run & 4B064 & training & 6405 & 486 & 8.58 \\
 &  & test & 493 & 323 & 8.49 \\\cline{2-6}
 & 5H180 & training & 6222 & 214 & 7.90 \\
 &  & test & 508 & 174 & 9.21 \\\cline{2-6}
 & 5J104 & training & 1920 & 268 & 10.03 \\
 &  & test & 544 & 251 & 12.07 \\\hline
\end{tabular}
\end{center}
\end{table}

We used 
documents with the given theme categories for training. 
In the dry run, 
we were given about 8,400 patent documents with the given theme categories.
In the formal run, we were given about 1,900 to 6,700 patent documents 
with each of the given theme categories.
The details are shown in Table \ref{tab:stat-ft-ex}:
the numbers of documents
and F-terms
and the average numbers of F-terms per document 
in the training and 
test data. 
A total of 337,027 F-terms were possible across all the themes;
the number of F-terms within each theme was relatively small.
Between 70 and 500 F-terms  were possible for each of the six themes.
In the data used, 
each patent had an average of 1.7 theme categories
and 15 F-term categories.  

In our evaluation, the
mean F-measure was used. 
The F-measure is defined as the harmonic mean 
of precision and recall 
(2 times the sum of the inverse of precision 
and the inverse of recall).
The recall is the ratio of the correct outputs
to all the correct categories.
The precision is the ratio of the correct outputs
to all the outputs.
These can be expressed as the following equations.
\begin{equation}
\mbox{F-measure} = \frac{2}{\frac{1}{\mbox{Recall}} + \frac{1}{\mbox{Precision}}}
\end{equation}
\begin{equation}
\mbox{Recall} = \frac{\mbox{The number of correct outputs}}{\mbox{The number of all the correct categories}}
\end{equation}
\begin{equation}
\mbox{Precision} = \frac{\mbox{The number of correct outputs}}{\mbox{The number of all the outputs}}
\end{equation}


\section{Variations of the k-nearest neighborhood method}
\label{sec:variation}

We used the following four variations of the k-nearest neighborhood method. 
In general, 
the k-nearest neighborhood method is used 
when each item has only one correct category. 
However, in this study, 
multiple categories can be correct, so
the original k-nearest neighborhood method is not suitable.
Therefore, we used the following 
variations of the method.
\begin{enumerate}
\item 
Method 1

The system first selects the
$k$ patent documents with the highest similarities 
to an input patent document 
from all the patent documents with a given input theme in the training data set.
We refer to the $k$ selected documents as $KDOC$. 
We used the ruby-ir toolkit \cite{ruby-ir-eng2_2,NLP2003_eng_2} to select documents.
We experimentally determined the constant $k$. 

The system next calculates the score ($Score_{M1}(x)$) of an F-term $x$ 
using the following equation by sorting $KDOC$ by
their similarity to the input patent document:
\begin{equation}
Score_{M1}(x) = \sum_{i=1}^{k} ((k_r)^i \times score_{doc}(i) \times role(x,i)),
\end{equation}
where
\begin{align*}
role(x,i) & = 1 \ \mbox{(if the $i$-th document has a F-term $x$)} \nonumber\\
          & = 0 \ \mbox{(otherwise)}. \nonumber
\end{align*}
Here, 
$score_{doc}(i)$ is the value of the similarity 
of the selected document that has the $i$th highest value of the similarity 
between the input patent document and the selected document, 
and $k_r$ is a constant 
determined using experiments.

The system finally selects the 
F-term categories, $x$, satisfying 
\begin{equation}
\{x| Score_{M1}(x) \geq k_p \times max_y Score_{M1}(y)\},
\end{equation}
where $k_p$ is a constant 
determined using experiments.
The selected F-term categories are 
output as the desired categories.

\item 
Method 2

The system first selects $KDOC$ the same way as in Method 1.

The system next calculates the number of occurrences
of an F-term, $x$, in $KDOC$. 
We refer to the number as $F_{KDOC}(x)$. 
The system finally selects the 
F-term categories, $x$, satisfying
\begin{equation}
\{x| F_{KDOC}(x) \geq k_u \times k\},
\end{equation}
where, $k_u$ is a constant determined by experiments.

When $k_u=0.5$, this method is exactly 
the same as the original k-nearest neighborhood method.

\item 
Method 3

The system first selects $KDOC$ the same way as in Method 1.

The system next calculates $F_{KDOC}(x)$. 
The system finally selects 
the $k_f$ F-term categories that 
have the highest values of $F_{KDOC}(x)$. 
We experimentally determined the constant $k_f$.

\item 
Method 4

The system first selects $KDOC$ the same way as in Method 1.

The system next calculates $F_{KDOC}(x)$. 
The system finally selects 
the $k_a$ F-term categories that 
have the highest values of $F_{KDOC}(x)$, where 
$k_a$ is the average number of F-term categories 
each document has in the $k$ selected documents. 

\end{enumerate}

Methods 2 through 4 
were based on and expanded upon Lewis's k-per-doc and probability thresholding strategies \cite{Lewis92_2}.

To test the effectiveness of each method, 
we also used the following baseline methods in our experiments.
\begin{enumerate}
\item 
  Baseline 1

  The system first selects 
  all the F-term categories 
  from all the patent documents with a given theme in the training data set.
  The system randomly selects $k_b$ F-term categories among them as the desired output, where 
  $k_b$ is the average number of F-term categories 
  of the documents with the given theme.

\item 
  Baseline 2

  The system first selects 
  all the F-term categories 
  from all the patent documents with a given theme in the training data set
  and sorts them 
  in the order of their frequency in the documents. 
  The system selects the $k_b$ most frequent F-term categories among them as the desired output, where 
  $k_b$ is the average number of F-term categories 
  of the documents with the given theme.

\item 
  Original k-nearest neighborhood method \cite{Fukunaga,Okamoto97B_2,Yang-sigir99_2,Pattern_class,Guo2004_2}

  The original k-nearest neighborhood method is used 
  for each F-term category. 

  The system first selects $KDOC$ the same way as in Method 1.
 
  For each F-term category, 
  the system counts the number ($NUM_+$) of documents that have the category
  and the number ($NUM_-$) of documents that do not have the category
  among $KDOC$. 
  The system then selects the F-term categories 
  in which $NUM_+$ 
  is larger than or the same as $NUM_-$
  as the desired categories. 
        
  This method can alternatively be explained as follows.

  The system first selects $KDOC$ the same way as in Method 1.
  
The system next calculates $F_{KDOC}(x)$. 
The system finally selects the 
F-term categories, $x$, satisfying the following equation as the desired categories. 
\begin{equation}
\{x| F_{KDOC}(x) \geq 0.5 \times k\}
\end{equation}

\end{enumerate}


\section{Method of calculating similarity}
\label{sec:similarity}

We used the following four methods 
of calculating the similarity between an input patent document and 
each patent document in a training data set.
\begin{enumerate}
\item 
SMART

The system first extracts terms\footnote{We used only nouns as terms. We used ChaSen\cite{chasen} for identify nouns.} for each input patent document. 
The system next selects documents containing at least 
one of the terms from all the patent documents with a given input theme in the training data set. 
It uses the following equation to calculate $Sim_{SMART}$
for each selected document. 
We used $Sim_{SMART}$ as 
the similarity between an input patent document and 
each patent document in the training data.
\begin{equation}
Sim_{SMART} = \sum_{t \in T} (W_d \times W_q),
\end{equation}
\begin{equation}
W_d = \frac{1+log(tf)}{1+log(avtf)} \times \frac{1}{0.8 + 0.2 \frac{utf}{pivot}},
\end{equation}
\begin{equation}
W_q = (1 + log(qtf)) \times log \frac{N + 1}{n}
\end{equation}
In these equations, 
$T$ is the set of terms appearing in
both the input document and the selected document,
$tf$ is the number of occurrences of a term $t$ 
in the selected document,
$avtf$ is the average number of occurrences of each term in the set in the selected document,
$qtf$ is the number of occurrences of a term $t$ 
in the query document,
$utf$ is the number of unique terms in the selected document,
$pivot$ is the average number of unique terms per document in the training documents, 
$N$ is the total number of patent documents with a given input theme in the training data set,
and $n$ is the number of documents in which a term $t$ appears. 

SMART is a term weighting method in information retrieval \cite{Singhal96_2,smart97_2,Iwayama_2004}.

\item 
BM25

The system first extracts terms for each input patent document. 
The system next selects documents containing at least 
one of the terms. 
It uses the following equation to calculate $Sim_{BM25}$
for each selected document. 
We used $Sim_{BM25}$ as 
the similarity between an input patent document and 
each patent document in the training data.
\begin{equation}
Sim_{BM25} = \sum_{t \in T} (W_d \times W_q),
\end{equation}
\begin{equation}
W_d = \frac{(k_1 + 1) tf}{k_1 ((1-b) + b \frac{dl}{avdl}) + tf},
\end{equation}
\begin{equation}
W_q = \frac{(k_3 + 1)qtf}{k_3 + qtf} log \frac{N}{n}
\end{equation}
In these equations, 
$T$, $tf$, $qtf$, $N$, and $n$ are 
the same as in SMART,
$dl$ is the length of the selected document,
$avdl$ is the average length of the documents, and
$k_1$, $k_3$, and $b$ are constants determined using experiments.
We used the default values described in the ruby-ir toolkit as $k_1$, $k_3$, and $b$
($k_1 = 1$, $k_3 = 1000$, and $b = 1$).
We used $log \frac{N}{n}$ instead of 
$log \frac{N - n + 0.5}{n + 0.5}$ in the original equations of BM25 
because $Sim_{BM25}$ sometimes produced negative scores. 
We confirmed that we obtained higher F-measures 
when we made this revision in the experiments. 

BM25 is a term weighting method in information retrieval \cite{robertson_trec3_2,murata_irex_ir_nlp_eng_2,Iwayama_2004}. 

\item 
Tfidf

The system first extracts terms for each input patent document. 
It next selects documents containing at least 
one of the terms.
The system uses the following equation to calculate $Sim_{Tfidf}$
for each selected document. 
We used $Sim_{Tfidf}$ as 
the similarity between an input patent document and 
each patent document in the training data set.
\begin{equation}
Sim_{Tfidf} = \sum_{t \in T} tf \times log \frac{N}{n},
\end{equation}
In this equation, 
$T$, $tf$, $N$, and $n$ are the same as in SMART. 

\item 
Overlap

The system first selects terms for each input patent document. 
It next selects documents containing at least 
one of the terms.
The system uses the following equation to calculate $Sim_{Overlap}$
for each selected document. 
We used $Sim_{Overlap}$ as 
the similarity between an input patent document and 
each patent document in the training data set.
\begin{equation}
Sim_{Overlap} = \sum_{t \in T} 1,
\end{equation}
In this equation, 
$T$ is the same as in SMART. 
\end{enumerate}


\section{Regions used to extract terms}
\label{sec:regions}

We first extracted terms from the abstracts, claims, and descriptions
of patent documents. 

We next made combinations of the three regions as follows:
\begin{enumerate}
\item 
Abstract, claim, and description

\item 
Abstract and claim

\item 
Abstract and description

\item 
Claim and description

\item 
Abstract

\item 
Claim

\item 
Description

\end{enumerate}

The abstract, claim, and description 
are as described in Section \ref{sec:patent-exp}. 
In the experiments, we eliminated the bibliographies, explanations of drawings, and drawings.


\section{Experiment}
\label{sec:experiment}

\subsection{Experiments on variations of 
the k-nearest neighborhood method and methods of calculating 
similarity}

We first experimented with variations of 
the k-nearest neighborhood method and methods of calculating 
similarity using the dry run data. 
We extracted terms from 
the abstract and claim regions.

\begin{table}[t]
\caption{Experimental results}
\label{tab:result}
\begin{center}
\begin{tabular}{|l|l|l|l|} \hline
Similarity method    & Parameters             & \multicolumn{2}{|c|}{F-measure} \\\hline   
    &                             &  Dry run    & Formal run\\\hline 
\multicolumn{4}{|l|}{Baseline 1} \\\hline
---           & ---                         & 0.0324$^{--}$     & 0.0396$^{--}$\\\hline
\multicolumn{4}{|l|}{Baseline 2} \\\hline                       
---           & ---                         & 0.3991$^{--}$     & 0.2962$^{--}$\\\hline
\multicolumn{4}{|l|}{Original k-nearest neighborhood method} \\\hline               
SMART         & $k=31$                      & 0.4186$^{--}$     & 0.2941$^{--}$\\
BM25          & $k=21$                      & 0.4131$^{--}$     & 0.3009$^{--}$\\
Overlap       & $k=21$                      & 0.3823$^{--}$     & 0.2689$^{--}$\\
Tfidf         & $k=101$                     & 0.3196$^{--}$     & 0.1998$^{--}$\\
\hline
\multicolumn{4}{|l|}{Method 1} \\\hline                         
SMART         & $k=101,k_r=0.99,k_p=0.3$    & 0.5350$^{*}$      & 0.4525$^{*}$\\
BM25          & $k=101,k_r=0.99,k_p=0.3$    & 0.5237$^{--}$     & 0.4403$^{--}$\\
Overlap       & $k=101,k_r=0.99,k_p=0.3$    & 0.4764$^{--}$     & 0.4040$^{--}$\\
Tfidf         & $k=301,k_r=1,k_p=0.3$       & 0.4323$^{--}$     & 0.3766$^{--}$\\
\hline
\multicolumn{4}{|l|}{Method 2} \\\hline                         
SMART         & $k=51,k_u=0.3$              & 0.5232$^{--}$     & 0.4048$^{--}$\\
BM25          & $k=101,k_u=0.2$             & 0.5161$^{--}$     & 0.3979$^{--}$\\
Overlap       & $k=51,k_u=0.3$              & 0.4721$^{--}$     & 0.3610$^{--}$\\
Tfidf         & $k=101,k_u=0.2$             & 0.4271$^{--}$     & 0.3621$^{--}$\\
\hline
\multicolumn{4}{|l|}{Method 3} \\\hline                         
SMART         & $k=51,k_f=8$                & 0.5148$^{--}$     & 0.4067$^{--}$\\
BM25          & $k=101,k_f=8$               & 0.5054$^{--}$     & 0.3941$^{--}$\\
Overlap       & $k=101,k_f=9$               & 0.4640$^{--}$     & 0.3644$^{--}$\\
Tfidf         & $k=501,k_f=10$              & 0.4319$^{--}$     & 0.3431$^{--}$\\
\hline
\multicolumn{4}{|l|}{Method 4} \\\hline                         
SMART         & $k=101$                     & 0.5254$^{--}$     & 0.4346$^{--}$\\
BM25          & $k=51$                      & 0.5132$^{--}$     & 0.4289$^{--}$\\
Overlap       & $k=101$                     & 0.4650$^{--}$     & 0.3937$^{--}$\\
Tfidf         & $k=301$                     & 0.4293$^{--}$     & 0.3634$^{--}$\\
\hline
\end{tabular}
\end{center}
\end{table}


The results are shown in Table \ref{tab:result}.
(The F-measure in the table is explained in Section \ref{sec:problem}.)

We tested the following values for each parameter 
and experimented with using 
all the combinations of these values 
to determine the best values for each parameter. 
\begin{enumerate}
\item 
Method 1

$k$: 3, 5, 7, 9, 11, 13, 15, 21, 31, 51, 101, 301, 501, 701, 1001, 1501, 2001\footnote{We used
odd numbers for $k$ because 
odd numbers have been shown to be appropriate in the k-nearest neighborhood method \cite{Okamoto97B_2}.}.
$k_r$: 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.95, 0.99, 1. 
$k_p$: 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9. 

\item 
Method 2

$k$: 3, 5, 7, 9, 11, 13, 15, 21, 31, 51, 101, 301, 501, 701, 1001, 1501, 2001. 
$k_u$: 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9. 

\item 
Method 3

$k$: 3, 5, 7, 9, 11, 13, 15, 21, 31, 51, 101, 301, 501, 701, 1001, 1501, 2001. 
$k_f$: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15. 

\item 
Method 4

$k$: 3, 5, 7, 9, 11, 13, 15, 21, 31, 51, 101, 301, 501, 701, 1001, 1501, 2001. 

\item 
Baselines 1 and 2

These methods do not use parameters.

\item 
  Original knn method

$k$: 3, 5, 7, 9, 11, 13, 15, 21, 31, 51, 101, 301, 501, 701, 1001, 1501, 2001. 

\end{enumerate}

\begin{figure}[t]
      \begin{center}
        \includegraphics[height=8cm,width=12cm]{k.eps} 
      \end{center}
    \caption{Tuning of $k$ for Method 1 ($k_r=1,k_p=0.3$)}
    \label{fig:k}
\end{figure}

The evaluation scores and the parameters' values 
that resulted in the highest scores for each method on the dry run data are shown in Table \ref{tab:result}.
Some examples of the results of experimentally determining the parameters 
for Method 1 and SMART 
are shown in Figures \ref{fig:k}, \ref{fig:kr}, and \ref{fig:kp}.

\begin{figure}[p]
      \begin{center}
        \includegraphics[height=8cm,width=12cm]{kr.eps} 
      \end{center}
    \caption{Tuning of $k_r$ for Method 1 ($k=101,k_p=0.3$)}
    \label{fig:kr}
    \vspace{\baselineskip}
      \begin{center}
        \includegraphics[height=8cm,width=12cm]{kp.eps} 
      \end{center}
    \caption{Tuning of $k_p$ for Method 1 ($k=101,k_r=1$)}
    \label{fig:kp}
\end{figure}

We also experimented with the formal run data by using 
the parameter values 
that resulted in the highest scores for each method
on the dry run data. 
The results are shown in Table \ref{tab:result}.

We used the dry run data to determine the parameters
and the formal run data to evaluate the effectiveness of the methods. 

We used the two-sided t-test to determine significant differences,
with the best methods (Method 1 and SMART) as the baseline methods, which were labeled ``*''.
When a method performed better than the baseline method at the 0.05 or 0.01 significance level,
it was labeled ``+'' or ``++''.
Likewise, when a method performed worse than the baseline method at the 0.05 or 0.01 significance level,
it was labeled ``$-$'' or ``$--$''.

Table \ref{tab:result} shows the following.
\begin{itemize}
\item 
Among the variations of the k-nearest neighborhood method, 
Method 1 had the best score. 
The difference between Method 1 and 
the other three methods was small. 
However, we confirmed that 
Method 1 was more effective than the other methods 
when SMART was used
by using the statistical test at a significance level of 0.01.

Methods 1 through 4 yielded higher scores than the original k-nearest neighborhood method. 
This indicates that 
the modifications in these methods were effective. 

Baselines 1 and 2 yielded low F-measures. 
This indicates that 
the problems handled in this paper 
were difficult. 
Therefore, 
the F-measure of the best Method 1 (0.4525) was not 
so high, but it was higher 
than the scores of Baselines 1 and 2. 

\item 
Among the methods of calculating 
similarity, 
SMART had the best score.
The difference between SMART and 
the other three methods was small.
However, we confirmed that 
SMART was more effective than the other methods 
when Method 1 was used
by using the statistical test at a significance 
level of 0.01.
\end{itemize}

\begin{figure}[t]
      \begin{center}
        \includegraphics[height=8cm,width=12cm]{rp.eps} 
      \end{center}
    \caption{Precision and recall curve of Method 1}
    \label{fig:rp}
\end{figure}

Figure \ref{fig:rp} shows the relationship between the recall and precision 
using Method 1 and SMART on the dry and formal run data
when we changed the value of the parameter $k_p$ 
\linebreak
($k_p = 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9$).  
Our method obtained 
various values of precision and recall 
by using the various values of $k_p$.
In short, 
our method can be adjusted 
to have high precision or high recall. 

\subsection{Experiment on regions used to extract terms}

We next experimented with the regions used to extract terms.
The results of using
Method 1 and SMART in the formal run data
are shown in Table \ref{tab:region}. 
The parameters, $k$, $k_r$, and $k_p$,
were determined using the dry run data in each region. 
We experimentally determined that 
BM25, Tfidf, and Overlap did not produce higher F-measures than SMART in each region 
and that Methods 2 to 4 did not produce higher F-measures than Method 1 in each region 
when we used SMART. 

We used the two-sided t-test to determine significant differences,
with the best method (the use of the abstract and claim) as the baseline method.
When a method performed better than the baseline method at the 0.05 or 0.01 significance level,
it was labeled ``+'' or ``++''.
Likewise, when a method performed worse than the baseline method at the 0.05 or 0.01 significance level,
it was labeled ``$-$'' or ``$--$''.

This table shows the following.
\begin{itemize}
\item 
Using the abstract, claim, and description regions together
yielded
lower scores than using the abstract and claim regions together.
This indicates that
we should not use 
description sections for classification.

\item 
The use of the abstract and claim together
yielded the best scores.  
The differences between 
the F-measure of the abstract and claim together
and those of the other regions
are not large. 
However, the differences 
were confirmed by using the statistical test
at a significance level of 0.01.
\end{itemize}

\begin{table}[t]
\caption{Experimental results of using regions}
\label{tab:region}
\begin{center}
\begin{tabular}{|l|l|l|} \hline
Regions used                  & F-measure\\\hline 
Abstract, claim and, description   & 0.4448$^{--}$\\
Abstract and claim             & 0.4525$^{*}$\\
Claim and description          & 0.4324$^{--}$\\
Abstract and description       & 0.4201$^{--}$\\
Abstract only                  & 0.4436$^{--}$\\
Claim only                     & 0.4470$^{--}$\\
Description only               & 0.4247$^{--}$\\\hline
\end{tabular}
\end{center}
\end{table}

\subsection{Experiments on the amount of training data}

We experimented with changing the amount of training data
using the formal run data.
We used the following fractions of the data.
\begin{enumerate}
\item 
 1 (all the training data)

\item 
 1/2

\item 
 1/4

\item 
 1/8 
\item 
 1/16 
\end{enumerate}
We used Method 1 and SMART in the experiments. 
We extracted the terms from the abstract and claim.

The results are shown in Figure \ref{fig:amount}.
When we used part of the training data, 
we experimentally produced F-measures for each part 
and used the average of the F-measures of all the parts 
as the F-measure shown in the figure.
For example, when we use 1/4 of the training data, 
we divided the data into four parts
and produced an F-measure for each part. 
We calculated the average of the F-measures of all four parts 
to get the F-measure shown in Figure \ref{fig:amount}.

As shown in Figure \ref{fig:amount}, 
when we used more training data,
we obtained higher F-measures. 
\begin{figure}[t]
      \begin{center}
        \includegraphics[height=8cm,width=12cm]{am.eps} 
      \end{center}
    \caption{F-measures for different amounts of training data}
    \label{fig:amount}
\end{figure}


\subsection{Experiment for the NTCIR Patent Workshop}

In this section, we describe the results of our 
participation in the NTCIR Patent Workshop \cite{Ntcir5_patent_2}. 

The results of all the teams are shown in Table \ref{tab:NTCIR5}.
In the workshop, 
our team used Method 1 and BM25\footnote{Our five 
systems in the NTCIR Patent Workshop each used 
different parameters.}.  
We explored use of the SMART weighting schemes after the workshop.
Three teams participated in the workshop,
including our team \cite{Ntcir5_patent_2}.
Team 1 used a method in which
each category was represented as a word vector 
and each test document was compared with these word vectors.
Team 2 used the support vector machine. 
As shown in Table \ref{tab:NTCIR5},
our team obtained the best scores, and
the differences between our scores 
and the other teams' scores were large.
Our current system using SMART 
yielded a higher F-measure than the best in the workshop. 
This result indicates that 
our methods were effective.

In the workshop \cite{Ntcir5_patent_2}, 
another task was to classify the theme categories of patent documents, 
but we did not participate in it.
The averages of the F-measures of all the participants' systems 
in the formal run data 
are 0.3119 and 0.2380 in the theme and F-term tasks.
Because the F-term categories are 
more fine-grained than the theme categories, 
the F-term classification was more difficult than
the theme classification. 


\begin{table}[t]
\caption{Results of formal run of NTCIR-5 Patent Workshop}
\label{tab:NTCIR5}
\begin{center}
\begin{tabular}{|l|l|l|} \hline
System &  F-measure\\\hline
Our system 1            & 0.4379\\
Our system 2            & 0.4190\\
Our system 3            & 0.4168\\
Our system 4            & 0.4258\\
Our system 5            & 0.4393\\\hline
Team 1's system 1 & 0.1604\\
Team 1's system 2 & 0.1648\\
Team 1's system 3 & 0.1646\\
Team 1's system 4 & 0.1652\\
Team 1's system 5 & 0.1447\\
Team 1's system 6 & 0.1614\\
Team 1's system 7 & 0.1606\\
Team 1's system 8 & 0.1581\\
Team 1's system 9 & 0.1696\\
Team 1's system 10 & 0.1579\\\hline
Team 2's system 1 & 0.2830\\
Team 2's system 2 & 0.1435\\
Team 2's system 3 & 0.1110\\\hline
\end{tabular}
\end{center}
\end{table}

\section{Related studies}
\label{sec:related}

There have been several previous studies on automatically classifying patent documents \cite{Larkey99_2,koster-multiclassification_2,Fall03_2}.
Larkey created a tool for 
assigning US patent codes based on the k-nearest neighborhood method, 
but the overall system precision was not reported \cite{Larkey99_2}. 
Korster et al. experimented with using 
patent documents in the European Patent Office
and the Winnow method and obtained an F-measure of 0.68 
when classifying documents into 44 subclasses \cite{koster-multiclassification_2}.
Fall et al. experimented
with classifying documents into 451 subclasses 
and reported that 
the support vector machine, 
the k-nearest neighborhood method, 
the Winnow method, 
and the simple Bayes method yielded
accuracies of 0.50, 0.46, 0.45, and 0.43
when using the all-categories measure,
which compares
the top prediction of the classifier with all categories 
associated with the document, and
if a single match is found, the categorization is deemed successful \cite{Fall03_2}. 
When we used the same measure for our evaluation, 
our best result of using Method 1 and SMART
yielded 0.83 and 0.75 in the dry 
and formal run data.
However, the data set used in their experiments was different from 
ours, so we cannot compare our evaluation scores (accuracy or F-measure) 
with theirs. 

In our preliminary experiments using the dry run data, 
the support vector machine and
the maximum entropy method yielded
F-measures of 0.2582 and 0.2749.
In the experiments, 
we used the 3,000 most frequent words as features. 
These F-measures were much lower than 
those of our methods of using 
the k-nearest neighborhood method. 
The reason was that 
we could not use many words as features
in the support vector machine and
the maximum entropy method 
because these methods are complicated and 
require much time and many machine resources (memory). 
In addition, we must construct 
a classifier for each F-term when 
using these methods. 
This was a very hard job because 
a thousand classifiers must be made to
handle patent documents
with a theme having a thousand F-terms. 
In contrast, we have to 
make only one classifier
when we use the k-nearest neighborhood method. 
Therefore, using the k-nearest neighborhood method
was reasonable. 
We concentrated on the k-nearest neighborhood method 
and examined various aspects of it.

\section{Discussion}
\label{sec:discussion}

According to information from the Japan Patent Office, 
when an expert assigns F-terms to patent documents, 
he takes about one hour per document. 
The accuracy rate (the rate that 
the results by two experts match each other) 
is more than 0.9. 
The authors also tried assigning F-terms to patent documents
by consulting documents 
describing 
the definitions and explanations of F-terms. 
We were not experts. 
The F-measure of the results 
ranged from 0.2 to 0.7, i.e., very low. 
Experts are necessary for all domains. 
We found that 
assigning F-terms to patent documents is 
a laborious task 
requiring extensive human costs. 
Therefore, 
it is very important 
to achieve
automatic F-term classification 
such as that discussed in this paper 
or a support system for human beings 
to assign F-terms to patent documents. 

We should be able to construct the following support system 
for human beings to assign F-terms to patent documents 
using our system. 
\begin{itemize}
\item 
  The system displays F-terms and their values of precision
  that are calculated using system performance 
  for input patents. 
  The system displays F-terms 
  in the descending order of 
  the values of the precisions. 
\end{itemize}
The number of F-terms the system outputs 
can be changed by using a parameter, $k_p$. 
When a larger $k_p$ is used, 
the number of F-terms output is larger. 
Because 
we can calculate 
the precision for all values of $k_p$ 
by using patent documents used in the formal run, 
we can calculate the precision for
all output F-terms by using the results. 
The F-terms and their values of precision output
are useful, because 
human beings know
which F-term has what degree of reliability. 
A system outputting F-terms and their values of precision 
can be used as a support system 
for human beings assigning F-terms to patent documents. 

As our system did not perform as well as expected, 
we need to improve it through the following means.
\begin{itemize}
\item 
  It did not use
  the definitions or explanations
  of F-terms. 
  The definitions and explanations 
  include information
  about which F-terms mean which things. 
  When our system uses this information in addition, 
  its performance should be improved.
\end{itemize}
Human beings use
the definitions and explanations of F-terms 
to assign F-terms to patent documents. 
When we can use this information in our system, 
we can improve it.

\section{Conclusion}
\label{sec:conclusion}

Patent processing is important in 
various fields such as industry, business, and law.
We used F-terms to classify 
patent documents using the k-nearest neighborhood method.
Because the F-term categories are fine-grained, 
they are useful when we classify patent documents. 

We experimented with the following three points:
i) variations of 
the k-nearest neighborhood method, 
ii) methods of calculating 
similarity, and 
iii) regions used to extract terms. 
We found that 
Method 1, which adds the scores of 
k extracted documents to classify patent documents, was the most effective
among the variations. 
We also found that 
SMART, which is known 
to be effective in information retrieval, 
was the most effective method of calculating similarity.    
For regions to extract terms from, 
we found that 
using the abstract and claim regions together
was the best method among 
all the combinations of using
abstract, claim, and description regions.
These results were confirmed by statistical tests.

Moreover, we experimented with changing 
the amount of the training data 
and found that 
we obtained better performance 
when we used more data,
which was limited to that provided in the NTCIR-5 Patent Workshop. 

In the future, 
we would like to study 
constructing application systems 
to show users the results of classifying patent documents
by using the automatic F-term classification technique
used in this study. 


\acknowledgment

We are grateful to all of the organizers of patent task at NTCIR 5, 
who gave us a chance to participate in the patent task of the NTCIR 5 contest 
to study and examine patent document classification. 
We greatly appreciate the kindness of all those who helped us including a reviewer. 

\begin{thebibliography}{}

\bibitem[\protect\BCAY{Cristianini \BBA\ Shawe-Taylor}{Cristianini \BBA\
  Shawe-Taylor}{2000}]{SVM}
Cristianini, N.\BBACOMMA\ \BBA\ Shawe-Taylor, J. \BBOP 2000\BBCP.
\newblock {\Bem An Introduction to Support Vector Machines and Other
  Kernel-based Learning Methods}.
\newblock Cambridge University Press.

\bibitem[\protect\BCAY{Duda, Hart, \BBA\ Stork}{Duda
  et~al.}{2001}]{Pattern_class}
Duda, R.~O., Hart, P.~E., \BBA\ Stork, D.~G. \BBOP 2001\BBCP.
\newblock {\Bem Pattern Classification (Second Edition)}.
\newblock A Wiley-Interscience Publication.

\bibitem[\protect\BCAY{Fall, Toresvari, Benzineb, \BBA\ Karetka}{Fall
  et~al.}{2003}]{Fall03_2}
Fall, C.~J., Toresvari, A., Benzineb, K., \BBA\ Karetka, G. \BBOP 2003\BBCP.
\newblock \BBOQ Automated categorization in the international patent
  classification\BBCQ\
\newblock {\Bem SIGIR Forum}, {\Bbf 37}  (1), \mbox{\BPGS\ 10--25}.

\bibitem[\protect\BCAY{Fukunaga}{Fukunaga}{1972}]{Fukunaga}
Fukunaga, K. \BBOP 1972\BBCP.
\newblock {\Bem Introduction to Statistical Pattern Recognition}.
\newblock Academic Press Inc.

\bibitem[\protect\BCAY{Guo, Wang, Bell, Bi, \BBA\ Greer}{Guo
  et~al.}{2004}]{Guo2004_2}
Guo, G., Wang, H., Bell, D.~A., Bi, Y., \BBA\ Greer, K. \BBOP 2004\BBCP.
\newblock \BBOQ An kNN Model-Based Approach and Its Application in Text
  Categorization\BBCQ\
\newblock In {\Bem Computational Linguistics and Intelligent Text Processing,
  5th International Conference (CICLing 2004)}, \mbox{\BPGS\ 559--570}.

\bibitem[\protect\BCAY{Iwayama, Fujii, \BBA\ Kando}{Iwayama
  et~al.}{2005}]{Ntcir5_patent_2}
Iwayama, M., Fujii, A., \BBA\ Kando, N. \BBOP 2005\BBCP.
\newblock \BBOQ Overview of Classification Subtask at {NTCIR-5 Patent Retrieval
  Task}\BBCQ\
\newblock In {\Bem Proceedings of the Fifth NTCIR Workshop}.

\bibitem[\protect\BCAY{Iwayama, Fujii, Kando, \BBA\ Marukawa}{Iwayama
  et~al.}{2006}]{Iwayama_2004}
Iwayama, M., Fujii, A., Kando, N., \BBA\ Marukawa, Y. \BBOP 2006\BBCP.
\newblock \BBOQ Evaluating patent retrieval in the third NTCIR workshop\BBCQ\
\newblock {\Bem Information Processing and Management}, {\Bbf 42}, \mbox{\BPGS\
  207--221}.

\bibitem[\protect\BCAY{JPO}{JPO}{2005}]{JPO_2_2}
JPO \BBOP 2005\BBCP.
    \newblock \BBOQ Japan Patent Office\BBCQ\ 
\newblock http://www.jpo.go.jp/ index.html.

\bibitem[\protect\BCAY{Koster, Seutter, \BBA\ Beney}{Koster
  et~al.}{2003}]{koster-multiclassification_2}
Koster, C.~H., Seutter, M., \BBA\ Beney, J.~G. \BBOP 2003\BBCP.
\newblock \BBOQ Multi-Classification of Patent Applications with Winnow\BBCQ\
\newblock In {\Bem Proceedings PSI 2003, Springer LNCS 2890}, \mbox{\BPGS\
  19--26}.

\bibitem[\protect\BCAY{Larkey}{Larkey}{1999}]{Larkey99_2}
Larkey, L.~S. \BBOP 1999\BBCP.
\newblock \BBOQ A patent search and classification system\BBCQ\
\newblock In {\Bem Proceedings of the fourth ACM conference on Digital
  libraries (DL '99)}, \mbox{\BPGS\ 179--187}.

\bibitem[\protect\BCAY{Lewis}{Lewis}{1992}]{Lewis92_2}
Lewis, D.~D. \BBOP 1992\BBCP.
\newblock \BBOQ An evaluation of phrasal and clustered representations on a
  text categorization task\BBCQ\
\newblock In {\Bem Proceedings of the 15th annual international ACM SIGIR
  conference on Research and development in information retrieval (SIGIR '92)},
  \mbox{\BPGS\ 37--50}.

\bibitem[\protect\BCAY{Matsumoto, Kitauchi, Yamashita, Hirano, Matsuda, \BBA\
  Asahara}{Matsumoto et~al.}{1999}]{chasen}
Matsumoto, Y., Kitauchi, A., Yamashita, T., Hirano, Y., Matsuda, H., \BBA\
  Asahara, M. \BBOP 1999\BBCP.
\newblock \BBOQ Japanese Morphological Analysis System {ChaSen} version 2.0
  Manual 2nd edition\BBCQ.

\bibitem[\protect\BCAY{Murata, Ma, Uchimoto, Ozaku, Utiyama, \BBA\
  Isahara}{Murata et~al.}{2000}]{murata_irex_ir_nlp_eng_2}
Murata, M., Ma, Q., Uchimoto, K., Ozaku, H., Utiyama, M., \BBA\ Isahara, H.
  \BBOP 2000\BBCP.
\newblock \BBOQ Information Retrieval Using Location and Category
  Information\BBCQ\
\newblock {\Bem Journal of the Association for Natural Language Processing},
  \mbox{\BPGS\ 141--160}.
\newblock (in Japanese).

\bibitem[\protect\BCAY{{NTCIR committee}}{{NTCIR
  committee}}{2005}]{Ntcir5_patent_web_2}
{NTCIR committee} \BBOP 2005\BBCP.
\newblock
    \newblock \BBOQ {The Patent Retrieval Task in the NTCIR-5 Workshop}\BBCQ\ 
\newblock http://www.slis.tsukuba.ac.jp/ \~fujii/ ntcir5/ cfp-en.html.

\bibitem[\protect\BCAY{Okamoto \BBA\ Satoh}{Okamoto \BBA\
  Satoh}{1995}]{Okamoto97B_2}
Okamoto, S.\BBACOMMA\ \BBA\ Satoh, K. \BBOP 1995\BBCP.
\newblock \BBOQ An Average-Case Analysis of k-Nearest Neighbor Classifier\BBCQ\
\newblock In {\Bem Proceedings of the First International Conference on
  Case-Based Reasoning Research and Development (ICCBR '95)}, \mbox{\BPGS\
  253--264}.

\bibitem[\protect\BCAY{Ristad}{Ristad}{1997}]{ristad97}
Ristad, E.~S. \BBOP 1997\BBCP.
\newblock \BBOQ {Maximum Entropy Modeling for Natural Language}\BBCQ\
\newblock ACL/EACL Tutorial Program, Madrid.

\bibitem[\protect\BCAY{Robertson, Walker, Jones, Hancock-Beaulieu, \BBA\
  Gatford}{Robertson et~al.}{1994}]{robertson_trec3_2}
Robertson, S.~E., Walker, S., Jones, S., Hancock-Beaulieu, M.~M., \BBA\
  Gatford, M. \BBOP 1994\BBCP.
\newblock \BBOQ Okapi at {TREC-3}\BBCQ\
\newblock In {\Bem Proceedings of the third Text REtrieval Conference
  (TREC-3)}, \mbox{\BPGS\ 109--126}.

\bibitem[\protect\BCAY{Schellner}{Schellner}{2002}]{Schellner2002_2}
Schellner, I. \BBOP 2002\BBCP.
\newblock \BBOQ Japanese File Index classification and {F-terms}\BBCQ\
\newblock {\Bem World Patent Information}, {\Bbf 24}, \mbox{\BPGS\ 197--201}.

\bibitem[\protect\BCAY{Singhal, Choi, Hindle, \BBA\ Pereira}{Singhal
  et~al.}{1997}]{smart97_2}
Singhal, A., Choi, J., Hindle, D., \BBA\ Pereira, F. \BBOP 1997\BBCP.
\newblock \BBOQ AT\&T at TREC-6\BBCQ\
\newblock In {\Bem SDR Track in NIST Special Publication 500-226: The 6th Text
  REtrieval Conference (TREC6)}, \mbox{\BPGS\ 227--232}.

\bibitem[\protect\BCAY{Singhal, Buckley, \BBA\ Mitra}{Singhal
  et~al.}{1996}]{Singhal96_2}
Singhal, A., Buckley, C., \BBA\ Mitra, M. \BBOP 1996\BBCP.
\newblock \BBOQ Pivoted document length normalization\BBCQ\
\newblock In {\Bem Proceedings of the 19th annual international ACM SIGIR
  conference on Research and development in information retrieval (SIGIR '96)},
  \mbox{\BPGS\ 21--29}.

\bibitem[\protect\BCAY{Utiyama}{Utiyama}{2005}]{ruby-ir-eng2_2}
Utiyama, M. \BBOP 2005\BBCP.
    \newblock \BBOQ Information Retrieval Module for Ruby\BBCQ\ 
\newblock http://www2.nict.go.jp/x/ x161/members/mutiyama/software.html.

\bibitem[\protect\BCAY{Utiyama \BBA\ Isahara}{Utiyama \BBA\
  Isahara}{2003}]{NLP2003_eng_2}
Utiyama, M.\BBACOMMA\ \BBA\ Isahara, H. \BBOP 2003\BBCP.
\newblock \BBOQ Large scale text classification\BBCQ\
\newblock In {\Bem Proceedings of the 9th Annual Meeting of the Association for
  Natural Language Processing}, \mbox{\BPGS\ 385--388}.
\newblock (in Japanese).

\bibitem[\protect\BCAY{Yang \BBA\ Liu}{Yang \BBA\ Liu}{1999}]{Yang-sigir99_2}
Yang, Y.\BBACOMMA\ \BBA\ Liu, X. \BBOP 1999\BBCP.
\newblock \BBOQ A re-examination of text categorization methods\BBCQ\
\newblock In {\Bem Proceedings of the 22nd annual international ACM SIGIR
  conference on Research and development in information retrieval (SIGIR '99)},
  \mbox{\BPGS\ 42--49}.

\end{thebibliography}

\begin{biography}

\bioauthor{Masaki Murata}
{Masaki Murata received his Bachelor's,
  Master's, and Doctorate degrees in engineering from Kyoto University in 1993, 1995, 
  and 1997, respectively.  
He is a senior researcher at the National Institute of Information and Communications Technology, Japan, 
an independent administrative institution.  
He is a member of the Information Processing Society of Japan,
the Japanese Society for Artificial Intelligence, 
the Institute of Electronics, Information and Communication Engineers,
the Mathematical Linguistic Society of Japan, 
and the Association for Computational Linguistics.
His research interests include natural language processing, machine translation, 
information retrieval, and question answering.
}


\bioauthor{Toshiyuki Kanamaru}
{
Toshiyuki Kanamaru received 
the Bachelor of Integrated Human Studies 
and Masters of Human and Environmental Studied 
from Kyoto University, in 2001 and 2003 respectively.
He is a member of the National Institute of Information 
and Communications Technology.
He is a member of the Information Processing Society of Japan,
the Japanese Cognitive Linguistics Association,
the Japanese Cognitive Science Society,
and the Association for Natural Language Processing.
His research interests include cognitive linguistics and 
natural language processing.
}

\bioauthor{Tamotsu Shirado}
{
Tamotsu Shirado received the Dr. Eng. degree in 1999 from University of
Electro-Communications, Japan. Since 1986 he has been with National
Institute of Information and Communications Technology, where he
is currently a senior research scientist.
He is a member of the Information Processing Society of Japan,
and the Institute of Electronics, Information and Communication Engineers.
His research interests cover psycholinguistics.
}

\bioauthor{Hitoshi Isahara}
{
Hitoshi Isahara received his Bachelor's,
Master's, and Doctoral degrees in engineering from Kyoto University in 1978, 1980,
and 1995, respectively.  He is currently a leader of the Computational Linguistic Group  
at the National Institute of Information and Communications Technology, Japan, 
an independent administrative institution.  
He is a member of the Information Processing Society of Japan, 
the Japanese Society for Artificial Intelligence, 
the Japanese Cognitive Science Society, 
and the Association for Computational Linguistics.
His research
interests include natural language processing, machine translation, and
lexical semantics.
}

\end{biography}


\biodate


\end{document}
