IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> KMeans算法 -> 正文阅读

[数据结构与算法]KMeans算法

原理参考:
K-means聚类算法原理及python实现
Sklearn之KMeans算法

python实现:

import random
import pandas as pd
import numpy as np

class KMeans:
    def __init__(self, dataSet, k):
        self.dataSet = dataSet
        self.k = k

    # 计算欧拉距离
    def calcDis(self, centroids):
        clalist=[]
        for data in self.dataSet:
            diff = np.tile(data, (self.k, 1)) - centroids  #相减  a=[0,1,2], (np.tile(a,(2,1))就是把a先沿x轴复制1倍,即没有复制,仍然是 [0,1,2]。再把结果沿y方向复制2倍得到array([[0,1,2],[0,1,2]]))
            squaredDiff = diff ** 2     #平方
            squaredDist = np.sum(squaredDiff, axis=1)   #和  (axis=1表示行)
            distance = squaredDist ** 0.5  #开根号
            clalist.append(distance) 
        clalist = np.array(clalist)  #返回一个每个点到质点的距离len(dateSet)*k的数组
        return clalist

    # 计算质心
    def classify(self, centroids):
        # 计算样本到质心的距离
        clalist = self.calcDis(centroids)
        #print(dataSet, centroids, clalist)
        # 分组并计算新的质心
        minDistIndices = np.argmin(clalist, axis=1)    #axis=1 表示求出每行的最小值的下标
        #print(clalist, minDistIndices)
        newCentroids = pd.DataFrame(self.dataSet).groupby(minDistIndices).mean() #DataFrame(dataSet)对DataSet分组,groupby(min)按照min进行统计分类,mean()对分类结果求均值
        #print(newCentroids, newCentroids.values)
        newCentroids = newCentroids.values    
        changed = newCentroids - centroids #计算变化量
        return changed, newCentroids

    # 使用k-means分类
    def predict(self):
        # 随机取质心
        centroids = self.dataSet[np.random.choice(self.dataSet.shape[0], size=self.k, replace=False), :]
        # 更新质心 直到变化量全为0
        changed, newCentroids = self.classify(centroids)    
        #print(centroids,newCentroids) 
        while np.any(changed != 0):          
            changed, newCentroids = self.classify(newCentroids)
            #print(changed)   
        centroids = newCentroids.tolist()   #tolist()将矩阵转换成列表
        # 根据质心计算每个集群
        cluster = []
        clalist = self.calcDis(centroids) #调用欧拉距离
        minDistIndices = np.argmin(clalist, axis=1)  
        for i in range(self.k):
            cluster.append([])
        for i, j in enumerate(minDistIndices):   #enumerate()可同时遍历索引和遍历元素
            cluster[j].append(self.dataSet[i])        
        return centroids, cluster
 

if __name__=='__main__': 
    x = np.array([[1, 1], [1, 2], [2, 1], [6, 4], [6, 3], [5, 4]])
    kmeans = KMeans(x, 2)
    centroids, cluster = kmeans.predict()
    print('质心为:%s' % centroids)
    print('集群为:%s' % cluster)

python调包:

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn import metrics
import matplotlib.pyplot as plt

x = np.array([[1, 1], [1, 2], [2, 1], [6, 4], [6, 3], [5, 4]])
k_means = KMeans(n_clusters=2)
k_means.fit(x)

y_predict = k_means.predict(x)
plt.scatter(x[:,0],x[:,1],c=y_predict)
plt.show()
print(k_means.predict((x[:,:])))
print(k_means.cluster_centers_)
print(k_means.inertia_)
print(metrics.silhouette_score(x,y_predict))

C++实现:

#include <iostream>
#include <vector>
#include <time.h>

void printMat(std::vector<std::vector<float>> mat)
{
	for (size_t i = 0; i < mat.size(); i++)
	{
		for (size_t j = 0; j < mat[0].size(); j++)
		{
			std::cout << mat[i][j] << " ";
		}
		std::cout << std::endl;
	}
	std::cout << std::endl;
}

bool checkZeros(std::vector<std::vector<float>> mat)
{
	bool flag = true;
	for (size_t i = 0; i < mat.size(); i++)
	{
		for (size_t j = 0; j < mat[0].size(); j++)
		{
			if (mat[i][j] != 0) flag = false;
		}
	}
	return flag;
}

std::vector<int> getminDistIndices(std::vector<std::vector<float>> clalist)
{
	std::vector<int> minDistIndices(clalist.size());
	for (size_t i = 0; i < clalist.size(); i++)
	{
		float minDist = INT_MAX;
		int minDistIndex = 0;
		for (size_t j = 0; j < clalist[0].size(); j++)
		{
			if (clalist[i][j] < minDist)
			{
				minDist = clalist[i][j];
				minDistIndex = j;
			}
		}
		//std::cout << minDistIndex << std::endl;
		minDistIndices[i] = minDistIndex;
	}
	return minDistIndices;
}

class KMeans
{
public:
	KMeans(std::vector<std::vector<float>> dataSet, int k) :m_dataSet(dataSet), m_k(k) {};

	std::vector<std::vector<float>> calcDis(std::vector<std::vector<float>> centroids)
	{
		std::vector<std::vector<float>> clalist;
		for (auto data : m_dataSet)
		{
			std::vector<std::vector<float>> diff(m_k);
			for (size_t i = 0; i < diff.size(); i++)
			{
				diff[i] = data;
			}
			for (size_t i = 0; i < diff.size(); i++)
			{
				for (size_t j = 0; j < diff[0].size(); j++)
				{
					diff[i][j] -= centroids[i][j];
					diff[i][j] = pow(diff[i][j], 2);
				}
			}
			std::vector<float> squaredDist(diff.size());
			for (size_t i = 0; i < diff.size(); i++)
			{
				for (size_t j = 0; j < diff[0].size(); j++)
				{
					squaredDist[i] += diff[i][j];
				}
				squaredDist[i] = sqrt(squaredDist[i]);
			}
			clalist.push_back(squaredDist);
		}

		//printMat(clalist);
		return clalist;
	}

	void classify(std::vector<std::vector<float>> centroids, std::vector<std::vector<float>>& newCentroids, std::vector<std::vector<float>>& changed)
	{
		std::vector<std::vector<float>> clalist = calcDis(centroids);
		std::vector<int> minDistIndices = getminDistIndices(clalist);

		newCentroids.resize(m_k, std::vector<float>(m_dataSet[0].size()));
		for (size_t i = 0; i < m_dataSet[0].size(); i++)
		{
			std::vector<float> sum(m_k);
			std::vector<int> num(m_k, 0);
			for (size_t j = 0; j < m_dataSet.size(); j++)
			{
				sum[minDistIndices[j]] += m_dataSet[j][i];
				++num[minDistIndices[j]];
			}

			for (size_t j = 0; j < m_k; j++)
			{
				//std::cout << sum[j] <<" "<<num[j] << std::endl;
				newCentroids[j][i] = sum[j] / num[j];
			}
		}

		//printMat(newCentroids);

		changed.resize(m_k, std::vector<float>(m_dataSet[0].size()));
		for (size_t i = 0; i < changed.size(); i++)
		{
			for (size_t j = 0; j < changed[0].size(); j++)
			{
				changed[i][j] = newCentroids[i][j] - centroids[i][j];
			}
		}
	}

	void predict(std::vector<std::vector<float>>& centroids, std::vector<std::vector<std::vector<float>>>& cluster)
	{
		srand((unsigned)time(NULL));
		std::vector<int> random_indices;
		while (random_indices.size() < m_k)
		{
			int random_index = rand() % m_dataSet.size();
			if(find(random_indices.begin(), random_indices.end(), random_index)== random_indices.end())
				random_indices.push_back(random_index);
		}

		centroids.resize(m_k, std::vector<float>(m_dataSet[0].size()));
		for (size_t i = 0; i < m_k; i++)
		{
			centroids[i] = m_dataSet[random_indices[i]];
		}

		std::vector<std::vector<float>> newCentroids;
		std::vector<std::vector<float>> changed;
		classify(centroids, newCentroids, changed);
		//printMat(centroids); printMat(newCentroids);

		while (!checkZeros(changed))
		{
			std::vector<std::vector<float>> copyCentroids = newCentroids;
			classify(copyCentroids, newCentroids, changed);
			//printMat(changed);
		}
		centroids = newCentroids;

		std::vector<std::vector<float>> clalist = calcDis(newCentroids);
		std::vector<int> minDistIndices = getminDistIndices(clalist);
		//for (auto i : minDistIndices)	std::cout << i << std::endl;

		cluster.resize(m_k);
		for (size_t i = 0; i < minDistIndices.size(); i++)
		{
			cluster[minDistIndices[i]].push_back(m_dataSet[i]);
		}
	}

private:
	std::vector<std::vector<float>> m_dataSet;
	int m_k;
};


int main(int argc, char* argv[])
{
	std::vector<std::vector<float>> dataSet = { {1, 1},{1, 2},{2, 1},{6, 4},{6, 3},{5, 4} };
	//std::vector<std::vector<float>> centroids = { {1, 2},{6, 4} };
	int k = 2;
	KMeans kmeans = KMeans(dataSet, k);
	//kmeans.calcDis(centroids);
	//kmeans.classify(centroids);

	std::vector<std::vector<float>> centroids;
	std::vector<std::vector<std::vector<float>>> cluster;
	kmeans.predict(centroids, cluster);
	printMat(centroids);
	printMat(cluster[0]); printMat(cluster[1]);

	system("pause");
	return EXIT_SUCCESS;
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-05-08 08:20:57  更:2022-05-08 08:24:57 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 3:52:44-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码