Proceedings of NTCIR-8 Workshop Meeting, June 15–18, 2010, Tokyo, JapanClustering and OCCC approaches in Document Re-ranking
Chong Teng1 , Yanxiang He1, Donghong Ji1, Yixuan Geng2, Zhewei Mai2, Guimin Lin2
1 School of Computer Science, Wuhan University, Wuhan 430072, China
2 International School of Software, Wuhan University, Wuhan 430072, China
Email: tengchong@whu.edu.cn
Abstract
In this paper, we describe our approach for information
retrieval for question answering (IR4QA) of NTCIR-8tasks. For improving information retrieval performance,
we focus mostly on the document re-ranking technique,which locates between the first retrieval documents andquery expansion. In this paper, we employ two
approaches in document re-ranking. One is based on
entropy clustering, a kind of unsupervised learningtechnology. Relevant documents from top initial
retrieval result can be automatically clustered sameclass according to information entropy values. That is acontinuation of our previous work. The other is One
Class Co-Clustering (OCCC) approach. it aims to detect
topical terms, and compute document’s topicality score.
The method is simple and performs well. The experimentresult shows using the two approaches in Document Reranking, Clustering and OCCC, can improveinformation retrieval performance.
Keywords: NTCIR, Document re-ranking, Entropy
Clustering, OCCC

1. Introduction
We participated in the IR4QA (Information Retrievalfor Question Answering) task of the ACLIA (AdvancedCross-lingual Information Access) task in NTCIR-8.
Our research focuses on the document re-ranking
technology in information retrieval. We use both bigram and single Chinese Character as index units andOKAPI BM25 as retrieval model. We apply document
re-ranking technology between the initial retrieval andthe query expansion phrase. We test two document reranking methods on the NTCIR-8 data collection andsubmit five runs.
The rest of this paper is organized as following. In
section 2, we briefly describe the initial retrieval andquery expansion phrases of our system. In section 3, thedocument re-ranking with entropy clustering approach isdiscussed. In section 4, we introduce another re-ranking
method, namely, OCCC. The performance of ourmethods on NTCIR-8 is evaluated and analyzed insection 5. In section 6, we draw conclusions and present
future work.

2. Initial Retrieval and Query Expansion
Like our previous work, we use Okapi BM25 model[7] as the retrieval model in initial retrieval, withdocuments indexed by bi-gram and single Chinesecharacter. For the BM25 model, the relevance between
the document and the query is defined in (1)-(3).

(k1  1)tf d (t ) (k 3  1)tf q (t )k 3  tf q (t )d¦ w K  tf (t )tqwtKt( N  df (t )  0.5)log
df (t )  0.5
k1 u ((1  b)  b u

(1)

(2)

dlavdl(3)
Where wt, defined in (2), is the Robertson/Spark
Jones weight of t. k1, b and k3 are parameters. k1 and b
are set as 1.2 and 0.75 respectively by default, and k3 isset as 7. dl and avdl are respectively the document lengthand average document length measured by the numberof the bi-grams.
We use re-ranked retrieved documents to do query
expansion, and use Robertson’s RSV scheme [6] toselect 200 bi-grams or single Chinese characters fromtop 20 re-ranked documents. We also make use of
Rocchio’s [5] formula, as improved by Salton andBuckley [3] to perform query expansion. The new queryis retrieved again to get the final result.

3. Document Re-Ranking With Entropy
Clustering Approach
Since no labeled relevant or irrelevant documents are
generally available in information retrieval system. Our
approaches try to explore relevant document. Firstly, weregard top documents after initial retrieval as relevant
ones, or likely relevant ones. The hypothesis result insome noises, which will be carried into relevant
documents, and affect next work. It is one of ourprevious researches.
In this paper, we make use of entropy clustering
approach to cluster relevant documents, which aims to― 143 ―Proceedings of NTCIR-8 Workshop Meeting, June 15–18, 2010, Tokyo, Japan

improve the pseudo-labeled document construction
process. Entropy clustering approach merges elementswith high similarity into the same group and separates
elements having low similarity to different groups. The
value of within-cluster entropy determines whether twoclasses should be merged, and the value of betweencluster entropy determines how many clusters arereasonable. In essence, entropy clustering is a kind of
unsupervised learning approach. That is to say, thisprocess is conducted with providing training data. We
focus on documents in initial retrieval result for theclustering strategy.
In Entropy clustering Approach, two definitions must
be clarified: within-cluster entropy and between-cluster
entropy. According to Robert Jenssen [4], within-cluster
entropy is the entropy calculated based on points in thesame cluster and is computed for each cluster
respectively; between-cluster entropy is used to calculate
the double sum runs over all data points. We use withincluster entropy to evaluate the consistency of
information within a single cluster and use betweencluster entropy to evaluate difference between twoclusters. Within-cluster entropy[1] is represented asH(Ck), while between-cluster Entropy between any twoclasses Ci and Cj is represented as H(Ci,Cj). they aredefined in (4) and (5).

f (Ci,Cj)= H(CiыCj)- H(Ci)- H(Cj)(6)3) Find out the smallest value of f (Ci,Cj), and thenmerge corresponding Ci and Cj to one new class.
4) Go back to step 2) and repeat the process until all
the documents are clustered into one.
During the clustering process, the between-classentropy between any two classes Ci and Cj is calculated
and the minimum one is recorded. A record containing
all minimum between-class entropy for each cluster stepis generated after completing the whole process.
Input:
rankDocs, initial retrieval ranking of documents
K, number of documents in the top document set
Output:re-rank, re-ranking of documents
for i=1:k
topDocs[i]= rankDocs[i];endfor i=1:kcalculate f (Ci,Cj);merge clusters;
clusters[i][]=update clusters;
betweenEntropys=calculate H(Ci,Cj)
minEntropys[i]=min(betweenEntropys);
end

H Ck

 log ³ f22 ·§ n¨ ¦ wip  w jp ¸kk1¸
 log¦¦ exp ¨¨  p 1 2h2n
¸2S k 2 h 2 n i 1 j 1¨¸©
¹M di , d j(4)2 ·§ n¨ ¦ wip  w jp ¸1¸ log¦¦ M di , d j exp ¨¨  p 1 2h2n
¸2S 2k 2 h2 n i 1 j 1¨¸©
¹­1, d  Ci , d  C j or d j  Ci , d  C j®
0, other¯k

H Ci , C jreasonableStep=max(minEntropys);for i=1: length of clusters[reasonableStep]
similarity(clusters[reasonableStep][i],query);
update maxSimilar;
end
coreCluster= clusters[reasonableStep][ maxSimilar];foreach document in coreClusterextract 5 key terms;
update keys[];end
pseudoDoc=constructPseudoDoc(keys[]);foreach document in rank
score=similarity(document, pseudoDoc);update scores[];end
re-rank=sortBy(rank, scores[]);x dxk(5)
Where h is a parameter which is set as 0.5. Ck is adocument cluster including top k documents from first
retrieval, which is defined as Ck={d1,d2,…,dk}, CK ęRk.
Rk is k dimensional vector space. di (lik) is a document
element in the document set and is represented by key
terms extracted from itself, which is which is denoted
respectively as di={w1,w2,…,wn} , d ę Rn, meaning ndimensional vector space composed by weights, whichis measured by TF·IDF scheme. wip and w jp is theweight of the pth term of document di and dj respectively.
The whole clustering process can be formulated asfollows:
1) Treat each document as an initial class forclustering.
2) With respect to any two classes, assuming
merging them together, records the difference in withincluster entropy, which is indicated by f (Ci,Cj).
f (Ci,Cj) is a evaluation function to calculate change
in within-cluster entropy as follows:

Figure 1 Re-ranking with entropy clustering
Finally, reasonable clustering result can be found in
the position where there exists a significant value ofH(Ci,Cj). Because according to the understanding in
information entropy, a combination of text information
experiences a transform from disorder to order at that
position. That is, documents which have high similarity
are clustered into together while others which have low
similarity are divided into different clusters.
Based on information entropy clustering technology,clustering result is just an intermediate stage during
document re-ranking process. What to do next is to finda cluster from clustering result which is most similar
with query to construct pseudo labeled document(Figure 1). The pseudo-labeled document represents― 144 ―

Proceedings of NTCIR-8 Workshop Meeting, June 15–18, 2010, Tokyo, Japan

relevant information which matches user’s query. Thencompare such pseudo-labeled document with all thedocuments for retrieval as our previous methods [2]. At
last, the output of document re-ranking is ranged
according to their relevance between document and userquery.

ODQPHDVPLQPD[DYH

:+8&&

&6
&6  0$3



04







0Q'&*







0$3



04





0Q'&*







(1&6  

4. One Class Co-Clustering (OCCC) Reranking
Intuitively, more topic related terms a document has,more relevant to the topic it is. Based on the assumption,
Ron Bekkerman el al. [9] proposed an OCCC (OneClass Co-Clustering) method to retrieve more topicrelated documents. One step of our document re-ranking
method is inspired from the algorithm.
Assuming that the top 20 documents are relevant
documents and the top 1000 documents are general
Chinese, we firstly extract all terms, including both bigrams and single Chinese characters, from top 20
documents from first retrieval to construct a term set(Sw). And score the topicality of every term in Sw byadopt the function J ( w)

Table 1. statistical results

Pl ( w), where Pl (w) isPg ( w)w ’s occurrence probability in the top 20 documentsfrom first retrieval (i.e. w ’s TF in top 20 documents
divided by the sum of the sum of all terms’ TF in top 20documents), and Pg (w) is w ’s occurrence probability

Row [CS-CS] represents simplified Chinese tosimplified Chinese, row [EN-CS] represents English tosimplified Chinese. Column [min] represents theminimum among all participants, column [max]represents the maximum among all participants, column[ave] represents the average of all participants, andcolumn [WHUCC] represents our group’s best result.
From statistical results, for CS-CS run, our group
achieves 0.3964, 0.4323 and 0.6433 based MAP, MQand MnDCG respectively; for EN-CS run, our group
achieves the best evaluation result among all teams,
which query employs the keywords of QA analysis
result in APQA-EN-CS-01-T.
For CS-CS run, Topic 0048 and 0049 get better
evaluation. However, we find we get poor results on
individual query topics, such as topic 0062 and topic0030. We list these three query topics as following:in top 1000 documents from first retrieval (i.e. w ’s TF
in top 1000 documents divided by the sum of all terms’
TF in the top 1000 documents). Then, we represent top
1000 documents as bags-of-words (BOW) over Sw. At
last, we apply Max-KL Algorithm, a simple information
theoretic algorithm, for score the topicality of top K
documents which will be re-ranked. The KL distance isdefined as:<TOPIC ID="ACLIA2-CS-0048"><QUESTION LANG="CS"><![CDATA[ 䇕 ᤚ䰜 ା቟㧫 ]]></QUESTION><NARRATIVE LANG="CS"><![CDATA[ ૶ ↪ ⠪ ᗐ ⍮ ㆏ 䰜 ା ቟ น ⢻ ᦭ ⊛ ⒓ภ‫>]]ޕ‬</NARRATIVE></TOPIC>Pd (di , w)
P ( w)
log l¦Pg ( w)wS w ¦ Pd ( d i , w)

<TOPIC ID="ACLIA2-CS-0049"><QUESTION LANG="CS"><![CDATA[ 䇕 ᤚ啭 ᑨ บ㧫 ]]></QUESTION><NARRATIVE LANG="CS"><![CDATA[ ૶↪⠪ᗐ⍮㆏ 啭 ᑨ บน⢻᦭⊛⒓ภᚗᜂછ䖛 ⊛㘠 ࡵ ‫>]]ޕ‬</NARRATIVE></TOPIC>KL(di )

㧔7㧕wS w

Where Pd (d , w) is w ’s occurrence probability inthe document d (i.e. w ’s TF in the document divided
by the length of the document).

5. Evaluation
We submitted five runs to NTCIR8: WHUCC-CSCS-01-T, WHUCC-CS-CS-02-T, WHUCC-EN-CS-01T, WHUCC-EN-CS-02-T, WHUCC-EN-CS-03-T.
Table 1 list statistical results of MAP (MeanAverage Precision), MQ (Mean Q-measure), MnDCG(Mean Normalized Discounted Cumulated Gain) for all
query topics [8].

<TOPIC ID="ACLIA2-CS-0062"><QUESTION LANG="CS"><![CDATA[ ᒰಾዦᜂછ⟤࿖೽ ᘏ 㒳 ᯊ 㧘 䇕 ᤚᘏ 㒳 㧫 ]]></QUESTION><NARRATIVE LANG="CS"><![CDATA[ ↪ ᠋ ᗐੌ⸃࿷ಾዦᜂછ⟤࿖೽ ᘏ㒳 ᯊ ⊛ᘏ 㒳 ᤚ䇕 㧘ઁ⊛ోฬਇ㔛ⷐ‫>]] ޕ‬</NARRATIVE>― 145 ―

Proceedings of NTCIR-8 Workshop Meeting, June 15–18, 2010, Tokyo, Japan</TOPIC><TOPIC ID="ACLIA2-CS-0030"><QUESTION LANG="CS"><![CDATA[ 䇋 ೉಴ᓴ 㡎 䇟 ⊛ශ⽎♽೉‫>]]ޕ‬</QUESTION><NARRATIVE LANG="CS"><![CDATA[ ಽᨆ⠪ᗐ⍮㆏ ᓴ 㡎 䇟 ⊛ශ⽎♽೉᦭າੜ‫>]]ޕ‬</NARRATIVE></TOPIC>
Anlyzing the results, we find question about
definition can get better results. Maybe little keywords
decrease noise in retrieval procedure. However, somefeature terms don’t get enough weightiness whenquestion is complex.

[5] J. Rocchio. Relevance Feedback in information Retrieval.
In the SMART Retrieval System Experiments in
Automatic Document processing. G. Salton, Ed., Prentice
Hall, Englewood Cliffs, N. j. 1971
[6] S. E., Robertson. On Term Selection for Query Expansion.
Journal of Documentation 46. Dec 1990, pp 359-364.
[7] S. E., Robertson, S. Walker, and M. Sparck Jones, Okapi at
TREC-3. Proc. of Third Text Retrieval Conference (TREC3), 1995
[8] Tetsuya Sakai, Hideki Shima, Noriko Kando, Ruihua Song,Chuan-Jie Lin, Teruko Mitamura, Miho Sugimoto,
Overview of the NTCIR-8 ACLIA IR4QA[9] R. Bekkerman, K. Crammer. One-Class Clustering in theText Domain. Proceedings of the 2008 Conference on
Empirical Methods in Natural Language Processing, pp.
41–50, Oct, 2008.

6. Conclusion and Future
In this paper, we introduce our approach for
information retrieval system and our experience inparticipating in IR4QA task in NTCIR-8.
In our information retrieval system, firstly, we use
both bi-grams and single characters as index units. The
initial retrieval generates ordering 1000 documents.
Secondly, we focus document re-ranking techniquewhich it is implemented between the first retrieval andquery expansion. We attempt two methods: Entropy
Clustering Approach and One Class Co-Clustering toimproving re-ranking. Lastly, we use re-ranked retrieved
documents to do query expansion.
The evaluation results show proper re-ranking
technology can explore more relevant information for
unlabeled document, and improve the precision ofretrieval system. In future, we will find an semisupervised learning approach for improving information
retrieval system greatly.

AcknowledgeThis paper is supported by the National Nature
Science Foundation of China (No. 60773011 and No.
90820005) and “985” 2nd phase development project(No. 985yk001 and 985yk004). Thanks to NTCIR andLDC for offering experiment dataset.

References[1] A. Renyi, On Measures of Entropy and Information, FourthBerkeley Symposium on Mnrhemoiicol Simistics andProbability, 1960, pp. 547-561.
[2]Chong Teng, et al. Yanxiang He, Donghong Ji, Guiming
Lin, Zhewei Mai. A Study on Pseudo Labeled Document
Constructed for Document Re-ranking, proceedings of2009 International Conference on Artificial Intelligence
and Computational Intelligence (AICI'09), shanghai during
7-8, Nov. 2009:377-380[3] G. Salton, C. Buckley. Improving Retrieval Performanceby relevance feedback. J. Am. Soc. Inf. Sci. 41, 288-297.
1990.
[4] J. Robert, et al. Clustering using Renyi’s entropy,
Proceedings of the International Joint Conference, July
2003, Vol. 1, pp. 523-528.

― 146 ―