吴莫愁 price tagDBSCAN聚集算法改进，可⽤于车辆GPS经纬度聚集计算1、DBSCAN简介
DBSCAN（Density-Bad Spatial Clustering of Applications with Noi，具有噪声的基于密度的聚类⽅法）是⼀种基于密度的空间聚类算法。该算法将具有⾜够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最⼤集合。
该算法利⽤基于密度的聚类的概念，即要求聚类空间中的⼀定区域内所包含对象（点或其他空间对象）的数⽬不⼩于某⼀给定阈值。
DBSCAN算法的优点：
1. 聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类。
2. 与K-means⽅法相⽐，DBSCAN不需要事先知道要形成的簇类的数量。
3. 与K-means⽅法相⽐，DBSCAN可以发现任意形状的簇类。
4. 同时，DBSCAN能够识别出噪声点。
5. DBSCAN对于数据库中样本的顺序不敏感，即Pattern的输⼊顺序对结果的影响不⼤。但是，对于处于簇类之间边界样本，可能会根据哪个簇类优先被探测到⽽其归属有所摆动。
DBSCAN算法的弱点：
由于它直接对整个数据库进⾏操作且进⾏聚类时使⽤了⼀个全局性的表征密度的参数，因此也具有两个⽐较明显
1. 当数据量增⼤时，要求较⼤的内存⽀持I/O消耗也很⼤；
2. 当空间聚类的密度不均匀、聚类间距差相差很⼤时，聚类质量较差。
3. DBScan不能很好反映⾼尺⼨数据。
4. DBScan不能很好反映数据集以变化的密度。
2、算法步骤
DBScan需要⼆个参数: 扫描半径 (eps)和最⼩包含点数(minPts)。 任选⼀个未被访问(unvisited)的点开始，找出与其距离在eps之内(包括eps)的所有附近点。
如果 附近点的数量 ≥ minPts，则当前点与其附近点形成⼀个簇，并且出发点被标记为已访问(visited)。 然后递归，以相同的⽅法处理该簇内所有未被标记为已访问(visited)的点，从⽽对簇进⾏扩展。
如果 附近点的数量 < minPts，则该点暂时被标记作为噪声点。
如果簇充分地被扩展，即簇内的所有点被标记为已访问，然后⽤同样的算法去处理未被访问的点。
DBScan需要⼆个参数: 扫描半径 (eps)和最⼩包含点数(minPts)。 任选⼀个未被访问(unvisited)的点开始，找出与其距离在eps之内(包括eps)的所有附近点。
如果 附近点的数量 ≥ minPts，则当前点与其附近点形成⼀个簇，并且出发点被标记为已访问(visited)。 然后递归，以相同的⽅法处理该簇内所有未被标记为已访问(visited)的点，从⽽对簇进⾏扩展。
如果 附近点的数量 < minPts，则该点暂时被标记作为噪声点。
如果簇充分地被扩展，即簇内的所有点被标记为已访问，然后⽤同样的算法去处理未被访问的点。
3、代码
在⽹上找到DBSCAN聚集算法源代码，运⾏了⼀下发现结果有些偏差，于是着⼿修复和改进，并可⽤于车辆GPS经纬度进⾏聚集，不多说直接贴代码了：
DataPoint.h⽂件
#ifndef DataPoint_H
#define DataPoint_H
#pragma once
#include <vector>
#include <t>
using namespace std;
const int DIME_NUM=2; //数据维度为2，全局常量
//数据点类型
class DataPoint
{
private:
unsigned long dpID; //数据点ID
double dimension[DIME_NUM]; //维度数据
long clusterId; //所属聚类ID
bool isKey; //是否核⼼对象
bool visited; //是否已访问
vector<unsigned long> arrivalPoints; //领域数据点id列表
public:
CString strDeviceID;//设备ID
int nVehicleID;//车辆ID
public:
DataPoint(); //默认构造函数
DataPoint(unsigned long dpID,double* dimension , bool isKey); //构造函数
unsigned long GetDpId(); //GetDpId⽅法
void SetDpId(unsigned long dpID); //SetDpId⽅法
double* GetDimension(); //GetDimension⽅法
void SetDimension(double* dimension); //SetDimension⽅法
void SetDimension(double* dimension, const CString deviceID); //SetDimension⽅法
void SetDimension(double* dimension, const int vehicleID); //SetDimension⽅法
bool IsKey(); //GetIsKey⽅法
void SetKey(bool isKey); //SetKey⽅法
bool isVisited(); //GetIsVisited⽅法
void SetVisited(bool visited); //SetIsVisited⽅法
long GetClusterId(); //GetClusterId⽅法
void SetClusterId(long classId); //SetClusterId⽅法
vector<unsigned long>& GetArrivalPoints(); //GetArrivalPoints⽅法
};
#endif
DataPoint.cpp⽂件
#include "stdafx.h"
#include "DataPoint.h"
//默认构造函数
DataPoint::DataPoint()
{
}
//构造函数
DataPoint::DataPoint(unsigned long dpID,double* dimension , bool isKey):isKey(isKey),dpID(dpID) {
//传递每维的维度数据
ominfor(int i=0; i<DIME_NUM;i++)
{
this->dimension[i]=dimension[i];
this->dimension[i]=dimension[i];
}
}
//设置维度数据
void DataPoint::SetDimension(double* dimension)
{
for(int i=0; i<DIME_NUM;i++)
{
this->dimension[i]=dimension[i];
}
}
//设置维度数据
void DataPoint::SetDimension(double* dimension, const CString deviceID) {
SetDimension(dimension);
this->strDeviceID = deviceID;
}
//设置维度数据
void DataPoint::SetDimension(double* dimension, const int vehicleID)
{
SetDimension(dimension);
this->nVehicleID = vehicleID;
}
//获取维度数据
double* DataPoint::GetDimension()
{
return this->dimension;
}
//获取是否为核⼼对象
bool DataPoint::IsKey()
{
return this->isKey;
}
//设置核⼼对象标志
void DataPoint::SetKey(bool isKey)
{
this->isKey = isKey;
}
/
/获取DpId⽅法
unsigned long DataPoint::GetDpId()
{
return this->dpID;
}
//设置DpId⽅法
void DataPoint::SetDpId(unsigned long dpID)
{
this->dpID = dpID;
}
//GetIsVisited⽅法
bool DataPoint::isVisited()
{
return this->visited;
}
//SetIsVisited⽅法
void DataPoint::SetVisited( bool visited )
void DataPoint::SetVisited( bool visited )
{
this->visited = visited;
}
//GetClusterId⽅法
long DataPoint::GetClusterId()
{
return this->clusterId;
}
//GetClusterId⽅法
void DataPoint::SetClusterId( long clusterId )
{
this->clusterId = clusterId;
}
//GetArrivalPoints⽅法
vector<unsigned long>& DataPoint::GetArrivalPoints()
{
return arrivalPoints;
}
ClusterAnalysis.h⽂件
#ifndef ClusterAnalysis_H
#define ClusterAnalysis_H
#include <iostream>
#include <cmath>
#include "DataPoint.h"
using namespace std;
//聚类分析类型
class ClusterAnalysis
{
private:
vector<DataPoint> dadaSets; //数据集合
unsigned int dimNum; //维度
double radius; //半径
unsigned int dataNum; //数据数量
unsigned int minPTs; //邻域最⼩数据个数
unsigned long m_MaxclusterId; //最⼤簇ID;
void SetArrivalPoints(DataPoint& dp); //设置数据点的领域点列表
void KeyPointCluster( unsigned long i, unsigned long clusterId ); //对数据点领域内的点执⾏聚类操作
衣服店摆设
public:
ClusterAnalysis(){} //默认构造函数
bool Init(double radius, int minPTs); //初始化操作
bool Init(char* fileName, double radius, int minPTs); //从⽂件初始化
bool AddData(DataPoint &DP) ; //加载数据
bool DoDBSCANRecursive(); //DBSCAN递归算法
bool WriteToFile(char* fileName); //将聚类结果写⼊⽂件
double GetDistance(DataPoint dp1, DataPoint dp2, bool isGPS = true); //距离函数
unsigned long GetMaxClusterId(); //获取最⼤簇ID
DataPoint GetDataPoint(unsigned long clusterId, vector<DataPoint> &DpSets);//根据点簇ID，获取对应数据，并返回其中⼀个核⼼对象 };
#endif
ClusterAnalysis.cpp⽂件
#include "stdafx.h"
#include "ClusterAnalysis.h"
#include <fstream>
#include <iosfwd>
#include <math.h>
const double PI = 3.1415926535897932384626433;
const double R = 6.378137*1e6;
/*
函数：聚类初始化操作
说明：将半径，领域最⼩数据个数信息写⼊聚类算法类
参数：
double radius; //半径
int minPTs; //领域最⼩数据个数gct考试
返回值： true; */
bool ClusterAnalysis::Init(double radius, int minPTs)
{knockover
this->radius = radius; //设置半径
this->minPTs = minPTs; //设置领域最⼩数据个数
this->dimNum = DIME_NUM; //设置数据维度
dataNum = 0;
return true; //返回
}
/*四级总分多少
函数：聚类初始化操作
说明：将数据⽂件名，半径，领域最⼩数据个数信息写⼊聚类算法类，读取⽂件，把数据信息读⼊写进算法类数据集合中参数：
char* fileName; //⽂件名
double radius; //半径
int minPTs; //领域最⼩数据个数
返回值： true; */
bool ClusterAnalysis::Init(char* fileName, double radius, int minPTs)
{
this->radius = radius; //设置半径
this->minPTs = minPTs; //设置领域最⼩数据个数
this->dimNum = DIME_NUM; //设置数据维度
ifstream ifs(fileName); //打开⽂件
if (! ifs.is_open()) //若⽂件已经被打开，报错误信息
{
cout << "Error opening file"; //输出错误信息
exit (-1); //程序退出
nationalday}
福山雅治 最爱
unsigned long i=0; //数据个数统计
while (! f() ) //从⽂件中读取POI信息，将POI信息写⼊POI列表中
{
DataPoint tempDP; //临时数据点对象
2016年12月六级答案double tempDimData[DIME_NUM]; //临时数据点维度信息
for(int j=0; j<DIME_NUM; j++) //读⽂件，读取每⼀维数据
{
ifs>>tempDimData[j];
}
tempDP.SetDimension(tempDimData); //将维度信息存⼊数据点对象内
//char date[20]="";
//char time[20]="";
double type; //⽆⽤信息
//ifs >> date;nervous
/
/ifs >> time; //⽆⽤信息读⼊
tempDP.SetDpId(i); //将数据点对象ID设置为i
