Efficient feature selection for complex text Abstract This  paper  deals  with  a  new  feature  se-lection  and  feature  contrasting  approach for  classification  of  highly  unbalanced textual data with a high degree of similar-ity between associated classes. An exam-ple of such classification context is illus-trated  by  the  task  of  classifying  biblio-graphic  references  into  a  patent  classifi-cation  scheme.  This  task  represents  one of  the  domains  of  investigation  of  the QUAERO  project,  with  the  final  goal  of helping experts to evaluate upcoming pa-tents through the use of related research. 1Introduction Text  categorization  is  a  machine  learning  task which aims at automatically assigning predefined category  labels  to  new  upcoming  free  text  docu-ments with related characteristics [COH 05]. Be-cause  of  its  numerous  applications,  like  mail  or news  filtering  [COR  07][WAN  08],  emotion  de-tection [PAN 08], text genre analysis [BHA 93], or  patent categorization  [KOS 01][KOS 10],  text classification  has  been  one  of  the  most  studied branches  within  the  field  of  machine  learning [HIL  07].  However,  a  bunch  of  classification problems  raise  new  challenges  in  the  domain, especially  those  ones  which  implies to  deal  with imbalanced  data  and  highly  similar  classes.  In the context of text categorization, patents valida-tion assistance takes part in that class. It consists in  generating  help  to  experts  in  their  task  of evaluation of the novelty of a patent based on the automatic assignation of the most relevant scien-tific  papers  related  with  the  classification  codes of  the  said  patent.  As  soon  as  learning  is  based on citations extracted from the patents which are usually  associated  with  a  hierarchy  of  classifica-tion  codes  having  different  levels  of  generality, first, there is no guaranty of a homogeneous dis-tribution  of  the  citations  (i.e.  learning  samples) among  the  codes,  second,  there  is  a  high  chance to have similar citations in different classes.  We illustrate in that paper that the exploitation of standard  strategies  for  classification  and  prepro-cessing would leads to non exploitable results in the above mentioned context. We thus propose a new  preprocessing  alternative  as  well.  The  re-maining  of  the  paper  is  structured  as  follows. Section 2 presents the process we used to gener-ate our experimental dataset. Section 3 presents a new  feature  selection  approach  suitable  to  deal with  the   unsolved   class  imbalance  and   class similarities  problems.  Section  4  compares  the results  with  and  without  the  use  of  the  proposed approach.  Section  5  draws  our  conclusion  and perspectives. 2Dataset generation Our  main  experimental  resource  is  issued  from the  QUAREO1 project.  It  is  a  collection  of  pa-tents  related  to  the  pharmacology  domain  com-pleted  with  bibliographic  references  issued  from the  Medline2 database.  The  source  data  contains 6387  patents  in  XML  format,  grouped  into  15 subclasses  of  the  A61K  class  (medical  prepara-tion).  For  obtaining  the  bibliographical  refer-ences,  25887  citations  are  firstly  extracted  from the patents. Then the Medline database is queried with  extracted  citations  for  related  references. The querying results in 7501 bibliographical ref-erences3 which are then labeled by the class code of their citing patent.  1http://www.quaero.org 2http://www.ncbi.nlm.nih.gov/pubmed/3Medline recall is 90% relatively to unique references 
The set of labeled references represents the final document set on which the training is performed. It is converted to a bag of words model [SAL 71] using  the  TreeTagger  tool  [SCH 94]  developed by  the  Institute for  Computational  Linguistics  of the University of Stuttgart. In our case, the refer-ences are firstly lemmatized and the tagging pro-cess  is  performed  on  lemmatized  items  (in  the case when a word is unknown to the lemmatizer, its  original  form  is  conserved).  The  punctuation signs  and  the  numbers  identified  by  the  tagger are  deleted.  Every  reference  is  finally  represent-ed  as  a  term  vector  filled  with  term  frequencies. The  description  space  generated  by  the  tagger has  dimensionality  31214.  To  reduce  the  gener-ated  noise,  a  frequency  threshold  of  45  (i.e.  an average  threshold  of  3/class)  is  applied  on  the extracted descriptors. It resulted in a thresholdeddescription  space  of  dimensionality  1804.  Final-ly,  Term  Frequency-Inverse  Document  Frequen-cy  (TF-IDF)  weighting  scheme  [SAL  88]  is  ex-ploited  on  the  thresholded  space  to  obtain  a sparse representation of the data. Fig. 1. Distribution of data in patents classes(patents-cited articles-descriptors). Figure  1  highlights the  highly  imbalanced  distri-bution  of  both,  patents,  extracted  references  and keywords  attached  with  references  relatively  to the  different  class  codes.  As  an  example,  small-est  class  contains  only  22  extracted  references (A61K41  class)  whilst  the  bigger  one  has  more than 2500 (A61K31 class). The    exploitation    of    resampling    techniques [GOO 06]  as  well  as  the  one  of  standard  feature selection  techniques  [FOR  03]  could  be  envis-aged to compensate influence of the bigger clas-ses.  However,  in  our  context,  the  ability  of  such techniques  to  precisely  detect  the  right  class  is curtailed by the high class to class similarity dueto  the  association  of  the  initial  patents  to  a  spe-cialized branch of the patent classification: inter-class  similarity  computed  using  cosine  correla-tion  between  class  profiles  generated  by  the  de-scriptors  issued  from  the  extracted  bibliograph-ical  references  indicates  that  more  than  70%  of classes'  couples  have  a  similarity  between  0.5 and 0.9. As  an  alternative,  we  thus  propose  a  new  filter approach  which  relies  on  the  exploitation  of  a class-based quality measure grounded on the fea-ture  maximization  metric.  Such  metric  has  been formerly  exploited  by  Falk  et  al.  in  the  unsuper-vised context for clustering French verbs relying on syntactic and semantic features [FAL 12] and said  authors  demonstrated  both  its  intrinsic  effi-ciency  for  the  clustering  task  and  its  generic  ad-vantages for cluster labeling. 3Feature maximization based selection Let us consider a set of clusters C resulting from a  clustering  method  applied  on  a  set  of  data Drepresented  with  a  set  of  descriptive  features F, feature maximization introduced by Falk et al. in [FAL  12]  is  a  metric  which  favors  clusters  with maximum Feature  F-measure.  The Feature  F-measure of  a  feature f  associated  to  a cluster c is defined as the harmonic mean of Fea-ture    Recalland Feature    Precision indexes which in turn are defined as:  =∑∈∑   ∑∈∈ =∑∈∑∈,∈where represents  the  weight  of  the  feature ffor data d and Fc represent the set of features oc-curring in the data associated to the cluster c.  Taking  into  consideration  the  basic  definition  of feature maximization metric presented above, the feature   maximization-based   feature   selection process  can  thus  be  defined  as  a  parameter-free and  class-based  process  in  which  a  class  feature is  characterized  using  both  its  capacity  to  dis-criminate  a  given  class  from  the  others  (index) and its capacity to accurately represent theclass  data  ( index).  The  set Sc  of  features that  are  characteristic  of  a  given  class c  belong-ing to an overall class set C results in: = ∈ |  >    > where =∑∈//
and  =∑/
∈||. with C/f  representing  the  restriction  of  the  set Cto the classes in which the feature f is present. A61K6A61K8A61K9A61K31A61K33A61K35A61K36A61K38A61K39A61K41A61K45A61K47A61K48A61K49A61K511 0 0 02 0 0 03 00 04 0 0 05 0 0 06 00 07 0 0 0termesnotic esbrevets
Features that are judged relevant for a given classare the features whose representation is altogeth-er  better  than  their  average  representation  in  all the  classes  including  those  features  and  better than  the  average  representation  of  all  the  fea-tures, as regard to the feature F-measure metric.  In the specific framework of the feature maximi-zation  process,  a  contrast  enhancement  step  can be  exploited  complementary  to  the  former  fea-ture  selection  step.  The  role  of  this  step  is  to  fit the  description  of  each  data  to  the  specific  char-acteristics of its associated class which have beenformerly   highlighted   by   the   feature   selection step. In the case of our metric, it consists in mod-ifying  the  weighting  scheme  of  the  data  specifi-cally  to  each  class  by  taking  into  consideration the  "information  gain"  provided  by  the  Feature F-measures  of  the  features,  locally  to  that  class. For  a  feature c  belonging  to  the  set  of  selected features SC of a class C, the gain CFc can be de-fined as:  =  /4Experiments and results To  perform  our  experiments  we  firstly  take  into consideration  different  classification  algorithms which are implemented in the Weka toolkit4: J48 Decision Tree algorithm [QUI 93], Random For-est  algorithm  [BRE  01]  (RF),  KNN  algorithm [AHA  91],  DMNBtext  Bayesian  Network  algo-rithm [SU 08] (DMT) and SMO-SVM algorithm [PLA 98] (SMO). Most  of  these  algorithms  are  general  purpose classification algorithms, except from DMNBtext  which  is  a  Discriminative  Multino-mial Naive Bayes classifier especially developed for  text  classification.  As  compared  to  classical Multinomial  Naive  Bayes  classifier  this  algo-rithm  cumulates  the  computational  efficiency  of Naive  Bayes  approaches  and  the  accuracy  of Discriminating  approaches  by  taking  into  ac-count  both  the  likelihood  and  the  classification objectives  during  the  frequency  counting.  Other general  purpose  algorithms  whose  accuracy  has especially  been  reported  for  text  classification are  SMO  and  KNN  [ZHA  01].  Default  parame-ters  are  used  when  executing  these  algorithms, except  for KNN  for  which  the  number  of  neigh-bors is optimized based on resulting accuracy. We then more especially focus on testing the ef-ficiency  of  the  feature  selection  approaches  in-4http://www.cs.waikato.ac.nz/ml/weka/ cluding  our  new  proposal  (FMC). We include in our  test  a  panel  of  filter  approaches  which  are computationally  tractable  with  high  dimensional data5,  making  again  use  of  their  Weka  toolkit implementation.  The  panel  of  tested  methods includes:  Chi-square  selector  [LAD  11],  Infor-mation  gain  selector  |HAL  99b],  CBF  subset  se-lector  [DAS  03]  (CB),  Symmetrical  Uncertainty selector  [YUL  03],  ReliefF  selector  [KON  94] (RF)  and  Principal  Component  Analysis  selector [PER  01]  (PCA).  Defaults  parameters  are  also used  for  most  this  methods,  except  for  PCA  for which  the  percentage  of  explained  variance  is tuned  based  on  resulting  accuracy.  10-fold  cross validation is used on all our experiments. The different results are reported in Tables 1 to 4and  in  Figure  2  to  3.  Tables  and  figures  present standard  performance  measures  (True  Positive Rate (TP) or Precision, False Positive Rate (FP), Recall (R), F-measure (F) and ROC) weighted by class  sizes  and  averaged  over  all  classes.  For each  table,  and  each  combination  of  selection and  classification  methods,  a  performance  in-crease     indicator     is     computed     using     the DMNBtext  True  Positive  results  on  the  original data  as  the  reference.  Finally,  as  soon  as  the  re-sults  are  identical  for  Chi-square,  Information Gain and Symmetrical Uncertainty, they are thus reported  only  once  in  the  tables  as  Chi-square results (and noted CHI+). Table 1 highlights that performance of all classi-fication  methods  are  low  on  the  considered  da-taset if no feature selection process is performed.It    also    confirms    the    superiority    of    the DMNBtext, SMO and KNN methods on the two other  tree-based  methods  in  that  context.  Addi-tionally,  DMNBtext  provides  the  best  overall performance  in  terms  of  discrimination  as  it  is illustrated by its highest ROC value. However, as it is also shown by confusion matrix of figure 2, the method is clearly not exploitable in an opera-tional  patent  evaluation  context  because  of  the high resulting confusion between classes. It high-lights  its  intrinsic  incapacity  to  cope  with  the very  important  data  attraction  effect  of  the  big-gest class. Whenever  a  usual  feature  selection  process  is performed  in  combination  with  the  best  method, that is DMNBtext method, the exploitation of the usual  feature  selection  strategies  slightly  alters 5Exhaustive presentation and comparison of usual feature selection methods can be found in [FOR 03].
the  quality  of  the  results,  instead  of  bringing  up an  added  value,  as it  is  shown  in Table  1.  Alter-natively,  same  table  highlights  that  the  feature reduction of F-max selection method is similar to Chi-square  and  its  combination  with  F-max  data description contrasting boosts the performance of the  classification  method  (+81%),  leading  to  ex-cellent  classification  results  (Accuracy  of  0.96) in a very complex classification context. TP  FP  P R F ROC TP Incr. J48 0.42 0.16 0.40 0.42 0.40 0.63 -23% RF 0.45 0.23 0.46 0.45 0.38 0.72 -17% SMO 0.54 0.14 0.53 0.54 0.52 0.80 0% DMT 0.54 0.15 0.53 0.54 0.50 0.82 0% (Ref) KNN  0.53 0.16 0.53 0.53 0.51 0.77 -2% Table 1. Classification results on initial data. TP  FP  R F ROC Nbr Feat. TP Incr. CHI+ 0.52 0.17 0.52 0.47 0.80 282 -4% CBF 0.47 0.21 0.47 0.41 0.75 37 -13% PCA  0.47 0.18 0.47 0.44 0.77 483 -13% RF 0.52 0.16 0.52 0.48 0.81 937 -4% FMC 0.96 0.01 0.96 0.96 0.999 262/cl +81% Table 2. Classification results after feature selection (DMT classification). TP  FP  R F ROC TP Incr. J48 0.80 0.05 0.80 0.79 0.92 +48% RF 0.76 0.09 0.76 0.73 0.96 +40% SMO 0.92 0.03 0.92 0.91 0.98 +70% DMT 0.96 0.01 0.96 0.96 0.999 +81% KNN  0.66 0.14 0.66 0.63 0.85 +22% Table 3. Classification results after FMC feature  selection (all classification methods). Class label Class size Selected features  TP Rate with FMC TP Rate before a61k31 2533 223 0.999     0.79 a61k33 60 276 0.77 0.02 a61k35 459 262 0.97     0.31 a61k36 212 278 0.89     0.43 a61k38 1110 237 0.99     0.24 a61k39 1141 240 0.99     0.65 a61k41 22 225 0.14     0 a61k45 304 275 0.83     0.09 a61k47 304 278 0.91     0.21 a61k48 140 265 0.76     0.12 a61k49 90 302 0.76     0.26 a61k51 78 251 0.90     0.26 a61k6 47 270 0.55     0.04 a61k8 87 292 0.74 0.02 a61k9 759 250 0.97 0.45 Table 4. Class data and FMC selected features/class. Table 2 and figures 2-3 illustrate the capabilitiesof  the  F-max  approach  to  efficiently  cope  with the  class  imbalance  problem.  Hence,  examina-tion of both TP rate changes (especially in small classes) in table 4 and confusion matrices of fig-ures  2-3  shows  that  the  data  attraction  effect  of the  majority  class  that  occurs  at  a  high  level  in the  case  of  the  exploitation  of  the  original  data (figure 2) is quite completely overcome whenev-er  the  F-max  approach  is  exploited  (figure  3). The  capability  of  the  approach  to  correct  class imbalance  is  also  clearly  highlighted  by  the  ho-mogeneous  distribution  of  the  selected  features in  the  classes  it  provides,  despite  of  their  very different sizes (table 4). Figure 2. Confusion matrix of the optimal results before feature selection (DMT classification). Figure 3. Confusion matrix of the optimal results after FMC feature selection (DMT classification) 5Conclusion Feature maximization is an efficient cluster qual-ity  metric  which  favors  clusters  with  maximum feature representation as regard to their associat-ed data. In this paper, we have proposed a specif-ic  adaptation  of  such  metric,  which  has  already been exploited by other authors with generic ad-vantages in the framework of unsupervised learn-ing,  to  the  context  of  supervised  classification. Our  main  goal  was  to  build  up  an  efficient  fea-ture  selection  and  feature  contrasting  model  that could overcome the usual problems arising in the supervised classification of large volume of data, and more especially in that of large full text data. These problems relate to classes imbalance, high dimensionality,  noise,  and  high  degree  of  simi-larity  between  classes.  Through  our  experiments on  a  large  dataset  constituted  of  bibliographical records  extracted  from  a  patents  classification, we  more  especially  showed  that  our  approach can  naturally  cope  with  the  said  handicaps,  sig-nificantly  enhancing  the performance  of classifi-cation methods (+80%). Another main advantage of this technique is that it is a parameter-free ap-proach and it  can thus  be  used in  a  larger scope, like in the one of semi-supervised learning. 
References  [AHA  91]  Aha,  D.  &  Kibler,  D.  (1991).  Instance-based   learning   algorithms.   Machine   Learning, 6:37-66. [BHA  93]  Bhatia,  V.  K.  (1993).  Analysing  Genre  - Language  Use  in  Professional  Settings.  London, Longman,    Applied    Linguistics    and    Language Study Series. [BRE  01]  Breiman,  L.  (2001).  Random  forests.  Ma-chine Learning, 45(1): 5–32. [COH  05]  Cohen,  A.M.  &  Hersh,  W.R.  (2005).  A survey  of  current  work  in  biomedical  text  mining. Briefings in Bioinformatics 6, pp. 57-71. [COR  07]  Cormack,  G.V.  &  Lynam,  T.R.  (2007). Online  supervised  spam  filter  evaluation.  ACM Transactions on Information Systems, 25(3):11. [DAS  03]  Dash,  M.  &  Liu,  H.  (2003).  Consistency-based  search  in  feature  selection.  Artificial  Intelli-gence, 151(1):155-176. [EVA  07]  Evans,  M.,  McIntosh,  W.,  Lin,  J.  &  Cates, C.  (2007).  Recounting  the  courts?  Applying  auto-mated  content  analysis  to  enhance  empirical  legal research.   Journal   of   Empirical   Legal   Studies, 4(4):1007–1039. [FAL   12]   Falk,   I.,   Gardent,   C.   &   Lamirel,   J.-C.  (2012). Classifying French Verbs using French and English  Lexical  Resources  Proceedings  of  ACL 2012. Jeju Island. Korea. [FOR 03] Forman, G. (2003). An extensive empirical study  of  feature  selection  metrics  for  text  classifi-cation. The Journal of Machine Learning Research, 3 (2003):1289-1305. [GOO 06] Good, P. (2006). Resampling Methods. 3rd Ed. Birkhauser. [HAL  99]  Hall,  M.A.  (1999).  Correlation-based  Fea-ture Selection for Machine Learning. PhD, Univer-sity of Waikato. [HAL 99b] Hall, M.A. & Smith, L.A. (1999). Feature Selection for Machine Learning: Comparing a Cor-relation-Based  Filter  Approach  to  the  Wrapper.  In Proceedings  of  the  Twelfth  International  Florida Artificial   Intelligence   Research   Society   Confer-ence, pp. 235–239. AAAI Press. [HILL  07]  Hillard,  D.  Purpura,  S.  &  Wilkerson,  J. (2007).  An  active  learning  framework  for  classify-ing  political  text.  In  Annual  Meeting  of  the  Mid-west Political Science Association. Chicago. [KON  94]  Kononenko,  I.  (1994).  Estimating  Attrib-utes:  Analysis  and  Extensions  of  RELIEF.  In:  Eu-ropean  Conference  on  Machine  Learning,  pp.  171-182. [KOS  01]  Koster,  C.H.A.,  Seutter,  M.,  Beney,  J. (2001).  Classifying  Patent  Applications  with  Win-now.  In:  Proceedings  Benelearn  2001.  Antwerpen. Belgia. [KOS   10]   Koster   C.H.A.,   Seutter,   M.,   Beney,   J. (2010).  Multi-classification  of  Patent  Applicationswith  Winnow.  In:  Ershov  Memorial  Conference, pp. 546-555. [LAD  11]  Ladha,  L.  &  Deepa,  T.  (2011).  Feature  se-lection methods and algorithms. International Jour-nal  on  Computer  Science  and  Engineering,  3(5): 1787–1797. [PAN 08] Pang, B. & Lee, L. (2008). Opinion mining and  sentiment  analysis.  Foundations  and  Trends  in Information Retrieval, 2(1-2):1–135. [PER 01] Pearson, K. (1901). On  Lines and Planes ofClosest Fit to Systems of Points in Space. Philosophical Magazine, 2(11):559–572. [PLA  98]  Platt,  J.  (1998).  Fast  Training  of  SupportVector  Machines  using  Sequential  Minimal  Opti-mization.  In:  Advances  in  Kernel  Methods  -  Sup-port Vector Learning, Schoelkopf, B., Burges C. & Smola A. editors. MIT Press. [QUI 93] Quinlan, R. (1993). C4.5: Programs for Ma-chine  Learning.  San  Mateo,  CA:  Morgan  Kauf-mann. [SAL  71]  Salton,  G.  (1971). Automatic  processing  offoreign  language  documents.  Prentice-Hill:  Eng-lewood Cliffs. NJ. [SAL  88]  Salton,  G.  &  Buckley,  C.  (1988).  Term weighting  approaches  in  automatic  text  retrieval. Information  Processing  and  Management,  24(5): 513–523. [SCH  94]  Schmid,  H.  (1994).  Probabilistic  part-of-speech  tagging  using  decision  trees.  In:  Proceed-ings  of  International  Conference  on  New  Methods in Language Processing. [SCH  98]  Schoelkopf,  B.,  Burges,  C.  &  Smola,  A.J. editors   (1998).   Advances   in   Kernel   Methods   - Support Vector Learning. MIT Press. [SU  08]  Su,  J.,  Zhang,  H.,  Ling,  C.  &  Matwin,  S. (2008).   Discriminative   parameter   learning   for bayesian networks. ICML 2008. [WAN 98] WAN, H. (1998). An automatic news arti-cle   filtering   engine.   PhD,   Acadia   University. Wolfville. Nova Scotia. Canada. [YUL 03] Yu, L. & Liu, H. (2003). Feature Selectionfor  High-Dimensional  Data:  A  Fast  Correlation-Based  Filter  Solution.  ICML  2003,  pp.  856-863, August 21-24, 2003. Washington DC. USA. [ZHA 01] Zhang T. & Oles, F. J. (2001). Text catego-rization  based  on  regularized  linear  classificationmethods. Inf. Retr., 4(1):5–31. 