轨迹聚类-trajectory-clustering

  • z4_130312
    了解作者
  • 421.2KB
    文件大小
  • 文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-04-18 02:16
    上传日期
轨迹聚类算法,先划分,后聚类,聚类算法是改进的DB-Scan;linux 编译,里面有Makefile
movebank.tar.gz
  • movebank
  • traclus
  • Trajectory.cpp
    431B
  • TraClusterDoc.cpp
    3.6KB
  • Main.cpp
    860B
  • Cluster.cpp
    803B
  • Makefile
    416B
  • ClusterGen.cpp
    28.4KB
  • MDPoint.cpp
    443B
  • Param.cpp
    783B
  • data
  • deer_1995.tra
    234.4KB
  • elk_1993.tra
    549.7KB
  • hurricane1950_2006.tra
    227.3KB
  • elk.out
    383B
  • bin
  • traclus
    51.9KB
  • param
    51.6KB
  • include
  • Cluster.h
    936B
  • ClusterGen.h
    3.9KB
  • MDPoint.h
    505B
  • TraClusterDoc.h
    707B
  • Trajectory.h
    1016B
  • Common.h
    179B
内容介绍
// ClusterGen.cpp : implementation file // #include "TraClusterDoc.h" #include "ClusterGen.h" #include <algorithm rel='nofollow' onclick='return false;'> // CClusterGen CClusterGen::CClusterGen() { } CClusterGen::CClusterGen(CTraClusterDoc* document) { m_document = document; m_idArray.clear(); m_lineSegmentPointArray.clear(); } CClusterGen::~CClusterGen() { } // CClusterGen message handlers bool CClusterGen::PartitionTrajectory() { vector<CTrajectory*>::iterator iter; for (iter = m_document->m_trajectoryList.begin(); iter != m_document->m_trajectoryList.end(); iter++) FindOptimalPartition(*iter); if (!StoreClusterComponentIntoIndex()) return false; return true; } bool CClusterGen::StoreClusterComponentIntoIndex() { int nDimensions = m_document->m_nDimensions; CMDPoint* startPoint; CMDPoint* endPoint; m_nTotalLineSegments = 0; vector<CTrajectory*>::iterator iter; for (iter = m_document->m_trajectoryList.begin(); iter != m_document->m_trajectoryList.end(); iter++) { CTrajectory* pTrajectory = *iter; for (int i = 0; i < pTrajectory->m_nPartitionPoints - 1; i++) { // convert an n-dimensional line segment into a 2n-dimensional point // i.e., the first n-dimension: the start point // the last n-dimension: the end point startPoint = &(pTrajectory->m_partitionPointArray[i]); endPoint = &(pTrajectory->m_partitionPointArray[i + 1]); if (MeasureDistanceFromPointToPoint(startPoint, endPoint) < MIN_LINESEGMENT_LENGTH) continue; m_nTotalLineSegments++; CMDPoint lineSegmentPoint(nDimensions * 2); for (int j = 0; j < nDimensions; j++) { lineSegmentPoint.SetCoordinate(j, startPoint->GetCoordinate(j)); lineSegmentPoint.SetCoordinate(nDimensions + j, endPoint->GetCoordinate(j)); } LineSegmentId id; id.trajectoryId = pTrajectory->GetId(); id.order = i; m_idArray.push_back(id); m_lineSegmentPointArray.push_back(lineSegmentPoint); } } return true; } bool CClusterGen::PerformDBSCAN(float eps, int minLns) { m_epsParam = eps; m_minLnsParam = minLns; m_currComponentId = 0; m_componentIdArray.resize(m_nTotalLineSegments, -1); for (int i = 0; i < m_nTotalLineSegments; i++) m_componentIdArray[i] = UNCLASSIFIED; for (int i = 0; i < m_nTotalLineSegments; i++) { if (m_componentIdArray[i] == UNCLASSIFIED) if (ExpandDenseComponent(i, m_currComponentId, eps, minLns)) m_currComponentId++; } return true; } bool CClusterGen::ConstructCluster() { // this step consists of two substeps // notice that the result of the previous substep is used in the following substeps if (!ConstructLineSegmentCluster()) return false; if(!StoreLineSegmentCluster()) return false; return true; } #include <math.h> // NOTE: that this version does not guarantee the optimal partition void CClusterGen::FindOptimalPartition(CTrajectory* pTrajectory) { int nPoints = pTrajectory->m_nPoints; int startIndex = 0, length; int fullPartitionMDLCost, partialPartitionMDLCost; // add the start point of a trajectory pTrajectory->AddPartitionPointToArray(pTrajectory->m_pointArray[0]); for (;;) { fullPartitionMDLCost = partialPartitionMDLCost = 0; for (length = 1; startIndex + length < nPoints; length++) { // compute the total length of a trajectory fullPartitionMDLCost += ComputeModelCost(pTrajectory, startIndex + length - 1, startIndex + length); // compute the sum of (1) the length of a cluster component and // (2) the perpendicular and angle distances partialPartitionMDLCost = ComputeModelCost(pTrajectory, startIndex, startIndex + length) + ComputeEncodingCost(pTrajectory, startIndex, startIndex + length); if (fullPartitionMDLCost + MDL_COST_ADVANTAGE < partialPartitionMDLCost) { pTrajectory->AddPartitionPointToArray(pTrajectory->m_pointArray[startIndex + length - 1]); startIndex = startIndex + length - 1; length = 0; break; } } // if we reach at the end of a trajectory if (startIndex + length >= nPoints) break; } // add the end point of a trajectory pTrajectory->AddPartitionPointToArray(pTrajectory->m_pointArray[nPoints - 1]); return; } #define LOG2(_x) (float)(log((float)(_x)) / log((float)2)) int CClusterGen::ComputeModelCost(CTrajectory* pTrajectory, int startPIndex, int endPIndex) { CMDPoint* lineSegmentStart = &(pTrajectory->m_pointArray[startPIndex]); CMDPoint* lineSegmentEnd = &(pTrajectory->m_pointArray[endPIndex]); float distance = MeasureDistanceFromPointToPoint(lineSegmentStart, lineSegmentEnd); if (distance < 1.0) distance = 1.0; // to take logarithm return (int)ceil(LOG2(distance)); } int CClusterGen::ComputeEncodingCost(CTrajectory* pTrajectory, int startPIndex, int endPIndex) { CMDPoint* clusterComponentStart; CMDPoint* clusterComponentEnd; CMDPoint* lineSegmentStart; CMDPoint* lineSegmentEnd; float perpendicularDistance; float angleDistance; int encodingCost = 0; clusterComponentStart = &(pTrajectory->m_pointArray[startPIndex]); clusterComponentEnd = &(pTrajectory->m_pointArray[endPIndex]); for (int i = startPIndex; i < endPIndex; i++) { lineSegmentStart = &(pTrajectory->m_pointArray[i]); lineSegmentEnd = &(pTrajectory->m_pointArray[i + 1]); perpendicularDistance = MeasurePerpendicularDistance(clusterComponentStart, clusterComponentEnd, lineSegmentStart, lineSegmentEnd); angleDistance = MeasureAngleDisntance(clusterComponentStart, clusterComponentEnd, lineSegmentStart, lineSegmentEnd); if (perpendicularDistance < 1.0) perpendicularDistance = 1.0; // to take logarithm if (angleDistance < 1.0) angleDistance = 1.0; // to take logarithm encodingCost += ((int)ceil(LOG2(perpendicularDistance)) + (int)ceil(LOG2(angleDistance))); } return encodingCost; } float CClusterGen::MeasurePerpendicularDistance(CMDPoint* s1, CMDPoint* e1, CMDPoint* s2, CMDPoint* e2) { // we assume that the first line segment is longer than the second one float distance1; // the distance from a start point to the cluster component float distance2; // the distance from an end point to the cluster component distance1 = MeasureDistanceFromPointToLineSegment(s1, e1, s2); distance2 = MeasureDistanceFromPointToLineSegment(s1, e1, e2); // if the first line segment is exactly the same as the second one, the perpendicular distance should be zero if (distance1 == 0.0 && distance2 == 0.0) return 0.0; // return (d1^2 + d2^2) / (d1 + d2) as the perpendicular distance return ((pow(distance1, 2) + pow(distance2, 2)) / (distance1 + distance2)); } float CClusterGen::MeasureDistanceFromPointToLineSegment(CMDPoint* s, CMDPoint* e, CMDPoint* p) { int nDimensions = p->GetNDimensions(); // NOTE: the variables m_vector1 and m_vector2 are declared as member variables // construct two vectors as follows // 1. the vector connecting the start point of the cluster component and a given point // 2. the vector representing the cluster component for (int i = 0; i < nDimensions; i++) { m_vector1.SetCoordinate(i, p->GetCoordinate(i) - s->GetCoordinate(i)); m_vector2.SetCoordinate(i, e->GetCoordinate(i) - s->GetCoordinate(i)); } // a coefficient (0 <= b <= 1) m_coefficient = ComputeInnerProduct(&m_vector1, &m_vector2) / ComputeInnerProduct(&m_vector2, &m_vector2); // the projection on the cluster component from a given point // NOTE: the variable m_projectionPoint is declared as a member variable for (int i = 0; i < nDimensions; i++) m_projectionPoint.SetCoordinate(i, s->GetCoordinate(i) + m_coefficient * m_vector2.GetCoordinate(i)); // return the distance between the projection point and the given point return MeasureDistanceFromPointToPoint(p, &m_projectionPoint); } float CClusterGen::MeasureDistanceFromPointToPoint(CMDPoint* point1, CMDPoint* point2) { int nDimensions = point1->GetNDimensions(); float squareSum = 0.0; for (int i = 0; i < nDimensions; i++) squareSum += pow((point2->GetCoordinate(i) - point1->GetCoordinate(i)), 2); return
评论
    相关推荐
    • K均值聚类算法
      模式识别中常用的聚类算法,采用控制台程序,输出聚类结果
    • 聚类算法程序
      聚类算法中的感知器算法,用于模式识别中,有比较完整的算法描述
    • 谱聚类 聚类算法
      谱聚类 聚类算法 spectralClustering
    • 图像聚类算法图像聚类算法
      图像聚类算法图像聚类算法图像聚类算法图像聚类算法图像聚类算法图像聚类算法
    • Ncut聚类算法
      Ncut聚类算法,可以直接运行,有例子,程序有注释。
    • DBSCAN聚类算法
      经典DBASCAN聚类算法,适合新手小白学习,提供了数据可出效果图
    • ap聚类算法
      一个很好的利用DTW距离作相似度的ap聚类算法,同时能够自适应的调整最佳参数
    • DBSCAN聚类算法
      利用经典的基于密度的聚类算法,将四线激光雷达采集的数据进行聚类,剔除干扰点
    • apcluster聚类算法
      APCLUSTER Affinity Propagation Clustering (Frey/Dueck, Science 2007) 一种基于apcluster affinity propagation 聚类算法,预先输入类别数,可以实现自动聚类
    • AP聚类算法代码
      给出了AP聚类算法的实现代码,并给出了一个对二维坐标点进行聚类的实际例子的聚类结果。