import numpy as npimport matplotlib.pyplot as pltdef k_means(X, K, max_iters):"""
k-means聚类算法
:param X: 数据集，每一行代表一个样本
:param K: 聚类数
:param max_iters: 最大迭代次数
:return: 聚类中心和每个样本所属的簇
"""
m, n = X.shape# 初始化聚类中心
centroids = X[np.random.choice(m, K, replace=False), :]# 迭代更新聚类中心
for i in range(max_iters):# 计算每个样本距离所有聚类中心的距离
distances = np.sqrt(np.sum((X[:, np.newaxis, :] - centroids) ** 2, axis=2))# 找到距离每个样本最近的聚类中心
labels = np.argmin(distances, axis=1)# 更新聚类中心
for j in range(K):
centroids[j, :] = np.mean(X[labels == j, :], axis=0)return centroids, labels# 生成随机数据集X = np.random.rand(100, 2)# 调用k-means聚类算法centroids, labels = k_means(X, 3, 10)# 可视化结果plt.scatter(X[:, 0], X[:, 1], c=labels)
plt.scatter(centroids[:, 0], centroids[:, 1], c='r', marker='x')
plt.show()
该示例代码中，k_means函数接受三个参数：数据集X、聚类数K和最大迭代次数max_iters。在函数内部，首先随机选择K个样本作为初始聚类中心，然后迭代更新聚类中心，直到达到最大迭代次数或者聚类中心不再变化。在每次迭代中，计算每个样本距离所有聚类中心的距离，找到距离最近的聚类中心，并更新聚类中心的位置。最终返回聚类中心和每个样本所属的簇。
在示例代码中，我们生成了一个随机数据集，并将聚类数设置为3。运行程序后，可以看到数据集被分成了3个簇，并且聚类中心用红色的叉号表示。
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法将簇看做高密度区域以从低密度区域中区分开。由于这个算法的一般性，DBSCAN建立的簇可以是任何形状的。相对的，K-means则假设簇是凸的。核样本的概念是DBSCAN的重要成分，核样本是指高密度区域的样本。一个簇是由互相靠近的核样本的集合以及靠近核样本的非核样本组成的集合组成的。这个算法有两个参数，
min_samples 和 eps ，这两个参数表示数据的稠密性。当 min_samples 增加 或者 eps 减小的时候，意味着一个簇分类有更大的密度要求。
若样本在数据集中存在 eps 距离内有至少 min_samples ，则该样本可以成为核样本。也用来定义边缘样本。核样本是向量空间的高密度区域。通过找到一个核样本，找到其附近的核样本，再找到附近核样本的附近的核样本递归地建立由核样本组成的簇。一个簇也包含邻居是核样本的非核样本。
根据定义，任何核样本是簇的一部分。任何距离核样本至少 eps 距离非核样本是异常值。
从下图中可以看到，不同的颜色表示不同的簇。大圈圈表示算法定义的核样本，小圈圈表示仍是簇的组成部分的非核样本。黑色点表示异常值。
这个算法是有随机性的，虽然标签会变化，但是核样本始终属于同一个簇。非确定性主要来自非核样本的归属。一个非核样本可能距离两个簇的非核样本都小于 eps 。根据三角不等式，这两个核样本之间的距离大于 eps ，否则他们会属于同一个簇。非核样本将会属于先产生的簇，而簇产生的先后顺序是随机的。不考虑数据集的顺序，算法是确定性的，相同数据上的 结果也会相对稳定。
当先实现是使用球树和线段树来计算点的邻居，这避免了计算时全距离矩阵。可以使用一般的距离度量方法。
当前实现不是一个节约内存的算法，因为它建立了kd-tree和ball-tree不能使用的成对的相似矩阵。可以绕过这个的方法如下：
class sklearn.cluster.DBSCAN( eps=0.5 , min_samples=5 , metric='euclidean' , algorithm='auto' , leaf_size=30 , p=None , n_jobs=1 )
程序地址： http://scikit-learn.org/stable/auto_examples/cluster/plot_dbscan.html#sphx-glr-auto-examples-cluster-plot-dbscan-py
关键在于调节前面提到的两个参数，需要不断修正。如果需要测试数据，可以留言。
DBSCAN是一种基于密度的聚类算法 它的基本原理就是给定两个参数 ξ和minp 其中 ξ可以理解为半径 算法将在这个半径内查找样本 minp是一个以ξ为半径查找到的样本个数n的限制条件 只要n>=minp 查找到的样本点就是核心样本点 算法的具体描述见参考文件 下边是这个算法的java实现
首先定义一个Point类 代表样本点
<! [endif] >
package sunzhenxing
public class Point {
private int x
private int y
private boolean isKey
private boolean isClassed
public boolean isKey() {
return isKey
}
public void setKey(boolean isKey) {
this isKey = isKey
this isClassed=true
}
public boolean isClassed() {
return isClassed
}
public void setClassed(boolean isClassed) {
this isClassed = isClassed
}
public int getX() {
return x
}
public void setX(int x) {
this x = x
}
public int getY() {
return y
}
public void setY(int y) {
this y = y
}
public Point(){
x=
y=
}
public Point(int x int y){
this x=x
this y=y
}
public Point(String str){
String[] p=str split( )
this x=Integer parseInt(p[ ])
this y=Integer parseInt(p[ ])
}
public String print(){
return <+this x+ +this y+ >
}
}
然后定义一个工具类 为算法的实现服务
package sunzhenxing
import java io BufferedReader
import java io FileReader
import java io IOException
import java util *
public class Utility {
/**
* 测试两个点之间的距离
* @param p 点
* @param q 点
* @return 返回两个点之间的距离
*/
public static double getDistance(Point p Point q){
int dx=p getX() q getX()
int dy=p getY() q getY()
double distance=Math sqrt(dx*dx+dy*dy)
return distance
}
/**
* 检查给定点是不是核心点
* @param lst 存放点的链表
* @param p 待测试的点
* @param e e半径
* @param minp 密度阈值
* @return 暂时存放访问过的点
*/
public static List<Point>isKeyPoint(List<Point>lst Point p int e int minp){
int count=
List<Point>tmpLst=new ArrayList<Point>()
for(Iterator<Point>it=erator()it hasNext()){
Point q=it next()
if(getDistance(p q)<=e){
++count
if(!ntains(q)){
tmpLst add(q)
}
}
}
if(count>=minp){
p setKey(true)
return tmpLst
}
return null
}
public static void setListClassed(List<Point>lst){
for(Iterator<Point>it=erator()it hasNext()){
Point p=it next()
if(!p isClassed()){
p setClassed(true)
}
}
}
/**
* 如果b中含有a中包含的元素 则把两个集合合并
* @param a
* @param b
* @return a
*/
public static boolean mergeList(List<Point>a List<Point>b){
boolean merge=false
for(int index= index<b size()++index){
if(ntains(b get(index))){
merge=true
break
}
}
if(merge){
for(int index= index<b size()++index){
if(!ntains(b get(index))){
a add(b get(index))
}
}
}
return merge
}
/**
* 返回文本中的点集合
* @return 返回文本中点的集合
* @throws IOException
*/
public static List<Point>getPointsList() throws IOException{
List<Point>lst=new ArrayList<Point>()
String txtPath= src\\\\sunzhenxing\\points txt
BufferedReader br=new BufferedReader(new FileReader(txtPath))
String str=
while((str=br readLine())!=null &&str!= ){
lst add(new Point(str))
}
br close()
return lst
}
}
最后在主程序中实现算法 如下所示
package sunzhenxing
import java io *
import java util *
public class Dbscan {
private static List<Point>pointsList=new ArrayList<Point>()//存储所有点的集合
private static List<List<Point>>resultList=new ArrayList<List<Point>>()//存储DBSCAN算法返回的结果集
private static int e= //e半径
private static int minp= //密度阈值
/**
* 提取文本中的的所有点并存储在pointsList中
* @throws IOException
*/
private static void display(){
int index=
for(Iterator<List<Point>>it=erator()it hasNext()){
List<Point>lst=it next()
if(lst isEmpty()){
continue
}
System out println( 第 +index+ 个聚类 )
for(Iterator<Point>it =erator()it hasNext()){
Point p=it next()
System out println(p print())
}
index++
}
}
//找出所有可以直达的聚类
private static void applyDbscan(){
try {
pointsList=Utility getPointsList()
for(Iterator<Point>it=erator()it hasNext()){
Point p=it next()
if(!p isClassed()){
List<Point>tmpLst=new ArrayList<Point>()
if((tmpLst=Utility isKeyPoint(pointsList p e minp)) != null){
//为所有聚类完毕的点做标示
Utility setListClassed(tmpLst)
resultList add(tmpLst)
}
}
}
} catch (IOException e) {
// TODO Auto generated catch block
e printStackTrace()
}
}
//对所有可以直达的聚类进行合并 即找出间接可达的点并进行合并
private static List<List<Point>>getResult(){
applyDbscan()//找到所有直达的聚类
int length=resultList size()
for(int i= i<length++i){
for(int j=i+ j<length++j){
if(rgeList(resultList get(i) resultList get(j))){
resultList get(j) clear()
}
}
}
return resultList
}
/**
* 程序主函数
* @param args
*/
public static void main(String[] args) {
getResult()
display()
//System out println(Utility getDistance(new Point( ) new Point( )))
}
}
下边是一个小测试 即使用src\\\\sunzhenxing\\points txt文件的内容进行测试 points txt的文件内容是
最后算法的结果是
第 个聚类
<>
<>
<>
<>
<>
<>
<>
<>
<>
<>
<>
第 个聚类
<>
<>
<>
<>
<>
<>
<>
lishixinzhi/Article/program/Java/hx/201311/26957
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）