一维K-means算法PHP代码实现

学习笔记 马富天 2016-07-21 22:37:36 152 1

【摘要】很难找到有数据聚类算法是用PHP编写的,不小心从git中找到一篇PHP编写K-means处理一维数据的代码,所以把它转载过来了,作为收藏。

K-means算法是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法认为簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标。

K-means算法以欧式距离作为相似度测度。

注意:欧氏距离是一个通常采用的距离定义,指在m维空间中两个点之间的真实距离,或者向量的自然长度(即该点到原点的距离)。在二维和三维空间中的欧氏距离就是两点之间的实际距离。

  1. /*
  2. $data = array( 
  3. 	2,
  4. 	3,
  5. 	20,
  6. 	30,
  7. 	25,
  8. 	35,
  9. 	45, 
  10. 	15,
  11. 	10,
  12. 	5,
  13. 	7,9,8,90,56,78,87,65,78,89,67,79,67,68,69,69,69,69
  14. );
  15. */
  16. $data=array(1,2,3,4,5,6,7,8,9);
  17. echo "<pre>";
  18. echo "Data:\n\n";
  19. print_r($data);
  20. print_r(kMeans($data, 3));
  21. function initialiseCentroids(array $data, $k) {
  22. 	$dimensions = count($data[0]);
  23. 	$centroids = array();
  24. 	for($i = 0; $i < $k; $i++) {
  25. 		
  26. 		$centroids[$i] =initialiseCentroid($data,$centroids);
  27. 	}
  28. 	return $centroids;
  29. }
  30. function initialiseCentroid($data,$centroids='') {
  31. 		if(isset($centroids))
  32. 		{
  33. 			while(true)
  34. 			{
  35. 				$centroid = $data[rand(0, count($data)-1)];
  36. 				if(!in_array($centroid,$centroids))
  37. 				{
  38. 					break;
  39. 				}
  40. 			}
  41. 		}
  42. 		else
  43. 		{
  44. 			$centroid = $data[rand(0, count($data)-1)];
  45. 		}
  46. 		echo $centroid;
  47. 		return $centroid;
  48. }
  49. function kMeans($data, $k) {
  50. 	$centroids = initialiseCentroids($data, $k);
  51. 	$mapping = array();
  52. 	echo "\n\n\nrandom generated centroids:\n\n";
  53. 	print_r($centroids);
  54. 	while(true) {
  55. 		$new_mapping = assignCentroids($data, $centroids);
  56. 		echo "\n\n\nmapping:\n\n";
  57. 		print_r($new_mapping);
  58. 		$changed = false;
  59. 		foreach($new_mapping as $documentID => $centroidID) {
  60. 			if(!isset($mapping[$documentID]) || $centroidID != $mapping[$documentID]) {
  61. 				$mapping = $new_mapping;
  62. 				$changed = true;
  63. 				break;
  64. 			}
  65. 		}
  66. 		if(!$changed){
  67. 			return formatResults($mapping, $data, $centroids); 
  68. 		}
  69. 		$centroids  = updateCentroids($mapping, $data, $k); 
  70. 	}
  71. }
  72. function formatResults($mapping, $data, $centroids) {
  73. 	$result  = array();
  74. 	$result['centroids'] = $centroids;
  75. 	foreach($mapping as $documentID => $centroidID) {
  76. 		$result[$centroidID][] = $data[$documentID];
  77. 	}
  78. 	echo "\n\n\n ========================Final results======================================<b>\n\n";
  79. 	return $result;
  80. }
  81. function assignCentroids($data, $centroids) {
  82. 	$mapping = array();
  83. 	foreach($data as $documentID => $document) {
  84. 		$minDist = 100;
  85. 		$minCentroid = null;
  86. 		foreach($centroids as $centroidID => $centroid) {
  87. 			$dist = 0;
  88. 			
  89. 				$dist = abs($centroid - $document);
  90. 		
  91. 			if($dist < $minDist) {
  92. 				$minDist = $dist;
  93. 				$minCentroid = $centroidID;
  94. 			}
  95. 		}
  96. 		$mapping[$documentID] = $minCentroid;
  97. 	}
  98. 	return $mapping;
  99. }
  100. function updateCentroids($mapping, $data, $k) {
  101. 	$centroids = array();
  102. 	$counts = array_count_values($mapping);
  103. 	foreach($mapping as $documentID => $centroidID) {
  104. 	
  105. 			if(!isset($centroids[$centroidID])) {
  106. 				$centroids[$centroidID] = 0;
  107. 			}
  108. 			
  109. 			$centroids[$centroidID] += $data[$documentID]/$counts[$centroidID]; 
  110. 		
  111. 	}
  112. 	
  113. 	if(count($centroids) < $k) {
  114. 		$centroids = array_merge($centroids, initialiseCentroids($data, $k - count($centroids)));
  115. 	}
  116.    
  117.    foreach($centroids as $centID=>$val)
  118. 	{
  119. 	$temp=null;
  120.    foreach($mapping as $documentID => $centroidID) {
  121. 		if($centroidID==$centID)
  122. 		{
  123. 			if($temp== null || abs($val - $temp) > abs($data[$documentID] - $val)) {
  124. 			$temp= $data[$documentID];
  125. 		}
  126. 	  }
  127. 	}
  128. 	$centroids[$centID]=$temp;
  129.    }
  130. 	$centroids=array_map(function($x){return round($x);},$centroids);
  131. 	echo "\n\n\n>>>>>>>>>>> new centroids\n\n";
  132. 	print_r($centroids);
  133. 	return $centroids;
  134. }

个人觉得这个代码写的很好,虽然并没有完全看懂代码。

执行结果图:

请输入图片名称

版权归 马富天PHP博客 所有

本文标题:《一维K-means算法PHP代码实现》

本文链接地址:http://www.mafutian.net/169.html

转载请务必注明出处,小生将不胜感激,谢谢! 喜欢本文或觉得本文对您有帮助,请分享给您的朋友 ^_^

4

1

上一篇《 array_map()简单介绍 》 下一篇《 数据挖掘中需要用到的数据集来源 》

所有评论

  1. 首页
  2. 上一页
  3. 1
  4. 下一页
  5. 尾页
  6. 第1页
  7. 每页12条
  8. 共1页
  9. 共1条
评论审核未开启
表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情
验证码

TOP10

  • 浏览最多
  • 评论最多