- Learning from a training set of labeled examples
- Not adequate for learning from interaction
- No targets provided
- An agent learns from its own experience,
interacting with its environment to achieve a goal-
Rewarded when doing something right
Punished when doing something wrong
Like how an animal or a baby learns
- model is provided unlabeled data
- goal: to discover hidden patterns
- no correct answer is provided
- Examples:
- Clustering
- Anomaly Detection
- Dimensionality Reduction
- Association Rule Mining
- Topic Modeling
- Image and Video Analysis
- Recommendation Systems:
- Medical Diagnosis:
- Clustering
Example: K-means Clustering
Groups data points into clusters based on their similarity.
Suppose we have customer data with features such as:
Age, Income, Shopping frequency
K-Means Clustering can group these customers into, say, 3 clusters:
Cluster 1: Young and budget-conscious
Cluster 2: Middle-aged professionals
Cluster 3: High-income frequent shoppers
- Randomly pick K central points (centroids or means)
- Each data point is assigned to the closest centroid, thus
obtain K clusters
- Update the centroids by finding the average position of each cluster
- Iterate the process for a number of times until the clusters become stable
A C/C++ Implementation of K-means
// kmeans.h
#ifndef __KMEANS__
#define __KMEANS__
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <limits>
using namespace std;
struct Point
{
double x, y;
int cluster;
};
void kmeans(vector<Point>& points, vector<Point>& centroids, int iterations);
#endif
|
// kmeans.cpp
// k-means clustering functions
// https://forejune.co/cuda/
#include "kmeans.h"
// distance from a point p to a centroid c
double distance(const Point& p, const Point& c)
{
return sqrt((p.x - c.x)*(p.x - c.x) + (p.y - c.y)*(p.y - c.y));
}
// Clustering 2D points stored in vector points and returns the centroids
// in vector centroids
void kmeans(vector< Point>& points, vector< Point>& centroids, int iterations)
{
int n = points.size();
int k = centroids.size();
for (int it = 0; it < iterations; it++) {
// Assign points to nearest centroid
for (int j = 0; j < n; j++ ){
double minDist = 9999;
int bestCluster = 0;
for (int c = 0; c < k; c++) {
double d = distance(points[j], centroids[c]);
if (d < minDist) {
minDist = d;
bestCluster = c;
}
}
points[j].cluster = bestCluster;
}
// Recompute centroids
int counts[k] = {0};
Point newCentroids[k] = {(0, 0, 0)};
for (int j = 0; j < n; j++){
int cl = points[j].cluster;
newCentroids[cl].x += points[j].x;
newCentroids[cl].y += points[j].y;
counts[cl]++;
}
for (int c = 0; c < k; c++) {
if (counts[c] != 0) {
centroids[c].x = newCentroids[c].x / counts[c];
centroids[c].y = newCentroids[c].y / counts[c];
}
} // for c
} // for it
}
|
Testing K-means routine
// testKmeans.cpp
// routine to test the k-means function
// https://forejune.co/cuda/
#include "kmeans.h"
int main()
{
srand(time(0));
//Some random 2D points
vector< Point> points = {
{10, 20}, {15, 18}, {50, 40},
{40, 40}, {30, 60}, {45, 55},
{18, 20}, {10, 20}, {50, 30}
};
int k = 3; // Number of clusters
int iterations = 20; // Number of K-means iterations
vector< Point> centroids(k);
int c[k];
// Randomly initialize centroids from points
for (int i = 0; i < k; i++) {
c[i] = rand() % points.size();
centroids[i] = {points[c[i]].x, points[c[i]].y};
}
kmeans(points, centroids, iterations);
//output results
for (int j = 0; j < points.size(); j++ ) {
cout << "Point (" << points[j].x << ", " << points[j].y
<< ") : Cluster " << points[j].cluster << endl;
}
return 0;
}
|
Sample Outputs:
