ICL at NTCIR-7: An Improved KNN
Algorithm for Text Categorization

Wei Wang, Sujian Li
Inst. of Computational Linguistics,Peking University

Outline• Introduction• Algorithm Details• Evaluations• Conclusion and future work
• Acknowledgment & Contact

Introduction• Traditional KNN algorithm’s computation expense is toolarge since there are nearly 5 million “labeled nodes” in
the NTCIR-7 PAJ data for the Patent Mining Task.
• To make the computing more efficient, we employ animproved KNN algorithm which makes trade-off between
effectiveness and time complexity.
– To come up with an improved algorithm which calculates thedistance between the unlabeled node and “centroid” nodes
instead of all nodes. The “centroid” node represents all nodes
belonging to the same category.
– To try two distance metrics in our algorithm: cosine similarityand Euclid distance. Evaluation results on NTCIR-7 test data
show that the former one is slightly better.

• The benefits of our method is two-fold:– Computation expense is greatly reduced, and now we have to only calculates
about 30, 000 distances for an unlabeled node. (The number of different IPC
codes used in NTCIR-7)– Data skew problem can be effectively resolved, because there is only one
centroid node for each category.

• However, whether the categorization can benefit from this method
still has to be further studied, which will be our future research.

Algorithm Details• Our system uses the PAJ (Patent Abstracts of Japan) of 1993-2002
as the labeled data for our KNN algorithm.
• We merge patent files with the same IPC code. The merged file isdenoted with a term vector which we call centroid vector.
• We find 1000 nearest centroid vectors (most possible IPC codes) for
each topic vector using two different distance metrics: the Euclid
distance metric and the cosine similarity metric.

Detailed Steps• Step 1. Extract patent file contents from raw data, compute the IDF
for each word. In order to remove noise features we discard words
appearing in less than 3 patents.
• Step 2. Merge patents with the same IPC code into one file. Countthe merged files’ term frequency and get the “centroid” vector
representation for the each merged file.
• Step 3. Get the term vector representation for each test topic. Thencalculate the distance or similarity between topic vector and eachcentroid vector. Choose 1,000 IPC codes with minimum distance or
maximum similarity as the answers.

Two distance metrics• Suppose the term vector for topic file and the ith merged file are
V i and V t o p i c respectively. The Euclid distance and cosine
similarity between the two vectors are calculated as:

Euclid (Vi , Vtopic ) =| Vi − Vtopic |C osine (V i , V topic ) =V i . V topic| V i | * | V topic |• The Euclid distance metric prefers long merged files because they
have more words. The cosine similarity metric can avoid suchproblem. Evaluation results prove this.

Evaluations• We will compare the performance of our system with otherparticipants. Each participant can submit at most 3 results. Of the 20
results submitted by nine participants, our best result ranks 12th.
• We will compare the performance of the two distance metrics:
Euclid distance and cosine similarity. Evaluation results show thatthe cosine similarity metric is better on average.

Comparison of our system and other systems• There are totally 2051 answers for 879 topics. Our system
retrieves 1888 of them.
Table 1: Comparison of retrieved answer number
Participant
Retrieved IPC (Relevant 2051)
NEUN1_S1
1975
xrce_e2j2e
1932
KECIR
1892
ICL07_1
1888
nttcs21848
BRKLY-PM-EN-02
1488
AINLP04
1455
rali1
953
PI-5b895• The IPC numbers showed in Table 1 are the maximum numbers
retrieved by each participant. The top 5 results (including ours)
show no significant difference with each other. In fact, our system’s
gap with other top systems lies in the precision indicators, as shownin Table 2 and Table 3.
Interpolate
d Value
0.00
0.10
0.20
0.30
0.40
0.50
0.60
0.70
0.80
0.90
1.00

Table 2: Comparison of average interpolated recall precision
ICL07_1
NEUN1_S1
xrce_e2j2eKECIR
0.21180.21180.20680.19220.16130.15870.11420.1021
0.09800.0962
0.09610.59650.59650.5936
0.57180.53080.52540.45220.41830.40850.40290.40270.53180.53180.53020.50750.46580.45550.38210.3536
0.34690.34240.34240.39730.39730.39490.37210.33000.32010.25070.22120.21130.20620.2062

Table 3: Comparison of micro average interpolated recall precisionInterpolated

ICL07_1

NEUN1_S1

xrce_e2j2e

KECIR

Value
0.00

0.1024

0.46640.41070.27080.10

0.0846

0.46640.41070.27080.20

0.05560.38740.33050.18620.30

0.04170.38740.27040.14860.40

0.03120.32010.2392

0.10900.50

0.02300.23530.16690.07440.60

0.01630.17700.10070.04680.70

0.01120.10970.06090.02520.80

0.00620.05190.02930.01240.90

0.00270.01490.00750.00381.00

0.00000.00000.00000.0000• Our system’s low precision indicates that our rank function is
not good enough. It’s partly caused by the model we use. Our KNN
model is “flat”, that is, it treats all categories equally while the IPC
has a hierarchical structure.

Results Analysis• We haven’t done much work on feature selection and term
weight tuning.
– Have about 400,000 features, most of which are perhaps noisefeatures. We believe that noise features greatly affect ourprecision.
– Use IDF as term weights, which may not be appropriate. Position
can also be used to tune feature weights. for example, words inpatent titles are usually more informative than words in claims,
so maybe we should assign such words higher weights.

Comparison of two distance metrics• We have submitted two results, using cosine similarity and Euclid
distance as the distance metric respectively. The former one
retrieves 1888 answers, while the other retrieves 1277. The
precision of cosine similarity is also higher than that of Euclid
distance.
Table 4: Comparison of I-precision and micro I-precision for two distance metrics
RecallI-precision

micro I-precision

CosineEuclidCosineEuclid0.00

0.21180.20940.10240.11490.10

0.21180.20940.0846

0.09140.20

0.20680.20580.0556

0.05350.30

0.19220.18990.04170.03190.40

0.16130.15430.03120.01730.50

0.15870.15090.02300.00600.60

0.1142

0.09670.01630.00190.70

0.10210.08450.01120.00000.80

0.09800.08070.00620.00000.90

0.09620.07960.00270.00001.00

0.09610.07960.00000.0000Conclusion and future work
• Conclusion– Our current model is simple, effective, at the cost of information loss.
– Negative features, and the hierarchical structure of IPC, are ignored by oursystem.

• Future work
– Consider the hierarchical structure of this classification– Try feature selection methods, like IG, MI and LSI to remove noise featuresand redundant features.
– Use a mixed model to improve the precision of our system, e.g., thecombination of KNN and other machine learning methods. That is, we will
first use the KNN model to extract top 1000 IPC codes and other models likeME or SVM to rescore each IPC code to get a more accurate ranking for them.

Acknowledgment• This work is supported by NSFC programs (No: 60603093 and60875042), and 973 National Basic Research Program of China(2004CB318102).

• For further information, please contact wwei@pku.edu.cn orlisujian@pku.edu.cn.