title: How to discover new classes in a classification machine learning algorithm?
body: <p>I'm using a multiclass classifier (a Support Vector Machine, via One-Vs-All) to classify data samples. Let's say I currently have <code>n</code> distinct classes.</p>
  
  <p>However, in the scenario I'm facing, it is possible that a new data sample may belong to a <strong>new</strong> class <code>n+1</code> that hasn't been seen before.</p>
  
  <p>So I guess you can say that I need a form of Online Learning, as there is no distinct training set in the beginning that suits all data appearing later. Instead I need the SVM to adapt dynamically to new classes that may appear in the future.</p>
  
  <p>So I'm wondering about if and how I can...</p>
  
  <ol>
  <li><p>identify that a new data sample does not quite fit into the existing classes but instead should result in creating a new class.</p></li>
  <li><p>integrate that new class into the existing classifier.</p></li>
  </ol>
  
  <p>I can vaguely think of a few ideas that might be approaches to solve this problem:</p>
  
  <ol>
  <li><p>If none of the binary SVM classifiers (as I have one for each class in the OVA case) predicts a fairly high probability (e.g. > 0.5) for the new data sample, I could assume that this new data sample may represent a new class.</p></li>
  <li><p>I could train a new binary classifier for that new class and add it to the multiclass SVM.</p></li>
  </ol>
  
  <p>However, these are just my naive thoughts. I'm wondering if there is some "proper" approach for this instead, e.g. using a Clustering algorithms to find all classes.</p>
  
  <p>Or maybe my approach of trying to use an SVM for this is not even appropriate for this kind of problem?</p>
  
  <p>Help on this is greatly appreciated.</p>