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

【摘要】很难找到有数据聚类算法是用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);

21. print_r(kMeans($data, 3));

23. function initialiseCentroids(array $data, $k) {

24. 	$dimensions = count($data[0]);

25. 	$centroids = array();

27. 	for($i = 0; $i < $k; $i++) {

29. 		$centroids[$i] =initialiseCentroid($data,$centroids);

30. 	}

31. 	return $centroids;

32. }

34. function initialiseCentroid($data,$centroids='') {

35. 		if(isset($centroids))

36. 		{

37. 			while(true)

38. 			{

39. 				$centroid = $data[rand(0, count($data)-1)];

40. 				if(!in_array($centroid,$centroids))

41. 				{

42. 					break;

43. 				}

44. 			}

45. 		}

46. 		else

47. 		{

48. 			$centroid = $data[rand(0, count($data)-1)];

49. 		}

50. 		echo $centroid;

51. 		return $centroid;

52. }

54. function kMeans($data, $k) {

55. 	$centroids = initialiseCentroids($data, $k);

56. 	$mapping = array();

57. 	echo "\n\n\nrandom generated centroids:\n\n";

58. 	print_r($centroids);

59. 	while(true) {

60. 		$new_mapping = assignCentroids($data, $centroids);

61. 		echo "\n\n\nmapping:\n\n";

62. 		print_r($new_mapping);

63. 		$changed = false;

64. 		foreach($new_mapping as $documentID => $centroidID) {

65. 			if(!isset($mapping[$documentID]) || $centroidID != $mapping[$documentID]) {

66. 				$mapping = $new_mapping;

67. 				$changed = true;

68. 				break;

69. 			}

70. 		}

71. 		if(!$changed){

72. 			return formatResults($mapping, $data, $centroids); 

73. 		}

74. 		$centroids  = updateCentroids($mapping, $data, $k); 

75. 	}

76. }

78. function formatResults($mapping, $data, $centroids) {

79. 	$result  = array();

80. 	$result['centroids'] = $centroids;

81. 	foreach($mapping as $documentID => $centroidID) {

82. 		$result[$centroidID][] = $data[$documentID];

83. 	}

84. 	echo "\n\n\n ========================Final results======================================<b>\n\n";

85. 	return $result;

86. }

88. function assignCentroids($data, $centroids) {

89. 	$mapping = array();

91. 	foreach($data as $documentID => $document) {

92. 		$minDist = 100;

93. 		$minCentroid = null;

94. 		foreach($centroids as $centroidID => $centroid) {

95. 			$dist = 0;

97. 				$dist = abs($centroid - $document);

99. 			if($dist < $minDist) {

100. 				$minDist = $dist;

101. 				$minCentroid = $centroidID;

102. 			}

103. 		}

104. 		$mapping[$documentID] = $minCentroid;

105. 	}

107. 	return $mapping;

108. }

110. function updateCentroids($mapping, $data, $k) {

111. 	$centroids = array();

112. 	$counts = array_count_values($mapping);

114. 	foreach($mapping as $documentID => $centroidID) {

116. 			if(!isset($centroids[$centroidID])) {

117. 				$centroids[$centroidID] = 0;

118. 			}

120. 			$centroids[$centroidID] += $data[$documentID]/$counts[$centroidID]; 

122. 	}

124. 	if(count($centroids) < $k) {

125. 		$centroids = array_merge($centroids, initialiseCentroids($data, $k - count($centroids)));

126. 	}

128.    foreach($centroids as $centID=>$val)

129. 	{

130. 	$temp=null;

131.    foreach($mapping as $documentID => $centroidID) {

133. 		if($centroidID==$centID)

134. 		{

135. 			if($temp== null || abs($val - $temp) > abs($data[$documentID] - $val)) {

137. 			$temp= $data[$documentID];

138. 		}

139. 	  }

140. 	}

141. 	$centroids[$centID]=$temp;

142.    }

143. 	$centroids=array_map(function($x){return round($x);},$centroids);

144. 	echo "\n\n\n>>>>>>>>>>> new centroids\n\n";

145. 	print_r($centroids);

148. 	return $centroids;

149. }

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

执行结果图：

我要打赏