# NIDDCluster

**Repository Path**: Followfire/NIDDCluster

## Basic Information

- **Project Name**: NIDDCluster
- **Description**: NIDD是一种基于密度的聚类算法，为了解决FDP算法中的缺点
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2018-08-21
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# NIDDCluster
NIDD是一种基于密度的聚类算法，为了解决FDP算法中的缺点


##### 来源：
硕士论文：基于邻域信息的聚类和社区发现算法研究（严正龙）---第二章

##### 欧式距离
欧几里得度量（euclidean metric）（也称欧氏距离）是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离就是两点之间的实际距离。
![](https://i.imgur.com/uraiEuV.png)


##### NIDD算法思想

1、密度和邻域

![](https://i.imgur.com/GsyJUb0.png)
![](https://i.imgur.com/tH3W2hK.png)

2、邻域交集和密度差异

	首先计算所有的数据对象的pk和SkNN,然后将点根据pk从小到大排序（等价于按照密度从小到大排序）。拥有最大密度的点被视为是一个簇的簇中心。
	
	对于一个参考点，k个最近邻有3中情况：
	（1）和参考点属于不同的簇
	（2）属于同一个簇，但是它是一个边界点，不可再扩展
	（3）属于同一个簇，但是它是一个内部点，在下一轮迭代中可以继续扩展。
![](https://i.imgur.com/OB84B3K.png)
![](https://i.imgur.com/PVjUXHK.png)


##### NIDD算法框架

NIDD聚类过程：
	
	首先，将拥有最大局部密度的点视为是第一个簇的簇中心。从这个簇中心开始，通过逐个考察其k近邻中的点来扩展当前簇。已获得簇标签的点是参考点，未获得标签且在参考点的k近邻中的点是待扩展的点。
	
	如果参考点的待扩展点的密度变化不大，则将待扩展点加入当前簇并且该待扩展点也可以继续扩展它的k邻域。如果参考点的待扩展点的密度变化较大，那么将带扩展点加入当前簇，但是该待扩展点不能扩展其k近邻了。

	如果参考点和待扩展点的密度变化较小，但是交集率很小，此时表示这两个点不属于同一个簇。当前簇不再扩张时，就说明这个簇已经形成好了。

	对于未处理的点，依然使用这个方法，最终得到数据集的聚类结果。


NIDD算法流程：

算法2.1：

	首先，计算每个点的Pk和SkNN
	然后，将根据点按照Pk从小到大排列，Pk指的是数据点到其第k近的邻居的距离，这个值越小表示改点的密度越大。（即密度从大到小排列）
	
	1、初始化一个优先队列，并且将密度最大的点加入这个优先队列
	2、考察其邻域内的点。如果某邻域内的点是内部点，则将其以权重pk加入优先队列，以便下一个阶段继续扩展。这个队列的生灭过程就是一个簇的形成过程。

	Input:  Data set D={x1,x2,...,xn}
			A parameter:k
	Output: Data with label
	
	1、		Calculate Pk and SkNN for all data points
	2、      D* <-- sort D based on Pk
	3、		labelnum<--0
	4、      For each p in D* and has not been clustered do:
	5、			labelnum+=1
	6、			Mark p by labelnum
	7、			Initialize a priority queue
	8、			Push p into queue with a priority pk
	9、			While queue is not empty do:
	10、				x<--pop queue
	11、				Investigate point x(Conduct 算法2.2）
	12、			End While
	13、		End For
	14、		Post-Process(Conduct 算法2.3）

![](https://i.imgur.com/Zjc673V.png)
![](https://i.imgur.com/XMQdNT3.png)
![](https://i.imgur.com/AeMfLUD.png)
![](https://i.imgur.com/mGIJiwE.png)
![](https://i.imgur.com/gid2taW.png)
![](https://i.imgur.com/G0rOM0g.png)
![](https://i.imgur.com/Y4ek4au.png)




#### 程序运行结果


![](https://i.imgur.com/rXJnyCR.png)

k值变化

![](https://i.imgur.com/1eY6FKJ.png)

密度差异阀值变化

![](https://i.imgur.com/Pr71yU0.png)