\documentclass[english]{jnlp_3.3}
\usepackage{jnlpbbl_2.2}
\usepackage[dvipdfmx]{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{url}
\usepackage{array}
\usepackage{hangcaption_jnlp}
%%%%\usepackage{array}
%%%%\usepackage{udline}
%%%%\setulminsep{1.2ex}{0.2ex}
%%%%\let\underline=\ul
\allowdisplaybreaks

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% author's definition
%%%%\newcommand{\argmax}{\mathop{\rm arg~max}\limits}
%%%%\newcommand{\argmin}{\mathop{\rm arg~min}\limits}
%%%%\usepackage{pslatex, graphicx}
%%%%\usepackage{ascmac}
%%%%\usepackage{comment}
%%%%\usepackage{lscape}
%%%%\usepackage{color}
%%%%\setcounter{topnumber}{6}
%%%%\setcounter{totalnumber}{6}
%%%%\def\topfraction{1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Volume{28}
\Number{3}
\Month{September}
\Year{2021}
%%%%\Issuetitle{「　　　　」特集号}

\received{2021}{2}{1}
\revised{2021}{4}{28}
%%%%\rerevised{2006}{5}{6}
\accepted{2021}{6}{9}

\setcounter{page}{802}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\esubject{General Paper}
\etitle{Improved Method for Organizing Information Contained in Multiple Documents into a Table}
\eauthor{Masaki Murata\affiref{Author_1} \and Kensuke Okazaki\affiref{Author_1} \and Qing Ma\affiref{Author_2}} 
\eabstract{%
\citeA{Okazaki_eng} have proposed a method for organizing the information contained in multiple documents into a table without limiting the information to be extracted. In this study, we propose a method for improving the accuracy of these tables. In our proposed method, information is first clustered hierarchically. Next, for the results of hierarchical clustering (with the number of clusters ranging from $1$ to $n$), the degree of filling and the information density of the resulting table are calculated. The number of clusters when the balance between these two indicators is optimal is chosen as the optimal number of clusters. The results of the method using the chosen number of clusters are organized into a table. In the conventional method, the number of clusters estimated by the $X$-means method tends to be too small. As demonstrated by the results of experiments using 15 types of multiple documents, the proposed method improves this problem, with its estimated number of clusters being closer to the optimum. The average evaluation result in the tables (F-measure) when applying the conventional method was 0.43; the proposed method improves this to 0.65. We therefore confirm the effectiveness of the proposed method.
}
\ekeywords{Information Extraction, Table, X-means, Hierarchical Clustering}

\headauthor{Murata et al.}
\headtitle{Improved Method for Organizing Information}

\affilabel{Author_1}{}{Tottori University}
\affilabel{Author_2}{}{Ryukoku University}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}

In recent years, it has become significantly easier to obtain information from the vast amount of electronic documents stored on the Web.
\citeA{Okazaki_eng} proposed a method for organizing the information contained in multiple documents into a table without limiting the information to be extracted.
Here, ``multiple documents'' refers to a collection of documents of the same type.
For example, information such as ``maker'' and ``price'' included in new product articles for smartphones of different models is organized in a table based on type.
Arranging the information of multiple documents of the same type in a table in this way is useful not only for extracting information, but also for comparing information between documents.
In Okazaki et al.'s study, information contained in multiple documents of the same type was extracted in sentence units, and the results of classifying the information by the clustering method of the $X$-means method \cite{xmeans1} 
were organized into a table with documents as rows and clusters as columns.
In this paper, we call this method the ``conventional method.''
The $X$-means method is a clustering method that automatically estimates the optimum number of clusters based on an index called BIC while repeating the clustering using the $K$-means method at $K = 2$. 
It is not necessary to specify the number of classification destinations.
However, the number of clusters estimated by the $X$-means method tends to be smaller than the optimal number of clusters; in the resulting tables, too much information is organized into a single column, and the accuracy of the tables is low. 


To address this problem, we propose a method for estimating the number of clusters by optimizing the balance between the degree of filling and the information density of a table.
The degree of filling of a table indicates that there are fewer blanks in the table. 
The degree of information density of a table indicates that the information in the same column of the table is more similar. 
With the proposed method, 
it is possible to create a more appropriate table where 
similar contents are arranged in the same column of a table with fewer blanks
by using the degree of filling and the information density of a table. 
Blank cells are generated when creating a table.
The degree of filling of a table is useful for reducing the number of blank cells. 


With the proposed method, information is first clustered hierarchically.
The results of hierarchical clustering, with the number of clusters ranging from 1 to $n$, are organized in $n$ tables.
Then, for each table, the degree of filling and the degree of organized information density are calculated.
When the balance between these two indicators is optimal, the resulting number of clusters is estimated to be optimal.
The results, with the optimal number of clusters estimated at the end, are organized in a table.
In this study, we attempt to improve the accuracy of the tables of the conventional method using the above approach.
This study was completed in Japanese, and Japanese text was used for the experiments. 

In this paper, we propose a method for estimating the optimum number of clusters based on the degree of filling and density in a table from the results of hierarchical clustering.
Several methods (a silhouette analysis, Upper Tail method, and BIC-based method) have already been proposed to estimate the optimal number of clusters. 

Our proposed method 
estimates the number of clusters by optimizing the balance between the degree of filling and the information density of a table.
In addition, the degree of filling of a table indicates that there are fewer blanks in the table. 
The degree of information density of a table indicates that the information in the same column of the table is more similar. 
With the proposed method, 
it is possible to create a more appropriate table in which
similar contents are arranged in the same column of the table with fewer blanks
by using the degree of filling and the information density of the table.

The other methods, i.e., the $X$-means method, silhouette analysis, Upper Tail method, and BIC-based method use an index similar to the degree of the information density, 
but do not use the degree of filling of the table. 
However, the proposed method does have the novelty of using such degree of filling.

In the experiments described in this paper, 
we confirmed that the proposed method significantly outperformed other methods. 
The novelty of method using the degree of filling of a table
seems to be the reason why the proposed method performed better than the other approaches. 


This paper is related to information extraction \cite{IE-2005Gibbs,Chang2006,Turmo2009,Fader2011,fukuda_nanba2014,Grishman2015,IEEE2017-IE,OIE-2018}; a brief description of related studies and their relevance to the present work is as follows. 
\citeA{fukuda_nanba2014} constructed a system that extracts expressions indicating the effects of technology from research papers and visualized the extracted information. 
They created supervised data and used machine learning to extract the expressions. 
By contrast, Okazaki et al.'s study \cite{Okazaki_eng} and the present approach use clustering instead of machine learning; there is therefore no need to create learning data. 


We additionally examined several studies related to tables \cite{Swain2016table,nishida2017table}. 
Swain et al. constructed a toolkit for an automated extraction of chemical information from tables in the scientific literature. 
Nishida et al. also constructed a method of understanding the semantic structures of tables. 
By contrast, Okazaki et al.'s study \cite{Okazaki_eng} and our own extract important information from sentences in documents and construct tables including extracted information. 

\citeA{akano_tmp1} studied tables and information extraction. 
In addition, Akano et al. utilized word2vec \cite{Mikolov2013} to represent the words that appear on Wikipedia pages related to a castle as vectors
and then clustered and organized them in the form of a table.
In word2vec, word vectors are obtained by considering the surrounding words,
and word vectors vary depending on the words that appear in the surroundings. 
For example, the words related to a person can be classified based on the role that they have in the castle.
However, only words are organized in the table in Akano et al.'s study and there is no 
information about the role in the table. 
In Akano et al.'s method, 
information was extracted word-by-word, for example, ``Mouri Motonari''; 
however, in Okazaki et al.'s study \cite{Okazaki_eng} and our own approach, information is extracted as a sentence unit, e.g., ``Mouri Motonari became a castle owner.''
In Okazaki et al.'s study \cite{Okazaki_eng} and our own method, 
we can see the role of a person in the sentences shown in the table.


Section \ref{sec:conventionalmethod} describes 
the conventional approach using the $X$-means method. 
Section \ref{sec:proposedmethod} describes 
the proposed method using hierarchical clustering. 
Section \ref{sec:exp} describes 
experiments confirming the effectiveness of the proposed method. 
Section \ref{sec:exp} includes an explanation of comparison methods (silhouette analysis, Upper Tail method, and BIC-based method). 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conventional Method}
\label{sec:conventionalmethod}

In Okazaki et al.'s study \cite{Okazaki_eng}, information contained in multiple documents of the same type was extracted in sentence units. The resulting information was clustered using a method called the $X$-means method \cite{xmeans1} and organized in a table.

In their study, 
the system creates a table with sentences that describe the same type of things in the same column. 
The clustering of sentences is used to collect sentences that describe the same type of things.

In the study, FastText \cite{FASTTEXT} is used to grasp similar contents of different words. 
Things with similar content may be written using different words. FastText allows us to vectorize words and make similar words into similar vectors.
FastText is used such that we can grasp similar content of different words when we check the similarity of sentences containing different words.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Explanation of the Conventional Method}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Procedure for organizing information in a table}
\label{make_table_method}

The procedure used by Okazaki et al. for organizing sentence information in a table is shown below. 

\begin{description}
\item[Step 1] The system divides multiple documents into sentences. \label{short_sentence}
\item[Step 2] The system calculates the sentence vector of each sentence obtained in Step 1. \label{svector}
\item[Step 3] The system clusters the sentence vectors using the $X$-means method \cite{xmeans1}. \label{clustering}
\item[Step 4] The results of clustering are organized into a table with documents as rows and clusters as columns. During clustering, which document contained the information is not taken into consideration, and thus one cell may contain multiple pieces of information.
\label{juuyoudo}
\item[Step 5] The system gives a name to each cluster (column) in the table.  \label{koumoku}
\end{description}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Step 2: Calculation of statement vector}

The vector of each sentence in Step 2 of Section \ref{make_table_method} is obtained by the following procedure.
\begin{enumerate}
\item The system conducts a morphological analysis of the sentences using MeCab.\footnote{\url{http://taku910.github.io/mecab/}}
\item It extracts words whose part-of-speech is a noun and whose detailed part-of-speech classification does not contain a pronoun, number, non-independent word, or adverb among the morphological analysis results.
\item The sum of the vectors of the extracted words is treated as the sentence vector. Word vectors are obtained by learning all articles on Wikipedia by FastText \cite{FASTTEXT}.  
\end{enumerate}

Things with similar contents may be written in different words. FastText is used to express the similarity of sentences 
and thus even such things can be grasped as similar contents. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Step 3: Clustering of sentences}
\label{tejun3-xmeans}

In Step 3 of Section \ref{make_table_method}, sentences are clustered using the $X$-means method \cite{xmeans1}. 
The $X$-means method repeats the division by the $K$-means method at $K = 2$ and determines whether to stop the division based on the Bayesian information $BIC$. 
In this clustering method, the number of clusters is determined automatically. 
If $BIC \leq BIC'$ is true for the Bayesian information $BIC$ before the division and the Bayesian information $BIC'$ after the division, the division is stopped.

Assuming that the $p$ multivariate normal distribution is given the following equation, $BIC$ is defined as follows.
\[
f(\theta_i;x)=(2\pi)^{-p/2}|V_i|^{-1/2}\exp\left[\frac{1}{2}(x-\mu_i)^tV_i^{-1}(x-\mu_i)\right]
\]
Here, $\hat{\theta_i}=[\hat{\mu_i},\hat{V_i}]$ is the maximum likelihood estimate of the $p$ multivariate normal distribution, $\mu_i$ is the $p$th mean vector, and $V_i$ is the variance-covariance matrix of $p \times p$. 
In addition, $q$ is the number of dimensions in the parameter space, which is $q = 2p$ if the covariance of $V_i$ is ignored, and $q=p(p+3)/2$ if it is not. 
Moreover, $L$ is a likelihood function ($L = \Pi f()$).
\[
BIC=-2\log(L\hat{\theta_i};x_i \in C_i) + q\log{n_i}
\]
In addition, $BIC'$ (after division) is defined as follows. 
Here, $\hat{\theta_i'}=[\hat{\theta_i^1},\hat{\theta_i^2}]$ is an estimated value of the maximum likelihood of the $p$ multivariate normal distribution in each of the two split clusters. 
If we ignore the covariance, there are two parameters, mean and variance, for each $p$, and thus $q'=2 \times 2p = 4p$; otherwise, $q'=2q=p(p+3)$.
\[
BIC'=-2\log(L\hat{\theta_i'};x_i \in C_i) + q'\log{n_i}
\]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Step 4: Organizing clustering results in a table}

The clustering results of Step 3 in Section \ref{make_table_method} are organized into a table with documents as rows and clusters as columns.
To improve the readability of the table, the columns are sorted in order of importance.
\par In the columns of the table that organize the clustering results, some columns are of high importance (such as Column 1 of Table \ref{tejun4_example}, which consists only of related sentences), and some are of low importance (such as Column 2, which includes unrelated sentences). 
Here, the importance of a column is defined based on the density and document coverage.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 1
\begin{table}[b]
\input{03table01.tex}
\caption{Example of importance in a column}
\label{tejun4_example}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The density $d_k$ in the $k$th column is defined by Equation \ref{siki_missyuudo}.
Here, $N_k$ is the total number of sentences contained in the $k$th column, and $S_{k,l}$ is the vector of the $l$th sentence contained in the $k$th column. 
$S_{k,mean}$ is the average of the vectors of the sentences contained in the $k$th column.
\begin{equation}
d_k = \frac{1}{N_k} \sum_{l=1}^{N} \frac{S_{k,l} \cdot S_{k,mean}}{|S_{k,l}||S_{k,mean}|}
\label{siki_missyuudo}
\end{equation}

The system normalizes the column density $d_k$ obtained by Equation \ref{siki_missyuudo} such that the minimum value is zero and the maximum value is 1 using Equation \ref{siki_nc}.
Here, $nd_k$ is the normalized column density of the $k$th column, and $K$ is the total number of columns.
\begin{gather}
nd_k = \frac{d_k - d_{min}}{d_{max} - d_{min}} 
\label{siki_nc}\\
d_{min} = \min_{1 \leq k \leq K} d_k \\
d_{max} = \max_{1 \leq k \leq K} d_k
\end{gather}

The document coverage rate $c_k$ in the $k$th column is defined by Equation \ref{siki_mourado}.
In addition, $p_k$ is the number of documents for which sentences could be extracted in the $k$th column, and $P$ is the total number of documents.
\begin{equation}
c_k = \frac{p_k}{P}
\label{siki_mourado}
\end{equation}

The document coverage $c_k$ obtained by Equation \ref{siki_mourado} is normalized by using Equation \ref{siki_np} such that the minimum value is zero and the maximum value is 1. \label{nrm_page_rate}
Here, $nc_k$ is the normalized document coverage of the $k$th column and $K$ is the total number of columns.
\begin{gather}
nc_k = \frac{c_k - c_{min}}{c_{max} - c_{min}}
\label{siki_np} \\
c_{min} = \min_{1 \leq k \leq K} c_k \\
c_{max} = \max_{1 \leq k \leq K} c_k
\end{gather}

We define the importance $i_k$ of the $k$th column using Equation \ref{siki_juuyoudo}.
\begin{equation}
i_k = nd_k \times nc_k
\label{siki_juuyoudo}
\end{equation}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Step 5: A methodology for finding the item name of a cluster}

In Step 5 of Section \ref{make_table_method}, 
item names are given to each column through the following procedure.

\begin{enumerate}
\item For each sentence included in the cluster, all nouns are extracted. \label{meisi}
\item The document frequency is found for each word extracted in \ref{meisi}.
\item The word with the highest document frequency is chosen as the item name of the cluster.
\item If the highest document frequency is shared by two or more words, all are used as the item name of the cluster (separated by commas).
\end{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Problems with conventional method}
\label{mondai}

Using the conventional method, it is often the case that either too much information is organized in one column, as in Column 1 of Table \ref{t1}, or the information is classified too finely, as in Columns 2 and 3 of Table \ref{t2}. A well-balanced table, such as Table \ref{t3}, is desirable.
In addition, the $X$-means method tends to underestimate the optimum number of clusters (that is, the optimum number of columns in the resulting table). 
This often results in a table with too much information in one column, such as Column 1 of Table \ref{t1}, where memory and storage information are mixed. 
This was the cause of the low accuracy.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 2
\begin{table}[t]
\input{03table02.tex}
\caption{Example of too much information in one column}
\label{t1}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 3
\begin{table}[t]
\input{03table03.tex}
\caption{Example of information being classified too finely}
\label{t2}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 4
\begin{table}[t]
\input{03table04.tex}
\caption{Example of an optimal table}
\label{t3}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proposed method}
\label{sec:proposedmethod}

To solve the problems of the conventional method, we propose a method for estimating the number of clusters by optimizing the balance between the filling degree and the density of information in the table.
In the $X$-means method used in the conventional method, the table obtained in each execution is different owing to the initial value dependency.
The proposed method uses a hierarchical clustering method that does not depend on the initial values.

With the proposed method, a table with the maximum score is selected after creating a corresponding individual table for each different $k$ (the number of clusters). 
The hierarchical clustering method is used to create individual tables.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Procedure used with our proposed method}

The procedure of our proposed method is shown below. 

\begin{description}
\item[Step 1] The system divides multiple documents into sentences. 
\item[Step 2] The system calculates the sentence vector of each sentence. 
\item[Step 3] The system clusters the sentence vectors using a hierarchical clustering method based on Ward's approach. 
\item[Step 4] The results of clustering are organized into a table with documents as rows and clusters as columns. 
The filling degree of a table with $k$ clusters is calculated using Equation \ref{cover}, and the density of information in the table is calculated from Equation \ref{density}.
In addition, $|c_{k,i}|$ is the total number of sentences contained in the $i$th column of the table with $k$ clusters,  
$d_{k,i,j}$ is the vector of the $j$th sentence in the $i$th column of the table with $k$ clusters, and 
$C_k$ is the total number of columns in the table with $k$ clusters, and $cosine(x,y)$ is the function for finding the cosine similarity of $x$ and $y$.
%%%%\label{juuyoudo2}
\begin{gather}
cover_k = \frac{\mbox{The number of non-empty cells in the table with $k$ clusters}}{\mbox{The total number of cells in the table with $k$ clusters}}
\label{cover} \\
density_k  =  \min_{j \neq h}(cosine(d_{k,i,j},d_{k,i,h}))
\label{density} \\
i  =  1, \cdots, C_k  \, \, \,  \, \, \, \, \, \,    j,h = 1, \cdots, \mbox{$|c_{k,i}|$}  \nonumber  
\end{gather}
Here, $COVER$ is the set of $cover_k$ for all clusters, $max(COVER)$ is the maximum value of the set $COVER$, and $min(COVER)$ is the minimum value of the set $COVER$.
The system normalizes $cover_k$ in each cluster to the range of $0$ to $1$ using Equation \ref{seiki1}.
\begin{equation}\label{seiki1}
norm(cover_k) = \frac{cover_k-min(COVER)}{max(COVER)-min(COVER)}
\end{equation}
Similarly, $DENSITY$ is the set of $density_k$ for all clusters, $max(DENSITY)$ is the maximum value of $DENSITY$, and $min(DENSITY)$ is the minimum value of $DENSITY$. 
The system normalizes $density_k$ in each cluster to the range of $0$ to $1$ using Equation \ref{seiki2}.
\begin{equation}\label{seiki2}
norm(density_k) = \frac{density_k-min(DENSITY)}{max(DENSITY)-min(DENSITY)}
\end{equation}
The system finds $Score_k$ in the table with $k$ clusters using Equation \ref{score}. 
The number of clusters $k$ when $Score_k$ is maximized is adopted as the optimum number of clusters.
\begin{equation}\label{score}
Score_k = norm(cover_k) \times norm(density_k)
\end{equation}


\item[Step 5] The system gives item names to each cluster in the table. 
\end{description}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Hierarchical clustering}

Hierarchical clustering is a clustering method that repeats the integration of clusters with the shortest distance. 
There are several methods for hierarchical clustering depending on the definition of the distance between clusters. 
In this study, we used Ward's method. 
In Ward's method, the distance $D(C_1,C_2)$ between Cluster $C_1$ and Cluster $C_2$ is defined as follows.
\begin{gather*}
D(C_1,C_2) = E(C_1 \cup C_2) - E(C_1) - E(C_2) \\
\mathrm{E}(C_i)=\sum_{\mathbf{x}\in C_i} (d(\mathbf{x},\mathbf{c}_i))^2 \\
c_i = \sum_{\mathbf{x}\in C_i}\mathbf{x}/{|C_i|}
\end{gather*}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Experiment}
\label{sec:exp}

In this section, we evaluate and compare tables generated using the conventional method and tables generated using the proposed method with the same input data.
In the $X$-means method used in the conventional approach, a different table can be obtained from each execution, depending on the initial value.
For our experiments, a table was generated 1,000 times; among the evaluation results of all tables applied, the maximum, average, and minimum value results were used as comparison targets.


In this section, we also describe comparative experiments between the proposed method and methods differing from the conventional method.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Experimental environment}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{FastText learning environment}

The word vector used in the calculation of the sentence vector is obtained using FastText \cite{FASTTEXT}.
FastText is a two-layer neural network consisting of a hidden layer and an output layer; the hidden layer corresponds to the distributed representation of words.
All 1,061,375 articles (22,794,659 lines) in Japanese Wikipedia (June 1, 2017)\footnote{\url{https://ja.wikipedia.org/}. The data were crawled on ``June 1, 2017.''} were used as learning data for FastText.
The learning data were unified in full-width for Japanese characters and numbers and half-width for Latin characters and numbers, and were divided into morpheme units with MeCab.
Skip-gram was used as the learning model in FastText, with 300 vector dimensions. The default values were used for all other parameters.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Experimental data}
\label{data_information}

Fifteen types of multiple documents were extracted 
from newspaper articles, Web product article pages, and Wikipedia 
for use in the experiment. 
The details of each type are shown in Table \ref{input_information}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 5
\begin{table}[b]
\input{03table05.tex}
\caption{Details of each type of multiple documents used in the experiment}
\label{input_information}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

For newspaper articles, 20 articles containing the corresponding word (e.g., ``robbery'') in the headline were randomly extracted from 2016 Mainichi Shinbun newspaper articles. 
For Web product article pages, the latest 20 new product news articles in the corresponding category (e.g., ``smartphone'') 
were extracted from the web pages of Kakaku.com (January 15, 2018).\footnote{\url{https://kakaku.com/}. The data were crawled on ``January 15, 2018.''} 
For Wikipedia, 
the summary sections of 20 randomly selected pages 
included in a corresponding Wikipedia category (e.g., ``100 Famous Castles in Japan'') were extracted 
from Japanese Wikipedia (June 1, 2017).
The same Wikipedia (June 1, 2017) was used for input documents and the learning data for FastText.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Evaluation method}

The accuracy of generated tables is evaluated using the following procedure. 
\begin{enumerate}
\item We focus on each column of a correct table, which is manually created in advance. 
\item We extract those columns of an experimental table containing the most data in the column of interest. 
The experimental table is the output of the proposed (or other) method. 
\item We find the precision, recall, and $F$-measure using Equations \ref{tekigou} through \ref{fti}.
\item We perform 2 and 3 for all of the correct columns, find the average of the $F$-measures in all columns, and use this as the evaluation result of the experimental table.
\end{enumerate}
\begin{gather}\label{tekigou}
\scalebox{0.9}{$\displaystyle
\mbox{Precision} = \frac{\mbox{\small The number of sentences commonly included in the correct table column and outputted table column}}{\mbox{The number of sentences included in the outputted table column}}
$} \\
\label{saigenritu}
\scalebox{0.9}{$\displaystyle
\mbox{Recall} = \frac{\mbox{\small  The number of sentences commonly included in the correct table column and outputted table column}}{\mbox{The number of sentences contained in the correct table column}}
$} \\
\label{fti}
\mbox{F-measure} = \frac{2 \times \mbox{Precision} \times \mbox{Recall}}{\mbox{Precision} + \mbox{Recall}}
\end{gather}

Correct tables are created manually without using the output tables of the system. 
A correct table is manually created 
by manually checking 20 input articles, 
collecting sentences that have the same main content, 
and putting them in the same column.


Here, an example of calculating the F-measure of a column is described. 
We suppose the following condition: 
We use ten documents from Wikipedia (wrestler) and are focusing on the fifth column of the correct table.
The column of the outputted table containing the most sentences in the fifth column of the correct table is the fourth column.  
The fifth column of the correct table is shown in Table \ref{tab:calc_correct_table}. 
The fourth column of the output table is shown in Table \ref{tab:calc_output_table}. 
In this case, the precision, recall, and F-measure are calculated as follows.
\begin{gather}\label{tekigou2}
\scalebox{0.9}{$\displaystyle
\mbox{Precision} = \frac{\mbox{\footnotesize The number of sentences commonly included in the correct table column and output table column}}{\mbox{\small The number of sentences included in the output table column}}
 = \frac{5}{5} 
$} \\
\label{saigenritu2}
\scalebox{0.9}{$\displaystyle
\mbox{Recall} = \frac{\mbox{\footnotesize  The number of sentences commonly included in the correct table column and output table column}}{\mbox{\small The number of sentences contained in the correct table column}}
 = \frac{5}{8}
$} \\[2ex]
\label{fti2}
\mbox{F-measure} = \frac{\mbox{2} \times \mbox{Precision} \times \mbox{Recall}}{\mbox{Precision} + \mbox{Recall}} = \mbox{0.77}
\end{gather}

With respect to the precision, there are five rows in Table 7 (output table), which is the number of sentences included in the output table column, 
and they all appear in Table 6 (correct table); thus, the precision is 5/5. 
With respect to the recall, there are eight rows in Table 6 (correct table), which is the number of sentences contained in the correct table column, 
and five of them appear in Table 7 (output table); thus, the recall is 5/8. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 6
\begin{table}[t]
\input{03table06.tex}
\caption{The fifth column of a correct table (Wikipedia (wrestler))}
\label{tab:calc_correct_table}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 7
\begin{table}[t]
\input{03table07.tex}
\caption{The fourth column of an output table (Wikipedia (wrestler))}
\label{tab:calc_output_table}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Comparison methods}

In this paper, we propose a method for estimating the optimum number of clusters based on the degree of filling and density in a table from the results of hierarchical clustering.
Several indicators have already been proposed to estimate the optimal number of clusters.
Therefore, experiments comparing 
our proposed methods with other methods using the indicators 
were conducted by applying the following three cluster number estimation methods in Step 4 of the proposed method.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Comparison method 1: Silhouette analysis}

A silhouette analysis \cite{SILHOUETTES} is an index based on the cohesiveness of data in clusters and the discreteness between clusters.
In a silhouette analysis, the silhouette coefficients of all data are calculated for each number of clusters, and the number of clusters when the average value 
of the silhouette coefficients is maximized is selected.

The silhouette coefficient $s(i)$ of the datapoint $i$ is expressed by Equation \ref{silhouettes}.
Here, $a(i)$ is the average distance between datapoint $i$ and each datapoint contained in the cluster to which point $i$ belongs.
In addition, $b(i)$ represents the average distance between the datapoint $i$ and each point contained in the cluster closest to $i$ among the clusters to which $i$ does not belong.
Here, the cluster closest to $i$ is the cluster for which the average distance between $i$ and each datapoint contained in the cluster is the smallest.
In addition, $max\{a(i),b(i)\}$ represents the larger value of $a(i)$ and $b(i)$.
\begin{equation}\label{silhouettes}
\scalebox{1}{$\displaystyle
s(i) = \frac{b(i)-a(i)}{max\{a(i),b(i)\}}
$}
\end{equation}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Comparison method 2: Upper tail method}

The upper tail method was proposed by \citeA{UPPERTAIL} to determine the optimum number of clusters based on statistical stop rules for the results of hierarchical clustering.
In the upper tail method, first, the reference value $\alpha_j$ is obtained for each clustering result when the number of clusters $j$ is $2$ to $N-1$.
Here, $\alpha_j$ represents the minimum distance between the centroids of clusters in the clustering result with number of clusters $j$.
Next, the system starts with the value of $j$ from 2, and increases the value of $j$ by 1 until the following conditions are no longer satisfied. 
\[
\alpha_j \leq \bar{\alpha} + ks_\alpha
\]
The value of $j$ when stopped is selected as the optimum number of clusters.
Here, $\bar{\alpha}$ and $s_\alpha$ represent the mean of all reference values $\alpha_j$ and the square root of the unbiased variance of all reference values $\alpha_j$.
Regarding the value of $k$, \citeA{UPPERTAIL} uses a value of 2 to 4 when the number of data is 60 to 120.
In addition, \citeA{CLUSTERING_COMPARE_eng} reported that $k = 3$ is a good value when the number of data in one group is approximately 30 to 50.
With reference to these, in this study, assuming that the number of data in one group is less than the number of documents (20 or less), the experiment is conducted using $k = 1$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Comparison method 3: BIC-based method}

The same method as the $X$-means method in Section \ref{tejun3-xmeans} is applied to the results of hierarchical clustering, and the optimum number of clusters is estimated.
Specifically, every time the tree diagram obtained as a result of hierarchical clustering is divided into two parts in order from the root of the tree, the system finds $BIC$ before division and $BIC'$ after division in the same way as described in Section \ref{tejun3-xmeans}, and if $BIC \leq BIC'$, the system stops splitting. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Experimental results}\label{result}

An example of a part of a table generated by the proposed method 
is shown in Table \ref{table_result_best}. 

The first column of the table shows the height and weight of sumo wrestlers.
The second column of the table shows the sumo ratings such as Makushita and Front.
The third column of the table shows the hometown of the wrestlers.
In the table, the contents related to sumo wrestlers are acquired. 
In the table, each column contains useful information with the same content with a few blanks. 
We were able to generate a table that is useful for gathering information. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 8
\begin{table}[t]
\input{03table08.tex}
\caption{An example of a part of a table obtained using the proposed method (Wikipedia (wrestler))}
\label{table_result_best}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We show the evaluation results using the conventional method, the proposed method, and comparison methods  
(silhouette analysis, upper tail method, and BIC-based method) in Table \ref{evaluation_result2}.
We also conducted a paired two-sided $t$ test to determine the significance of the difference in the evaluation results. 
The significance level was 0.05. The results of the significance test are shown in Table \ref{yuuisa_table2}.


In an experiment using 15 types of multiple documents, the average evaluation result of the proposed method (F-measure) was 0.65, which exceeded that of the other methods. 
The $t$ test confirmed that our proposed method significantly outperformed the other methods. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 9
\begin{table}[t]
\input{03table09.tex}
\caption{Evaluation results of each table}
\label{evaluation_result2}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 10
\begin{table}[t]
\input{03table10.tex}
\caption{Results of significance test}
\label{yuuisa_table2}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Discussion in comparison with conventional method}

In an experiment using 15 types of multiple documents, the average evaluation result of the proposed method was 0.65, which exceeded the maximum and average values of the conventional method.
In addition, based on a paired two-sided $t$ test with a significance level of 0.05, a significant difference was found between the evaluation results of the conventional method and the proposed method.
In the proposed method, by optimizing the balance between the filling degree and the density of information in a table, it is possible to more accurately estimate the number of clusters (columns in the table) suitable for organizing the table. As a result, the accuracy of the table can be improved. 

A comparison of the number of clusters estimated using the conventional and proposed methods with the number of columns in the correct table is shown in Table \ref{colmns_result}.
In addition, a comparison of the absolute values of the difference between the number of clusters estimated using the conventional and proposed methods and the number of columns in the correct table is shown in Table \ref{colmns_result2}.
From these results, the difference from the number of columns in the correct answer table was on average 6.7 for the conventional method. This difference was reduced to 3.8 in the proposed method.
Therefore, the conventional method's problem of the $X$-means method's tendency to underestimate the optimum number of clusters was improved by the proposed method.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 11
\begin{table}[p]
\input{03table11.tex}
\caption{Number of columns in generated tables}
\label{colmns_result}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 12
\begin{table}[p]
\input{03table12.tex}
\hangcaption{Difference between the number of columns in each table and the number of columns in an optimal table}
\label{colmns_result2}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 13
\begin{table}[t]
\input{03table13.tex}
\caption{Precision (average) and recall (average) in a table}
\label{psrs}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

During the experiments, the accuracy of a table was calculated as the average of the precision rates, recall rates, and $F$-measures in the columns of the table.
These results, shown in Table \ref{psrs}, indicate that the average recall rate of the conventional method is 0.79, and its average precision rate is as low as 0.39.
This indicates that the characteristics of the columns in the table obtained using the conventional method tend to include irrelevant information, and the information is less likely to be missed.
By contrast, with the proposed method, the average recall rate is 0.68 and the precision rate is 0.75. The gap between the two indicators is small, indicating that a well-balanced table is obtained using the proposed approach. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion}

Okazaki et al. proposed a method for organizing sentence information contained in multiple documents into a table using the $X$-means method \cite{Okazaki_eng}.
The $X$-means method is a clustering approach that estimates the optimum number of clusters based on $BIC$.
However, the number of clusters (that is, the number of columns in the table) estimated using the $X$-means method tends to be smaller than optimum, which can decrease the accuracy of the resulting table because too much information will be represented in a single column.
To address this problem, we proposed a method for estimating the number of clusters by optimizing the balance between the degree of filling and the density of information in tables resulting from hierarchical clustering of the sentence information.

With the proposed method, information is first clustered hierarchically.
For hierarchical clustering with the number of clusters ranging from $1$ to $n$, the degree of filling and the degree of density of information of the resulting table are calculated. The number of clusters when the balance between these two indicators is optimal is selected as the optimal number of clusters, and the final table is constructed accordingly.
In this study, we were able to improve the accuracy of tables generated by Okazaki et al.'s method by applying our proposed approach. 
The average of the evaluation results ($F$-measure) of the tables generated using the conventional method was 0.43; in addition, our method achieved a value of 0.65, thus confirming its effectiveness.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{jnlpbbl_1.6}
\bibliography{03refs}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{biography}

\bioauthor[:]{Masaki Murata}{%
received his BS and MS degrees and his PhD in engineering from Kyoto University in 1993, 1995, and 1997, respectively. He worked in the Communications Research Laboratory (currently the National Institute of Information and Communications Technology (NICT)), Japan, from 1998 to 2010. In 2010, he moved to Tottori University, Japan, where he worked as a professor in the Department of Information and Electronics, Graduate School of Engineering. 
He is also with the Cross-informatics Research Center, Tottori University. 
His research interests include natural language processing, machine translation, and information retrieval.
}

\bioauthor[:]{Kensuke Okazaki}{%
received his BS and MS degrees in engineering from Tottori University, Japan, in 2018 and 2020, respectively. 
}

\bioauthor[:]{Qing Ma}{%
received his BS degree in electrical engineering from Beihang
University, China, in 1983 and his MS and Dr. Eng. degrees in
computer science from the University of Tsukuba, Japan, in 1987 and 1990,
respectively. He worked in Ono Sokki Co., Ltd., Japan, from 1990 to
1993 and in the Communications Research Laboratory (currently, the
National Institute of Information and Communications Technology
(NICT)), Japan, from 1993 to 2003. In 2003, he moved to Ryukoku
University, Japan, as a professor in the Applied Mathematics and
Informatics Course, Faculty of Advanced Science and Technology. His
research interests include machine learning and natural language
processing.
}
\end{biography}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\biodate






\end{document}

