轨迹聚类-trajectory-clustering

// 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