| 2048 | #--- K-NEAREST NEIGHBOR CLASSIFIER ----------------------------------------------------------------- |
| 2049 | |
| 2050 | class KNN(Classifier): |
| 2051 | |
| 2052 | def __init__(self, k=10, distance=COSINE, train=[], baseline=FREQUENCY): |
| 2053 | """ k-nearest neighbor (kNN) is a simple supervised learning method for text classification. |
| 2054 | Documents are classified by a majority vote of nearest neighbors (cosine distance) |
| 2055 | in the training data. |
| 2056 | """ |
| 2057 | self.k = k # Number of nearest neighbors to observe. |
| 2058 | self.distance = distance # COSINE, EUCLIDEAN, ... |
| 2059 | Classifier.__init__(self, train, baseline) |
| 2060 | |
| 2061 | def train(self, document, type=None): |
| 2062 | """ Trains the classifier with the given document of the given type (i.e., class). |
| 2063 | A document can be a Document, Vector, dict, list or string. |
| 2064 | If no type is given, Document.type will be used instead. |
| 2065 | """ |
| 2066 | Classifier.train(self, document, type) |
| 2067 | |
| 2068 | def classify(self, document, discrete=True): |
| 2069 | """ Returns the type with the highest probability for the given document. |
| 2070 | If the classifier has been trained on LSA concept vectors |
| 2071 | you need to supply LSA.transform(document). |
| 2072 | """ |
| 2073 | # Distance is calculated between the document vector and all training instances. |
| 2074 | # This will make KNN.test() slow in higher dimensions. |
| 2075 | classes = {} |
| 2076 | v1 = self._vector(document)[1] |
| 2077 | D = ((distance(v1, v2, method=self.distance), type) for type, v2 in self._vectors) |
| 2078 | D = ((d, type) for d, type in D if d < 1) # Nothing in common if distance=1.0. |
| 2079 | D = heapq.nsmallest(self.k, D) # k-least distant. |
| 2080 | # Normalize probability estimates. |
| 2081 | s = sum(1 - d for d, type in D) or 1 |
| 2082 | p = defaultdict(float) |
| 2083 | for d, type in D: |
| 2084 | p[type] += (1 - d) / s |
| 2085 | if not discrete: |
| 2086 | return p |
| 2087 | try: |
| 2088 | # Ties are broken in favor of the majority class |
| 2089 | # (random winner for majority ties). |
| 2090 | m = max(p.itervalues()) |
| 2091 | p = sorted((self._classes[type], type) for type, w in p.iteritems() if w == m > 0) |
| 2092 | p = [type for frequency, type in p if frequency == p[0][0]] |
| 2093 | return choice(p) |
| 2094 | except: |
| 2095 | return self.baseline |
| 2096 | |
| 2097 | NearestNeighbor = kNN = KNN |
| 2098 | |