Details of the computational cost of the KNN and the PNCN classification algorithms. Let k denotes the nearest neighbour number, and M is category number. N and d are the number of training samples and the dimension of feature space, respectively.
| Classifier . | Computational cost . | Description . |
|---|---|---|
| KNN | O(Nd + Nk + k) | For each class, KNN is used to determine the class of the sample. |
| O(2Ndk + Nk) | Search k-nearest neighbour of the nearest centroid in each class. | |
| PNCN | O(Mdk(k + 1)/2) | Calculate k local mean vetors corresponding to k-nearest centroid neighbours for each class. |
| O(Mk) | Assigning weights to local mean vectors of each class. | |
| O(Md + M) | For each class, PNCN is used to determine the class of the sample. |
| Classifier . | Computational cost . | Description . |
|---|---|---|
| KNN | O(Nd + Nk + k) | For each class, KNN is used to determine the class of the sample. |
| O(2Ndk + Nk) | Search k-nearest neighbour of the nearest centroid in each class. | |
| PNCN | O(Mdk(k + 1)/2) | Calculate k local mean vetors corresponding to k-nearest centroid neighbours for each class. |
| O(Mk) | Assigning weights to local mean vectors of each class. | |
| O(Md + M) | For each class, PNCN is used to determine the class of the sample. |
Details of the computational cost of the KNN and the PNCN classification algorithms. Let k denotes the nearest neighbour number, and M is category number. N and d are the number of training samples and the dimension of feature space, respectively.
| Classifier . | Computational cost . | Description . |
|---|---|---|
| KNN | O(Nd + Nk + k) | For each class, KNN is used to determine the class of the sample. |
| O(2Ndk + Nk) | Search k-nearest neighbour of the nearest centroid in each class. | |
| PNCN | O(Mdk(k + 1)/2) | Calculate k local mean vetors corresponding to k-nearest centroid neighbours for each class. |
| O(Mk) | Assigning weights to local mean vectors of each class. | |
| O(Md + M) | For each class, PNCN is used to determine the class of the sample. |
| Classifier . | Computational cost . | Description . |
|---|---|---|
| KNN | O(Nd + Nk + k) | For each class, KNN is used to determine the class of the sample. |
| O(2Ndk + Nk) | Search k-nearest neighbour of the nearest centroid in each class. | |
| PNCN | O(Mdk(k + 1)/2) | Calculate k local mean vetors corresponding to k-nearest centroid neighbours for each class. |
| O(Mk) | Assigning weights to local mean vectors of each class. | |
| O(Md + M) | For each class, PNCN is used to determine the class of the sample. |
This PDF is available to Subscribers Only
View Article Abstract & Purchase OptionsFor full access to this pdf, sign in to an existing account, or purchase an annual subscription.
