\documentclass[11pt]{article}

\usepackage{concepts}
\usepackage{jair}
\usepackage{theapa}
%\usepackage{epic}
%\usepackage{eepic}
%\usepackage{ecltree}
\usepackage{times}
%\usepackage{latexsym}
%\usepackage{changebar}
\usepackage{epsfig}
\usepackage{theorem}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{xspace}
\usepackage{algorithm}
\usepackage{algorithmic}
%\usepackage[english]{babel}
%\newcommand{\clD}{\mathbb{P}}
%\newcommand{\setcluster}{\clD}
%\newcommand{\setdok}{D}
%\newcommand{\cluster}{P}
\newcommand{\kmeans}{KMeans\xspace}
\newcommand{\bisec}{Bi-Section-\kmeans}
\newcommand{\parabold}[1]{\vspace{2pt}\noindent\textbf{#1}}
\theoremstyle{break}
\newtheorem{Def}{Definition}

\jairheading{24}{2005}{305--339}{11/04}{8/05}
\ShortHeadings{Learning Concept Hierarchies from Text Corpora using Formal Concept Analysis}
{Cimiano, Hotho, \& Staab}
\firstpageno{305}

\begin{document}

\title{Learning Concept Hierarchies from Text Corpora \\ using Formal Concept Analysis}

\author{\name Philipp Cimiano \email cimiano@aifb.uni-karlsruhe.de \\
       \addr Institute AIFB, University of Karlsruhe \\ Englerstr. 11, 76131 Karlsruhe, Germany\\
       \AND
       \name Andreas Hotho \email hotho@cs.uni-kassel.de \\
       \addr Knowledge and Data Engineering Group, University of Kassel \\ Wilhelmsh\"oher Allee 73, 34121 Kassel, Germany \\
       \AND
       \name Steffen Staab \email staab@uni-koblenz.de \\
       \addr Institute for Computer Science, University of Koblenz-Landau \\ Universit\"atsstr. 1, 56016 Koblenz, Germany}

\maketitle

\begin{abstract}

We present a novel approach to the automatic acquisition of taxonomies
or concept hierarchies from a text corpus. The approach is based on
Formal Concept Analysis (FCA), a method mainly used for the analysis of data,
i.e. for investigating and processing explicitly given information.
We follow Harris' distributional hypothesis and model the context
of a certain term as a vector representing syntactic dependencies
which are automatically acquired from the text corpus with a linguistic parser.
On the basis of this context information, FCA produces a lattice
that we convert into a special kind of partial order constituting
a concept hierarchy.
The approach is evaluated by comparing the resulting concept hierarchies
with  hand-crafted taxonomies for two domains: tourism and finance.
We also directly compare our approach with hierarchical agglomerative
clustering as well as with \bisec as an instance of a divisive clustering
algorithm. Furthermore, we investigate the impact of using different
measures weighting the contribution of each attribute as well as of applying
a particular smoothing technique to cope with data sparseness.

\end{abstract}

\input{introduction}

\input{overall}

\input{fca}

\input{text_processing}

\input{evaluation}

%\input{open}

\input{related}

\input{conclusion}

\acks{
We would like to thank all our colleagues for feedback and comments,
in particular Gerd Stumme for clarifying our FCA-related questions. We would also like to thank Johanna V\"olker for comments on a first
version as well as for proof-reading the final version of the paper. 
All errors are of course our own. We would also like
to acknowledge the reviewers of the Journal of Artificial Intelligence
Research as well as the ones of the earlier workshops (ATEM04, FGML04) and
conferences (LREC04, ECAI04) on which this work was presented for valuable
comments. Philipp Cimiano is currently supported by the Dot.Kom project
(http://www.dot-kom.org), sponsored by the EC as part of the framework V,
(grant IST-2001-34038) as well as by the SmartWeb project (http://smartweb.dfki.de), funded by the German Ministry of Education and Research.}

\newpage

\appendix

\section{Mutually Similar Terms}

\label{appendix}

\begin{table}[ht]
\begin{center}
{\tiny
\begin{tabular}{|l|l|l|l|}
\hline
Jaccard & Cosine & L1 norm & Jensen-Shannon divergence \\
\hline
(art exhibition,thing) & (agreement,contract) & (day,time) & (group,person) \\
(autumn,spring) & (animal,plant) & (golf course,promenade) &  \\
(balcony,menu) & (art exhibition,washing machine) & (group,person) &  \\
(ballroom,theatre) & (basilica,hair dryer) &  &  \\
(banquet,ship) & (boat,ship) &  &  \\
(bar,pub) & (cabaret,email) &  &  \\
(basilica,hair dryer) & (cheque,pension) &  &  \\
(beach,swimming pool) & (city,town) &  &  \\
(billiard,sauna) & (conference room,volleyball field) &  &  \\
(bus,car) & (golf course,promenade) &  &  \\
(caravan,tree) & (group,party) &  &  \\
(casino,date) & (inn,yacht) &  &  \\
(cinema,fitness studio) & (journey,meal) &  &  \\
(city,town) & (kiosk,tennis court) &  &  \\
(conference,seminar) & (law,view) &  &  \\
(conference room,volleyball field) & (library,museum) &  &  \\
(cure,washing machine) & (money,thing) &  &  \\
(day tour,place) & (motel,port) &  &  \\
(distance,radio) & (pilgrimage,whirlpool) &  &  \\
(exhibition,price list) & (sauna,swimming) &  &  \\
(ferry,telephone) &  &  &  \\
(gallery,shop) &  &  &  \\
(golf course,promenade) &  &  &  \\
(holiday,service) &  &  &  \\
(journey,terrace) &  &  &  \\
(kiosk,time interval) &  &  &  \\
(law,presentation) &  &  &  \\
(lounge,park) &  &  &  \\
(motel,port) &  &  &  \\
(nature reserve,parking lot) &  &  &  \\
(night,tourist) &  &  &  \\
(region,situation) &  &  &  \\
\hline
\end{tabular}
}
\end{center}
\caption{Mutually Similar Terms for the tourism domain}
\end{table}

\newpage

\begin{table}[H]
\begin{center}
{\tiny
\begin{tabular}{|l|l|l|l|}
\hline
Jaccard & Cosine & L1 norm & Jensen-Shannon divergence \\
\hline
(action,average) & (access,advantage) & (archives,futures) & (cent,point) \\
(activity,downturn) & (acquisition,merger) & (assurance,telephone number) & (government,person) \\
(addition,liquidity) & (action,measure) & (balancing,countenance) & (month,year) \\
(afternoon,key) & (administration costs,treasury stock) & (cent,point) &  \\
(agency,purchase) & (advice,assurance) & (creation,experience) &  \\
(agreement,push) & (allocation,length) & (government,person) &  \\
(alliance,project team) & (amount,total) & (loss,profit) &  \\
(allocation,success) & (analysis,component) & (month,year) &  \\
(analysis,negotiation) & (area,region) &  &  \\
(animal,basis) & (arrangement,regime) &  &  \\
(anomaly,regression) & (assembly,chamber) &  &  \\
(archives,futures) & (assessment,receipt) &  &  \\
(area,profitability) & (backer,gamble) &  &  \\
(argument,dismantling) & (balancing,matrix) &  &  \\
(arrangement,capital market) & (bank,company) &  &  \\
(arranger,update) & (barometer,market price) &  &  \\
(assembly,price decline) & (bid,offer) &  &  \\
(assurance,telephone number) & (bond,stock) &  &  \\
(automobile,oil) & (bonus share,cassette) &  &  \\
(backer,trade partner) & (boom,turnaround) &  &  \\
(balance sheet,person) & (bull market,tool) &  &  \\
(balancing,countenance) & (business deal,graph) &  &  \\
(behaviour,business partnership) & (buy,stop) &  &  \\
(bike,moment) & (capital stock,profit distribution) &  &  \\
(billing,grade) & (caravan,software company) &  &  \\
(board,spectrum) & (cent,point) &  &  \\
(board chairman,statement) & (change,increase) &  &  \\
(bonus,nationality) & (commission,committee) &  &  \\
(bonus share,cassette) & (company profile,intangible) &  &  \\
(branch office,size) & (complaint,request) &  &  \\
(broker,competition) & (controller,designer) &  &  \\
(budget,regulation) & (copper,share index) &  &  \\
(builder,devices) & (copy,push) &  &  \\
(building,vehicle) & (credit,loan) &  &  \\
(business volume,outlook) & (credit agreement,credit line) &  &  \\
(business year,quota) & (currency,dollar) &  &  \\
(capital,material costs) & (decision,plan) &  &  \\
(capital increase,stock split) & (detail,test) &  &  \\
(capital stock,profit distribution) & (diagram,support) &  &  \\
(caravan,seminar) & (dimension,surcharge) &  &  \\
(cent,point) & (discussion,negotiation) &  &  \\
(chance,hope) & (diversification,milestone) &  &  \\
(change,subsidiary) & (do,email) &  &  \\
(charge,suspicion) & (document,letter) &  &  \\
(chip,woman) & (effect,impact) &  &  \\
(circle,direction) & (equity fund,origin) &  &  \\
(clock,ratio) & (evaluation,examination) &  &  \\
(code,insurance company) & (example,hint) &  &  \\
(comment,foundation) & (first,meter) &  &  \\
(commission,expansion) & (forecast,stock market activity) &  &  \\
(communication,radio) & (function,profile) &  &  \\
(community,radius) & (gesture,input) &  &  \\
(company profile,intangible) & (guarantee,solution) &  &  \\
(compensation,participation) & (half,quarter) &  &  \\
(complaint,petition) & (increment,rearrangement) &  &  \\
(computer,cooperation) & (information,trading company) &  &  \\
(conference,height) & (insurance,percentage) &  &  \\
(confidentiality,dollar) & (interest rate,tariff) &  &  \\
(consultant,survey) & (man,woman) &  &  \\
(contact,hint) & (maximum,supervision) &  &  \\
(contract,copyright) & (meeting,talk) &  &  \\
(control,data center) & (merchant,perspective) & & \\
(conversation,output) & (month,week) &  &  \\
(copper,replacement) & (press conference,seminar) &  &  \\
(corporation,liabilities) & (price,rate) &  &  \\
(cost,equity capital) & (productivity,traffic) &  &  \\
(course,step) & (profit,volume) &  &  \\
(court,district court) & (share price,stock market) &  &  \\
(credit,disbursement) & (stock broker,theory) &  &  \\
(credit agreement,overview) &  &  &  \\
(currency,faith) &  &  &  \\
(curve,graph) &  &  &  \\
(decision,maximum) &  &  &  \\
(deficit,negative) &  &  &  \\
(diagram,support) &  &  &  \\
(difference,elimination) &  &  &  \\
\hline
\end{tabular}
}
\end{center}
\caption{Mutually Similar Terms for the finance domain}
\end{table}

\newpage

\begin{table}[H]
\begin{center}
{\tiny
\begin{tabular}{|l|l|l|l|}
\hline
Jaccard & Cosine & L1 norm & Jensen-Shannon divergence \\
\hline
(disability insurance,pension) &  &  &  \\
(discrimination,union) &  &  &  \\
(diversification,request) &  &  &  \\
(do,email) &  &  &  \\
(effect,help) &  &  &  \\
(employer,insurance) &  &  &  \\
(energy,test) &  &  &  \\
(equity fund,origin) &  &  &  \\
(evening,purpose) &  &  &  \\
(event,manager) &  &  &  \\
(examination,registration) &  &  &  \\
(example,source) &  &  &  \\
(exchange,volume) &  &  &  \\
(exchange risk,interest rate) &  &  &  \\
(experience,questionnaire) &  &  &  \\
(expertise,period) &  &  &  \\
(faculty,sales contract) &  &  &  \\
(fair,product) &  &  &  \\
(flop,type) &  \hspace{2cm} & \hspace{2cm} &  \\
(forecast,stock market activity) &  &  &  \\
(fusion,profit zone) &  &  &  \\
(gamble,thing) &  &  &  \\
(good,service) &  &  &  \\
(government bond,life insurance) &  &  &  \\
(happiness,question) &  &  &  \\
(hold,shareholder) &  &  &  \\
(hour,pay) &  &  &  \\
(house,model) &  &  &  \\
(idea,solution) &  &  &  \\
(impact,matter) &  &  &  \\
(improvement,situation) &  &  &  \\
(index,wholesale) &  &  &  \\
(information,trading company) &  &  &  \\
(initiation,middle) &  &  &  \\
(input,traffic) &  &  &  \\
(institute,organization) &  &  &  \\
(investment,productivity) &  &  &  \\
(knowledge,tradition) &  &  &  \\
(label,title) &  &  &  \\
(letter,reception) &  &  &  \\
(level,video) & & & \\
(license,reward) &  &  &  \\
(loan,project) &  &  &  \\
(location,process) &  &  &  \\
(loss,profit) &  &  &  \\
(man,trainee) & & & \\
(margin,software company) &  &  &  \\
(market,warranty) &  &  &  \\
(market access,name) &  &  &  \\
(matrix,newspaper) &  &  &  \\
(meeting,oscillation) &  &  &  \\
(meter,share) &  &  &  \\
(method,technology) &  &  &  \\
(milestone,state) &  &  &  \\
(month,year) &  &  &  \\
(mouse,option) &  &  &  \\
(multiplication,transfer) &  &  &  \\
(noon,press conference) &  &  &  \\
(occasion,talk) &  &  &  \\
(opinion,rivalry) &  &  &  \\
(personnel,resource) &  &  &  \\
(picture,surcharge) &  &  &  \\
(plane,tool) &  &  &  \\
(police,punishment) &  &  &  \\
(profession,writer) &  &  &  \\
(property,qualification) &  &  &  \\
(provision,revenue) &  &  &  \\
(requirement,rule) &  &  &  \\
(risk,trust) &  &  &  \\
(sales revenue,validity) &  &  &  \\
(savings bank,time) &  &  &  \\
(segment,series) &  &  &  \\
(show,team) &  &  &  \\
(speech,winter) &  &  &  \\
(stock broker,theory) &  &  &  \\
(supplier,train) &  &  &  \\
(tariff,treasury stock) &  &  &  \\
(weekend,wisdom) &  &  &  \\
\hline
\end{tabular}
}
\end{center}
\caption{Mutually Similar Terms for the finance domain (Cont'd)}
\end{table}

\newpage

\bibliographystyle{theapa}
\bibliography{paper}

\end{document}
