HQE: A hybrid method for query expansion
Expert Systems with Applications 36 (2009) 7985–7991
Contents lists available at ScienceDirect
Expert Systems with Applications
j o u r n a l h o m e p a g e : w w w . e l s e v i e r . c o m / l o c a t e / e s w a
HQE: A hybrid method for query expansion
Lixin Han a,b,c,*, Guihai Chen b
a College of Computer and Information Engineering, Hohai University, Nanjing, China
b State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing, China
c Department of Mathematics, Nanjing University, Nanjing, China
a r t i c l e i n f o
Keywords:
Information retrieval
Collaborative filtering
Data mining
Optimization
0957-4174/$ - see front matter � 2008 Elsevier Ltd. A
doi:10.1016/j.eswa.2008.10.060
* Corresponding author. Address: College of Com
neering, Hohai University, Nanjing, Jiangsu 210098, C
E-mail address: lixinhan2002@hotmail.com (L. Ha
a b s t r a c t
Query expansion methods have been extensively studied in information retrieval. This paper proposes a
query expansion method. The HQE method employs a combination of ontology-based collaborative filter-
ing and neural networks to improve query expansion. In the HQE method, ontology-based collaborative
filtering is used to analyze semantic relationships in order to find the similar users, and the radial basis
function (RBF) networks are used to acquire the most relevant web documents and their corresponding
terms from these similar users’ queries. The method can improve the precision and only requires users to
provide less query information at the beginning than traditional collaborative filtering methods.
� 2008 Elsevier Ltd. All rights reserved.
1. Introduction
Query expansion methods have a long history in traditional
information retrieval. Its study may date back to, at least, the stud-
ies of Sparck Jones and Needham (1968), Sparck Jones (1971) in
which the collection is analyzed to provide a similarity thesaurus
of word relationships. A number of query expansion methods have
been proposed. Generally the existing query expansion methods
can be classified into the two classes of global analysis and local
analysis (Xu & Croft, 2000).
(1) Global analysis is one of the first techniques to produce con-
sistent and effective improvements through query expansion.
Global analysis analyzes the entire document corpus to discover
word relationships. A known global technique is Latent Seman-
tic Indexing (LSI) (Xu & Croft, 2000). Latent Semantic Indexing
(LSI) (Deerwester, Dumais, Landauer, Furnas, & Harshman,
1990), which is a way to represent data, has explored the use
of semantics for information retrieval and reduces the retrieval
and ranking problem to one of significantly lower dimensions.
Other global techniques are term clustering, similarity thesauri
and Phrasefinder (Xu & Croft, 2000). Generally, global analysis
needs to compute term correlation only once at system devel-
opment time. However, term ambiguity may introduce irrele-
vant correlated terms.
(2) In contrast to global analysis, local feedback methods (Sal-
ton & Buckley, 1990) are generally more effective. However,
ll rights reserved.
puter and Information Engi-
hina.
n).
these local feedback methods are not relatively robust. Local
analysis uses only top-ranked retrieved documents for further
query expansion. Local analysis needs to compute term correla-
tion for every query at run time.
The above query expansion methods require the systems to
analyze a large amount of information that the users provide. In
addition, it is too difficult to ensure the completeness and correct-
ness of the existing documents. Collaborative filtering goes some
way to addressing these issues. Collaborative filtering (CF) meth-
ods (Resnik, Iacovou, Suchak, Bergstrom, & Riedl, 1994) work by
assessing similarities among users, then recommending given
users more useful documents that like-minded users accessed pre-
viously. Therefore users’ query expansion information can be ac-
quired from other similar users. However, if the users provide
little information at the beginning, collaborative filtering cannot
discover any correlations between users and their similar users
and further collaborative filtering cannot find their similar users.
If external ontological sources including users’ personal informa-
tion can be employed, some similar users may be found. Initial
knowledge about all users and their interests can be provided from
these external ontologies. Accordingly, based on the idea above, we
propose a novel query expansion method called HQE (hybrid query
expansion). The HQE method employs collaborative filtering com-
bined with the Semantic Web and neural networks to improve
query expansion. The HQE method derives ontology-based user
similarity and then finds the similar users, and further constructs
the training data of relevant documents retrieved by similar users,
at last predict document relevancy and discover the most relevant
web documents and their corresponding terms.
The HQE method is more convenient for users to expand new
query than the above traditional query expansion methods. Be-
mailto:lixinhan2002@hotmail.com
http://www.sciencedirect.com/science/journal/09574174
http://www.elsevier.com/locate/eswa
7986 L. Han, G. Chen / Expert Systems with Applications 36 (2009) 7985–7991
cause of using ontology-based collaborative filtering, the HQE
method only requires users to enter some keywords and these
users do not require provide a large amount of information that
is acquired by analyzing these retrieved documents at the
beginning.
2. Related work
Various methods of query expansion have been explored in pre-
vious work. Xu and Croft (2000) propose a local context analysis
method, which combines both local analysis and global analysis.
Expansion terms employed are not based on frequencies in the
top-ranked documents, similarly to local feedback, but on co-
occurrences with the query terms. Therefore, the local context
analysis method can overcome the difficulty of local analysis to
some extent. The method is based on the hypothesis that a fre-
quent term from the top-ranked relevant documents will tend to
co-occurrence with all query terms within the top-ranked docu-
ments. However, the hypothesis is not always true. Cui, Wen,
Nie, and Ma (2002) propose a new method for query expansion
based on query logs. In the method, probabilistic correlations be-
tween query terms and document terms are extracted by analyzing
query logs. These correlations are then used to select high-quality
expansion terms for new queries. Kamps (2004) explores a new
feedback technique that re-ranks the set of initially retrieved doc-
uments based on the controlled vocabulary terms assigned to the
documents. The approach uses the combination of global and local
feedback techniques. On the one hand, the approach uses a global
feedback technique to analyze the usage of controlled vocabulary
in the collections. The rationale for this is that the approach does
not want to rely on the availability of special dictionaries or the-
sauri. The approach is similar to latent semantic indexing. On the
other hand, the approach uses a local feedback technique for
re-ranking the set of initially retrieved documents. Han and Chen
(2006) use ontology information to extend the keywords and then
employ an algorithm for mining association rules to find the terms
that are closely related to these keywords and their synonyms.
These keywords and their synonyms are restricted by these rele-
vant words to reduce ambiguity and improve precision. Pôssas,
Ziviani, Wagner, and Ribeiro-Neto (2002) propose a model referred
to as set-based model for computing index term weights and for
ranking documents. The components in set-based model are no
longer terms, but termsets. The model computes term weights
using association rules technique. El-Kahlout and Oflazer (2004)
present the design and implementation of a system called Meaning
to Word (MTW) to find the appropriate Turkish words that closely
match the definition entered by the user. The approach for extract-
ing words based on meanings checks the similarity between the
user’s definition and each entry of the Turkish database that does
not consider the semantics or the context.
Various methods of collaborative filtering have been proposed
in previous work. Sarwar, Karypis, Konstan, and Riedl (2001) pro-
pose an effective item-based approach to dealing with both the
scalability and sparsity problems in the context of collaborative fil-
tering. In this approach, the user-item representation matrix is
analyzed to identify the relations between items, rather than rela-
tions between users, and then to use these relations to indirectly
compute recommendations for users. Because the relations be-
tween items are relatively static, item-based algorithms may have
less online computation than the user-based algorithms. Huang,
Chen, and Zeng (2004) present an effective collaborative filtering
approach to exploring relational user and item similarities for deal-
ing with the sparsity problem. They apply associative retrieval
techniques and three related spreading activation algorithms
including a constrained spreading activation algorithm based on
the Leaky Capacitor Model (LCM), a branch and bound serial sym-
bolic search algorithm (BNB), and a Hopfield net parallel relaxation
search algorithm (Hopfield) to explicitly generate associations
among consumers and products in collaborative filtering. Rashid,
Karypis, and Riedl (2005) present a measure of influence that is
algorithm-independent, in order to ensure that it can be applied
to any ratings-based recommender system. Sarwar, Karypis, Kon-
stan, and Reidl (2000) present and experimentally evaluate an ap-
proach to applying the combination of the classical association rule
algorithms, nearest-neighbor collaborative filtering algorithms,
and algorithms based on dimensionality reduction to CF-based rec-
ommender systems. Hofmann (2004) presents a model-based ap-
proach to collaborative filtering. The approach introduces a
statistical latent class model to discover user communities and
build user profiles. In addition, the approach employs overlapping
user communities to decompose user preferences. Lemire (2005)
presents a scale and translation invariant as being a desirable prop-
erty for collaborative filtering. The paper takes into consideration
such criteria as the amplitude and the mean, and the number of
ratings to normalize users, in order to improve accuracy.
Here, we only have space to contrast our work with the most di-
rectly related to Middleton, Shadbolt, and De Roure (2004); Hust
(2004); Robin and Ramalho (2003); Ciaramita, Hofmann, and John-
son (2003) Akrivas, Wallace, Andreou, Stamou, and Kollias (2002).
Middleton et al. (2004) present a general ontology-based recom-
mendation system approach. Their two experimental systems,
Quickstep and Foxtrot, are built. Quickstep improves user profiles’
accuracy via inference and Quickstep is integrated with an external
ontology built from a publication database and personnel database
in order to bootstrap a recommender system for easing the cold-
start problem. Foxtrot enhances Quickstep by visualizing user pro-
files in order to acquire direct user profiles’ feedback. In contrast to
Middleton et al. (2004), the HQE method applies the combination
of using an ontology and collaborative filtering to query expansion
instead of user profiling within recommender systems. In addition,
the HQE method presents some algorithms to improve query
expansion. Hust (2004) introduces collaborative filtering tech-
niques to query expansion in a restricted collaborative information
retrieval environment. The information retrieval system acquires
the relevant documents from previous search processes carried
out by one or several users to improve retrieval performance for
the current query. The method does not acquire users’ knowledge
from ontologies. In contrast to Hust (2004), HQE combines Seman-
tic Web with collaborative filtering to perform the analysis of
semantic relationships for finding the similar users, and acquires
some relevant web documents from these similar users’ queries
using the Radial Basis Function (RBF) networks. Various uses of
ontology as a linguistic knowledge resource to improve IR effec-
tiveness have been tried in previous work. Robin and Ramalho
(2003) argue search engines access to wide-coverage linguistic
ontologies such as WordNet, can improve web search effectiveness
in retrieving a set of purely textual documents with no semantic
annotation. They present an experiment that empirically measured
the impact on retrieval effectiveness of automatically expanding
the query keywords with their synonyms or immediately neigh-
boring concepts. In the experiment, the individual impact of such
expansion under environment typical web searches is evaluated.
Ciaramita et al. (2003) introduce a hierarchical learning architec-
ture based on the multiclass perceptron for lexical semantic classi-
fication problems that integrates task-specific and general
information. They propose to generate additional training data by
extracting training sentences from a dictionary ontology-WordNet.
Akrivas et al. (2002) propose a query expansion method, which
takes into account the query context based on the Inclusion rela-
tion. The query context is defined as a fuzzy set of semantic enti-
ties. They integrate the method with the user’s profile. The user’s
L. Han, G. Chen / Expert Systems with Applications 36 (2009) 7985–7991 7987
preferences are used to change this context to provide the capabil-
ity for query personalization. In contrast to Robin and Ramalho
(2003), Ciaramita et al. (2003), and Akrivas et al. (2002), the HQE
method uses ontology information to find the similar users, ac-
quires the relevant web documents from these similar users’ que-
ries, and the relevant web documents are used by the RBF
networks in order to expand new query.
In contrast to the above work, the HQE method employs ontol-
ogy-based collaborative filtering combined with neural networks
to improve query expansion. In addition, the HQE method presents
some algorithms to improve query expansion. In the HQE method,
collaborative filtering is used to analyze semantic relationships
that are acquired from the constructed ontologies in order to find
the similar users, and the radial basis function (RBF) networks
are used to acquire the most relevant web documents and their
corresponding terms from these similar users’ queries.
3. The HQE method of improving query expansion
In this section, we propose a new query expansion method
called the HQE method. The HQE method consists mainly of the
CCIO (combines complete-link clustering with inference for con-
structing of ontologies) algorithm, the BBFU (branch and bound
for finding similar users) algorithm and the RENQ (RBF to expand
new query) algorithm. The CCIO algorithm is described in Section
3.1, The BBFU algorithm is described in Section 3.2, and the RENQ
algorithm is described in Section 3.3.
The HQE Method can be described as the following steps:
{the CCIO algorithm is used to construct ontologies;
based on the above ontologies, the BBFU algorithm is used to
perform the analysis of semantic relationships for finding the
similar users;
some relevant web documents are acquired from the above
similar users’ queries;
the RENQ algorithm is used to rank these web documents and
discover the most relevant web documents and their corre-
sponding terms;
}
3.1. The CCIO algorithm for constructing ontologies
An ontology is an explicit specification of a conceptualization
(Gruber, 1993). Form a human standpoint, an ontology is a concep-
tualisation of a domain; Form a machine standpoint, it consists of
entities, attributes, relationships, and axioms (Guarino & Giaretta,
1995).
The ontologies are constructed to identify the association rela-
tionships between concepts that can be extracted by users’ per-
sonal information, and to be shared among all users. In addition,
the existing relationships in the knowledge base provide a scope
for discovering new relationships. For example, if such entities as
teaching, institution, staff, project, student, and paper are con-
structed, we can expect to find all users’ university, department,
research interests, research projects, publications, course, graduate
student etc. Accordingly, based on the idea above, we propose the
CCIO algorithm for automatically constructing ontologies. The
CCIO algorithm can exploit the desirable properties of both com-
plete-link clustering algorithms and inference mechanism to con-
struct the hierarchically structured ontologies, that is, based on
the existing association entities acquired from the Complete-link
Clustering algorithm, new meaningful relationships that cannot di-
rectly observed can be inferred through Jena2’s inference
mechanism.
Formula (1) denotes the similarity between two entities repre-
sented as sets A and B.
SðA; BÞ¼ jA \ Bj=jA [ Bj ð1Þ
where ax is an interest of user x, by is an interest of user y, jj is the
cardinality of a set, and A = {ua1, . . . , uan} and B = {ub1, . . . , ubn}, where
ua1, . . . , uan are the terms of a
x, and ub1, . . ., ubn are the terms of b
y.
The larger S(A, B) is, the larger the similarity between A and B is.
The CCIO algorithm can be described as follows:
{ i = 0;
using formula (1), calculate the proximity matrix Di contain-
ing the distance between ax and by; treat each interest as a
cluster, that is Dpq = dpq; // Dpq is the distance between each
pair of clusters, dpq is the distance between each pair of terms
while all terms are not in one cluster
{ i = i + 1;
find the most similar pair of Dpq in the proximity matrix and
merge these two clusters Cp and Cq into one cluster Cr, that is
Cr = {Cp, Cq}; //Cr, Cp, Cq is cluster
using formula (1) and the formula Drk = max{Dpk, Dqk}, calcu-
late the proximity matrix Di to perform a merge operation;
a class hierarchy can be constructed;
generate some rules from the class hierarchy;
store these rules into the knowledge base;
the widely used Jena2’s inference mechanism (Wilkinson,
Sayers, Kuno, & Reynolds, 2003 & Carroll et al., 2003) is used
to infer semantic associations from the existing rules within
the knowledge base in order to discover more meaningful
association entities;
a class hierarchy can be reconstructed;
}
}
In contrast to the widely used complete-link clustering algo-
rithm (Jain, Murty, & Flynn, 1999), the CCIO algorithm provides
the inference mechanism to find more useful association entities
that are not directly observed in the users’ behaviour.
3.2. The BBFU algorithm for finding the similar users
Branch and bound algorithms are methods for global optimiza-
tion in non-convex problems (Lawler & Wood, 1966 & Moore,
1991). They are non-heuristic, in the sense that they maintain a
provable upper and lower bound on the globally optimal objective
value; they terminate with a guarantee proving that the indeed
suboptimal point found is suboptimal. In the worst case they re-
quire effort that grows exponentially with problem size, but in
some cases we are lucky, and the methods converge with much
less effort. The methods are useful to solve small instances of hard
problems.
We propose an efficient branch and bound search algorithm
BBFU that introduces a branch and bound method to find the sim-
ilar users. The BBFU algorithm employs optimization techniques to
evaluate the nodes close enough to the specified node. Specifically,
the BBFU algorithm examines the connectivity of entities in ontol-
ogies, traverses the semantic relationships between entities before
a given threshold is reached, according to their semantic distance,
identifies a set of close entities, and finds the similar users.
In the following description, k stands for the iteration index.
Listk denotes the list of nodes. Uk denotes the upper bound, at the
end of k iterations. x* denotes the optimal solution. The bounding
function F(x) = max(P). The Pearson correlation P ¼
Pn
i¼1
ðxi��XÞðyi��YÞ
ðn�1ÞSX SY
,
where X and Y are two entities vectors, �X and �Y are their means,
respectively, SX and SY are their standard deviations, respectively.
7988 L. Han, G. Chen / Expert Systems with Applications 36 (2009) 7985–7991
The Pearson correlation is often used to the similar entities whose
features are known.
The BBFU algorithm can be described as the following steps:
{ given ontologies and a user;
x* = Ø;
k = 0;
List0 = {root node};
U0 = +1;
do {maximizing choose the class node x with bounding func-
tion F(x), where x 2 Listk;
Listk+1 = Listk � {x};
if f(x) P Uk
then prune the node;
else {x* = x;
Uk = f(x);
split x into x1 and x2;
Listk+1 = Listk [ {x1, x2};
}
k = k + 1;
}
while Listk – Ø and Uk � f(x) > e
determine optimal solution x*, that is find the most similar
user;
a set of the similar users are identified from the most similar
user’ subclass and superclass in ontologies;
}
3.3. The RENQ algorithm for expanding new query
The RENQ algorithm introduces RBF networks to rank web doc-
uments and discover the most relevant web documents and their
corresponding terms. In the RBF networks, the relevant web pages
are obtained from a set of the similar users. The algorithm is based
on the hypothesis that two web pages are more similar in content
if there are more common keywords in their web pages. The algo-
rithm begins by training known relevant and irrelevant web docu-
ments. Relevant web documents are obtained from a set of the
similar users and irrelevant web documents are obtained from a
set of the dissimilar users. During training, the connection weights
of the RBF networks are initialized with some random values. The
training samples in the training set are then presented to the RBF
networks in random order and the connection weights are ad-
justed using the SC method. This process is repeated until the
least-squares error between the predicted outputs from the net-
work and the observed output is small or the predefined maximum
iterative number is achieved. After network training has finished,
the neural network is built using keywords from these web pages.
Each keyword maps into a 0 or 1, so the length of the input vector
equals the number of the keywords chosen. The neural network
can assign all the web pages to a relevancy value that is a fraction
between 1 and 0. These relevant values may be used to rank these
relevant web pages.
The RENQ algorithm can be described as follows:
{the training set is obtained from a set of the similar users and
the dissimilar users;
cstep = 0; // cstep is the current iterative step;
While (the least-squares error > tnumber) and step < maxstep
// tnumber is a predefined tolerance number, maxstep is a iter-
ative maximum number;
{using the following the SC method, the training samples are
trained;
step = step + 1;
}
using the trained neural networks, rank a set of web docu-
ments acquired from these existing similar users’ queries,
and discover the most relevant web documents and their cor-
responding terms;
}
In contrast to the widely used RBF Networks (Yang & Zheng,
2003 & Ibnkahla, 2000), a SC method has been proposed to update
RBF networks.
3.3.1. The SC method for updating RBF networks
The SC (Combine SACU with CTSB) method has been proposed
to update RBF networks. The method is composed of the SACU
algorithm for centers update and the CTSB algorithm for the output
weights update.
For clarity of presentation, the basic concepts about RBF net-
works are briefly recalled that are relevant to this paper.
The RBF network (Ibnkahla, 2000) is a two-layer feedforward
network, whose input-layer activation function can be described
as follows: f(x) = /(kxk), where / is a radial basis function. k � k is
the Euclidean norm on Rn. In contrast to MLNN (multi-layer neural
network), the activation function is a compact one, instead of the
usual sigmoid function. The activation function can be described
as follows: /ðTÞ¼ 1ffiffiffiffi
2p
p
d
expð�TÞ, T ¼ ðkx�ckkÞ
2
2d2
. The outputs of the first
layer neurons are described as follows: x1k ¼ 1ffiffiffiffi2pp d exp �
kx�ckk
2
2d2
� �
,
where x is the input vector and c is the weight associated to neuron
k. The network outputs are described as follows:
yj ¼
PN1
k¼1 wkj
1ffiffiffiffi
2p
p
d
exp �kx�ckk
2
2d2
� �
, where wkj is the weights associ-
ated with the output layer.
3.3.1.1. The SACU algorithm for centers update. Simulated annealing
is a generalization of a Monte Carlo method for examining the
equations of state and frozen states of n-body systems (Metropolis,
Rosenbluth, Rosenbluth, Teller, & Teller, 1953). The concept is
based on the manner in which liquids freeze or metals recrystalize
in the process of annealing. By analogy the generalization of this
Monte Carlo approach to combinatorial problems is straight for-
ward (Cerny, 1985; Kirpatrick, Gellat, & Vecchi, 1983). The major
difficulty in implementation of the algorithm is that there is no
obvious analogy for the temperature T with respect to a free
parameter in the combinatorial problem. Furthermore, avoidance
of entrainment in local minima is dependent on the ‘‘annealing
schedule”, the choice of initial temperature, how much iterations
are performed at each temperature, and how much the tempera-
ture is decremented at each step as cooling proceeds (Gray et al.,
1997).
We propose the SACU (Simulated Annealing to Centers Update)
algorithm to update centers. The SACU algorithm introduces simu-
lated annealing for centers update. The simulated annealing algo-
rithm can be viewed as globally optimizing an objective function.
The SACU algorithm can ensure to break away current local opti-
mal solution and to reduce the computing workload.
The SACU algorithm is based on the following solution form:
1. The solution space is a training set;
2. The objective function is f ¼ min
Pk
r¼1 Sr ¼ min
Pk
r¼1
Pnr
i¼1
ðxri � �xrÞ
0ðxri � �xrÞ, where k is the number of clusters, nr is the
number of training samples in cluster r, Sr is the squared error,
xri is training sample i in cluster r, and x�r is the centroid of clus-
ter r;
3. A new solution is produced by randomly choosing another
training sample from neighboring region N(x);
L. Han, G. Chen / Expert Systems with Applications 36 (2009) 7985–7991 7989
4. The objective function difference is Df = f (new training sam-
ple)-f (local optimal solution);
5. The accept criterion is P = 1 for Df > 0 or P = exp(�Df/t) for
Df 6 0.
The SACU algorithm can be described below:
{given a set of the training samples, initial solution x0, initial
optimal objective function value f*, initial temperature t0, initial
step q0, monotone increment function I(x);
x* = x0; // initialize optimal solution x*
q = q0; // initialize step q
t = t0; // initialize temperature t, t0 = 100
i = 1; // initialization
at = 1; // initialization
while jRi � Cj > e
// e is a given enough small positive number, where
e = 2 � 10�3. C is an threshold, where C = 0.75
{ Ri�1 = at/as; // at is the acceptable times of new solution, as
is iterative steps number, Ri�1 is acceptable rate
at = at + 1;
as = 0; // initialization
while J < >U//U is the upper limit of step length
{ as = as + 1;
while x R N(x)//N(x) is neighboring region
{step length is q and the BFGS optimizer in the quasi-
Newton method is used to compute local optimal
solution;
}
xi is produced by randomly choosing another training sam-
ple from neighboring region N(x) and objective function dif-
ference Df = f(xi) � f(x) is computed;
if Df 6 0 or exp(�Df/t) > random(0, 1)
then {x = xi;
if f < f*
then {x = x*;
f = f*;
}
if at is equal to the given acceptable times
then break;
}
q = I(Ri)�q;
// adjustment function I(x) is monofonic increasing function,
where I(x) = (x-0.5)2 + 1
}
if f < f*
then {x = x*;
f = f*;
}
Ri = at/as;
if i > 2
then // compute self-adjusting temperature
{if Ri�1 < C and Ri < C
then t = t+TC;// TC is a given constant
if Ri�1 P C and Ri P C
then t = t-TC;
if Ri�1 6 C and Ri P C
thent = t-TC/2;
if Ri�1 > C and Ri < C
then t = t + TC/2;
}
i = i + 1;
}
}
In contrast to the widely used simulated annealing algorithm
(Jonhson, Aragon, Mcgeoch, & Schevon, 1991; Kirpatrick et al.,
1983), there are three features in the SACU algorithm. Firstly, the
SACU algorithm can self-adaptingly adjust temperature. Therefore
it is regarded as time after time optional process. On the one hand,
the Boltzmann factor exp(�Df/t) increases with t. This is useful to
break away from the current local optimal solution and to increase
step length in order to look for a better new solution. On the other
hand, when acceptable rate meets the given condition, the pro-
gram can end so as to reduce the computing workload. Secondly,
local optimization techniques instead of choosing randomly a
new solution are employed in order to compute a local optimal
solution. Thirdly, the local optimal solution is recorded during
annealing process, in order to protect the current optimal solution
from being thrown away.
3.3.1.2. The CTSB algorithm for updating the output layer weights. We
propose the CTSB (combine TS with BFGS) algorithm to update the
output layer weights. The CTSB algorithm is a hybrid algorithm of
exploiting the desirable properties of both the widely used globally
optimal algorithms Tabu Search (Glover, 1986; Gray et al., 1997)
and locally optimal algorithms BFGS (Xie, Han, & Lin, 1997).
The CTSB algorithm can be described below:
{xj is normalized, that is, x0j ¼ ajxj þ bj, where aj ¼
2
xjmax�xjmin
,
bj ¼ 1 � ajxjmax, and xj 2 (xjmin, xjmax);
count = 1;
while count < maxno // maxno is the iterative maximum number
{DWijk(n � 1) = Wijk(n) � Wijk(n � 1), n = 0, 1, . . .;// Wijk(n) is a
weight vector
DW ijkðnÞ¼�l
oEðW ijkðnÞÞ
oW ijkðnÞ
þ mDW ijkðn � 1Þ; n ¼ 0; 1; . . . ; // l is the
learning rate, m is a law of inertia coefficient
if
Pk2�1
n¼0 ðEðW ijkðn þ 1ÞÞ� EðW ijkðnÞÞÞ > kEðW ijkðn1ÞÞ// move a
local optimal solution to a better local optimal solution, where
k is a given appropriate small positive number between 0.15 and
0.25, k2 is a current value, and Wijk(n1) is a initialized weight
vector, the squared error energy function E(n) is the error power
between the network output vector at time n and the desired
output
then the BFGS algorithm is used to determine a local optimal
solution and the weights are updated;
if
DEðW ijkðnÞÞj j
EðW ijkðnÞÞ
< e and EðW ijkðnÞÞ > L // indulge in a local optimal
solution, where L is a given appropriate large number, and e is
a given enough small positive number
then the Tabu Search algorithm is used to break away current
local optimal solution and the weights is updated;
count = count + 1;
}
}
In contrast to the supervised learning rules BP (Ibnkahla, 2000;
Yang & Zheng, 2003) for the output weights update in RBF net-
works, the SACU algorithm exploit the desirable properties of both
Tabu Search and BFGS. Therefore the SACU algorithm is easy to find
global optimal solution and to bring a less the squared error en-
ergy. In contrast to the BP algorithm (Ibnkahla, 2000), DWijk(n) in
the SACU algorithm consider not only learning rate but also a
law of inertia coefficient in order to have faster convergence at iter-
ative steps and avoid fluctuating fiercely around convergence
point.
4. Experimental results and discussion
In this section, we present the experiments results of the HQE
method. The HQE method employs OWL (Dean & Schreiber,
0
0.2
0.4
0.6
0.8
1
M
ea
n
a
v
er
ag
e
p
re
ci
si
o
n
All Tops
HQE method Hust's method keywords method
Fig. 2. MAP f or all tops.
7990 L. Han, G. Chen / Expert Systems with Applications 36 (2009) 7985–7991
2004; McGuinness & Harmelen, 2004) to describe resources and
their inter-relations. Jena2’s inference mechanism is used to infer
semantic associations from the existing rules. We select 251 Web
pages to acquire ontology information. These selected Web pages
are related to personal information. Some entities are extracted
from these Web pages and stored in the OWL files. Jena2’s infer-
ence mechanism allows additional facts to be inferred from these
entities. Inference mechanism uses forward chaining, backward
chaining and a hybrid execution model provided by the Jena2 rea-
soner. The connectivity of entities in ontologies is examined, and
the semantic relationships between entities are traversed before
a given threshold is reached, and according to their semantic dis-
tance, a set of close entities are identified, and eighteen similar
users are found. Some relevant web documents are acquired from
these similar users’ research interests. After training these relevant
web documents, a set of term for query expansion are discovered.
We submit the user’s queries that are related to our research to the
existing third party search engine Google. The search engine re-
sults are the ten top-ranked retrieved documents. These queries
belong to such topics as information retrieval, data mining, pattern
recognition, semantic web, optimization and network computing.
The query results are divided into relevant and irrelevant docu-
ments. The ranked results are analyzed to check whether the rele-
vant results are contained in the answer, in order to meet the need
of a quantitative measure. We adopt mean average precision
(MAP) to evaluate the HQE retrieval performance. Mean average
precision, which is a standard IR evaluation measure, is used to
find the mean of the average precisions over a set of queries, where
average precision is the mean of the precision scores after each rel-
evant document is retrieved. Hust’s method is the most relevant to
our work. We compare the results of the HQE method with the re-
sults of Hust’s method (Hust, 2004) and entering a set of keywords
without using the HQE method for six topics. Six topics are closely
related to these similar users. Six topics are described below: topic
1 is information retrieval, topic 2 is data mining, topic 3 is pattern
recognition, topic 4 is semantic web, topic 5 is optimization and to-
pic 6 is network computing. Mean average precision of these meth-
ods for six topics are shown, respectively, in Fig. 1. The experiment
result in Fig. 1 shows that the HQE method can perform better in
topic 1, topic 2, topic 4, and topic 5. The experiment result shows
that if a set of term for query is scientific terms without ambiguity,
these methods led to similar higher mean average precision, and if
a set of term for query suffer the usual problem of synonymy and
ambiguity, that HQE can perform better. Hust’s method does not
take into consideration acquiring relevant knowledge from ontolo-
gies. Hust’s method is a method of introducing collaborative filter-
ing techniques to query expansion. The method can help to
improve query expansion. However, if similar users provide too
many terms for a query and this causes too many expansion terms,
the method can not improve query expansion. In contrast to Hust’s
0
0.2
0.4
0.6
0.8
1
M
ea
n
av
er
ag
e
pr
ec
is
io
n
top1 top2 top3 top4 top5 top6
Every top
HQE method Hust's method keywords method
Fig. 1. MAP f or every top.
method, the HQE method can acquire the most relevant terms from
these similar users’ queries and reduce the number of expansion
terms. For example, we look for ranking algorithm in information
retrieval. When keyword ranking is entered, such useless informa-
tion as best college rankings and best graduate schools rankings
could be found from query results. Thus, its average precision is
only 0.297. After Hust’s method is used, its average precision is
0.757. After the HQE method is used, its average precision is
0.953. It is because ranking algorithm can be acquired from ontol-
ogy information. Some similar users in ontology user do research
in information retrieval area. Thus, ranking may be regarded as a
kind of ranking algorithm in ontology information retrieval. Mean
average precision of these methods for all tops are shown, respec-
tively, in Fig. 2. The experiment result in Fig. 2 shows that HQE can
perform better.
5. Conclusion
Nowadays, the amount of information in the Internet is increas-
ing dramatically. Facilitating users to get useful information has
become more and more important to information retrieval sys-
tems. The traditional query expansion methods require users to
analyze a large amount of information. In addition, it is too difficult
to ensure the completeness and correctness of the existing docu-
ments. To solve these problems, in this paper, we propose a query
expansion method called HQE. In the HQE method, the CCIO algo-
rithm is proposed to construct ontologies. The BBFU algorithm is
proposed to analyze semantic relationships for finding the similar
users. The RENQ algorithm is proposed to acquire the most rele-
vant web documents and their corresponding terms from these
similar users’ queries. The method can improve the precision and
only requires users to provide little query information at the begin-
ning than traditional collaborative filtering methods.
Acknowledgements
The authors thank Professor Linping Sun for technical help. This
work is supported by the National Natural Science Foundation of
China under Grants 60673186, 60571048 and 60736015, the na-
tional 863 program under Grants 2007AA01Z178, and the State
Key Laboratory Foundation of Novel Software Technology at Nan-
jing University under Grant A200604. The work is partly supported
by China NSF grants (60573131, 60673154, 60721002, 60825205),
Jiangsu High-Tech Research Project of China (BG2007039), and
China 973 project (2006CB303000).
References
Akrivas, G., Wallace, M., Andreou, G., Stamou, G., & Kollias, S. (2002). Context-
sensitive semantic query expansion. In 2002 IEEE international conference on
artificial intelligence systems (ICAIS’02).
Carroll, J., Dickinson, I., Dollin, C., Reynolds, D., Seaborne, A., & Wilkinson, K. (2003).
The Jena semantic Web platform: Architecture and design. HP Laboratories
Technical Report HPL-2003-146.
L. Han, G. Chen / Expert Systems with Applications 36 (2009) 7985–7991 7991
Cerny, V. (1985). Thermodynamical approach to the traveling salesman problem:
An efficient simulation algorithm. Journal of Optimization Theory and
Applications, 45(1), 41–51.
Ciaramita, M., Hofmann, T., Johnson, M., 2003. Hierarchical semantic classification:
Word sense disambiguation with world knowledge. In IJCAI 2003 (pp. 817–822).
Cui, H., Wen, J.-R., Nie, J.-Y., & Ma, W.-Y.(2002). Probabilistic query expansion using
query logs www.2002. (pp. 325–332).
Dean, M., & Schreiber, G. (2004). OWL Web ontology language reference. W3C
recommendation 10 February 2004. .
Deerwester, S. C., Dumais, S. T., Landauer, T. K., Furnas, G. W., & Harshman, R. A.
(1990). Indexing by latent semantic analysis. JASIS, 41(6), 391–407.
El-Kahlout, I. D. & Oflazer, K. (2004). Use of Wordnet for retrieving words from their
meanings. In Proceedings of the global Wordnet conference (GWC2004), (pp. 118–
123).
Glover, F. (1986). Future paths for integer programming and links to artificial
intelligence. Computers and Operations Research, 13(5), 533–549.
Gray, P., Hart, W., Painton, L., Phillips, C., Trahan, M., & Wagner, J. (1997). A survey of
global optimization methods. .
Gruber, T. R. (1993). A translation approach to portable ontology specifications.
Knowledge Acquisition, 5(2), 199–220.
Guarino, N., & Giaretta, P. (1995). Ontologies and knowledge bases: Towards a
terminological clarification. In N. Mars (Ed.), Towards very large knowledge bases:
Knowledge building and knowledge sharing (pp. 25–32). IOS Press.
Han, L., & Chen, G. (2006). The HWS hybrid web search. Information and Software
Technology, 48(8), 687–695.
Hofmann, T. (2004). Latent semantic models for collaborative filtering. ACM
Transactions on Information Systems (TOIS), 22(1), 89–115.
Huang, Z., Chen, H., & Zeng, D. (2004). Applying associative retrieval techniques to
alleviate the sparsity problem in collaborative filtering. ACM Transactions on
Information Systems, 22(1), 116–142.
Hust, A. (2004). Introducing query expansion methods for collaborative information
retrieval. Reading and Learning, 252–280.
Ibnkahla, M. (2000). Applications of neural networks to digital communications – A
survey. Signal Processing, 80(2000), 1185–1215.
Jain, A. K., Murty, M. N., & Flynn, P. J. (1999). Data clustering: A review. ACM
Computing Surveys, 31(3), 264–323.
Jonhson, D. S., Aragon, C. A., Mcgeoch, L. A., & Schevon, C. (1991). Optimization by
simulated annealing: an experimental evaluation – Part II (graph coloring and
number partition). Operations research, 39(3), 378–406.
Kamps, J. (2004). Improving retrieval effectiveness by reranking documents based
on controlled vocabulary. ECIR 2004, 283–295.
Kirpatrick, S., Gellat, C. D., & Vecchi, M. P. (1983). Optimization by simulated
annealing. Science, 4598, 671–680.
Lawler, E. L., & Wood, D. E. (1966). Branch-and-bound methods: A survey.
Operations Research, 14, 699–719.
Lemire, Daniel (2005). Scale and translation invariant collaborative filtering
systems. Information Retrieval, 8(1), 129–150.
McGuinness, D. L., & Harmelen, F. v. (2004). OWL Web ontology language overview.
W3C recommendation 10 February 2004. .
Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., & Teller, E. (1953). Equation
of state calculations by fast computing machines. Journal of Chemical Physics, 21,
1087–1091.
Middleton, S. E., Shadbolt, N. R., & De Roure, D. C. (2004). Ontological user profiling
in recommender systems. ACM Transactions on Information Systems (TOIS), 22(1),
54–88.
Moore, R. E. (1991). Global optimization to prescribed accuracy. Computers and
Mathematics with Applications, 21(6/7), 25–39.
Pôssas, B., Ziviani, N., Jr., Wagner, M., & Ribeiro-Neto, B. A. (2002). Set-based model:
A new approach for information retrieval. SIGIR 2002, 230–237.
Rashid, Al., Karypis, G., & Riedl, J. (2005). Influence in ratings-based recommender
systems: An algorithm-independent approach. In Proceedings of SIAM
international conference on data mining, 2005.
Resnik, P., Iacovou, N., Suchak, M., Bergstrom, P. & Riedl, J. (1994). GroupLens: An
open architecture for collaborative filtering of netnews. In Proceedings of ACM
1994 conference computer supported cooperative work (pp. 175–186). ACM Press.
Robin, J., Ramalho, F., 2003. Can ontologies improve web search engine effectiveness
before the advent of the semantic web? In SBBD 2003 (pp. 157–169).
Salton, Gerard, & Buckley, Chris (1990). Improving retrieval performance by
relevance feedback. JASIS, 41(4), 288–297.
Sarwar, B., Karypis, G., Konstan, J., & Reidl, J. (2000). Analysis of recommendation
algorithms for e-commerce. In Proceedings of the ACM conference on electronic
commerce (pp.158–167). New York: ACM.
Sarwar, B. M., Karypis, G., Konstan, J. A., & Riedl, J. T. (2001). Item-based
collaborative filtering recommendation algorithms. In Proceedings of the tenth
international World Wide Web conference (pp. 285–295).
Sparck Jones, K. (1971). Automatic keyword classification for information retrieval.
London: Butterworths.
Sparck Jones, K., & Needham, R. M. (1968). Automatic term classification and
retrieval. Information Processing & Management, 4(1), 91–100.
Wilkinson, K., Sayers, C., Kuno, H. A., & Reynolds, D. (2003). Efficient RDF storage
and retrieval in Jena2. In The first International Workshop on Semantic Web and
Databases, Co-located with VLDB 2003 (SWDB’03), Humboldt-Universität, Berlin,
Germany, September 7–8, 2003 (pp. 131–150).
Xie, K., Han, L., & Lin, Y. (1997). Optimization method. Tientsin: University Press.
Xu, J., & Croft, B. W. (2000). Improving the effectiveness of informational retrieval
with local context analysis. ACM Transactions on Information Systems, 18(1),
79–112.
Yang, X., & Zheng, J. (2003). Artificial neural network and blind signal processing.
Tsinghua University Press.
http://www.w3.org/TR/2004/REC-owl-ref-20040210/
http://www.w3.org/TR/2004/REC-owl-ref-20040210/
http://www.cs.sandia.gov/opt/survey/main.html
http://www.cs.sandia.gov/opt/survey/main.html
http://www.w3.org/TR/2004/REC-owl-features-20040210/
http://www.w3.org/TR/2004/REC-owl-features-20040210/
HQE: A Hybrid hybrid method for Query Expansionquery expansion
Introduction
Related work
The HQE method of improving query expansion
The CCIO algorithm for constructing ontologies
The BBFU algorithm for finding the similar users
The RENQ Algorithm algorithm for Expanding New Queryexpanding new query
The SC Method method for updating RBF networks
The SACU algorithm for centers update
The CTSB algorithm for updating the output layer weights
Experimental results and discussion
Conclusion
AcknowledgementAcknowledgements
References