KMedoids算法C++实现

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <cmath>

using namespace std;


struct network_packet { 
    // The structure of a network packet
    string src_addr, dst_addr;
    int src_port, dst_port, protocol, arri_time, pack_len;

    // Overload equals operator
    bool operator==(const network_packet b)const {
        return (this->src_addr == b.src_addr && this->dst_addr == b.dst_addr &&
                this->src_port == b.src_port && this->dst_port == b.dst_port );
    }

    // Overloaded less than operator
    bool operator < (const network_packet b) const {
        if      (this->src_addr != b.src_addr) return this->src_addr < b.src_addr;
        else if (this->src_port != b.src_port) return this->src_port < b.src_port;
        else if (this->dst_addr != b.dst_addr) return this->dst_addr < b.dst_addr;
        else if (this->dst_port != b.dst_port) return this->dst_port < b.dst_port; 
        else if (this->protocol != b.protocol) return this->protocol < b.protocol;
        return false;
    }
};


struct Cluster {
    // A cluster of network flows 
    vector<vector<int> > member;                            // svae the flows contained in each cluster. 
    unordered_map<int, int> medoids2index;                  // save the position(index) of the medoids in the flow.
    vector<int> index2medoids;                              // mapping the medoids index to flow index. 
    vector<bool>   none_medoids;

} cluster_init;


// The global variable
vector<pair<int, pair<double, double>> > flow;  // network flow
network_packet net_packet[10000];               // network packet

int size_packet = 0;
int k;                                          // nums of medoids

class KMedoids {
    /*
    This class is designed to calculate the k-Medoids clustering results for a set of data.
    */
private:
        vector<vector<double> > Distance;          // the distance between two flow pairs.
        Cluster &cluster;                          //
        vector<pair<double, double> > net_flow;
        int K;
public:
        //Constructors
        //KMedoids();
        KMedoids(vector<pair<int, pair<double, double>> > &flow, int k, Cluster &clust) : cluster(clust) {
            for (const auto &it : flow) {
                net_flow.emplace_back(make_pair(it.second.first, it.second.second));
            }
            Distance.resize(net_flow.size(), vector<double>(net_flow.size()));
            init_dist();
            K = k;
        }
        
        void init_dist();

        double get_dist(int flow1, int flow2);
        double get_cost(Cluster &cluster, int medoid_index, int calc_mem);
        double total_cost();

        bool regroup();
        void exchange(int, int);

        bool K_medoids_algorithm();
};

void KMedoids::exchange(int medoids_index, int mem) {
    // exchange the medoids by mem. 
    int medoids = cluster.index2medoids[medoids_index];
    if (medoids == mem) return ;
    
    cluster.medoids2index.erase(medoids);
    cluster.medoids2index.insert({mem, medoids_index});
    cluster.index2medoids[medoids_index] = mem;

    cluster.none_medoids[mem] = false;
    cluster.none_medoids[medoids] = true;
}

bool KMedoids::K_medoids_algorithm() {
    bool changed = true;
    int N = net_flow.size();
    regroup();
    while (changed) {  
        flag:;
        changed = false;
        double last_cost = total_cost();

        for (int h = 0; h < N; ++ h) {
            if (!cluster.none_medoids[h]) continue;            // assert h is not medoids.
            int min_med = 0, idx;

            for (int i = 0; i < K; ++ i) {       
                // bool is_medoids = false;
                // for (const auto & it : cluster.member[i]) {
                //     if (it == h) is_medoids = true;
                // }
                // if (!is_medoids) continue;
                int last_med = cluster.index2medoids[i];
                exchange(i, h);                             // replace i by h. 
                regroup();
                double cur_cost = total_cost();
                if (cur_cost < last_cost) {
                    changed = true;
                    goto flag ;
                }
                else {
                    exchange(i, last_med);
                    regroup();
                }
            }
        }
    } // end while.
    return true;
}


void KMedoids::init_dist() {

    for (int i = 0; i < net_flow.size(); ++ i) {
        for (int j = 0; j < net_flow.size(); ++ j) {
            Distance[i][j] = abs(net_flow[i].first - net_flow[j].first) + abs(net_flow[i].second - net_flow[j].second);
        }
    }
}

double KMedoids::get_dist(int flow1, int flow2) {
    return Distance[flow1][flow2];
}

double KMedoids::get_cost(Cluster &cluster, int medoid_index, int calc_mem) {
    double cost = 0;
    for (const auto &mem : cluster.member[medoid_index]){   // Enumerates all members that belong to the medoid cluster
        cost += Distance[calc_mem][mem];
    }
    return cost;
}

double KMedoids::total_cost() {
    double cost = 0;
    int medoid;
    for (int i = 0; i < K; ++ i) {
        medoid = cluster.index2medoids[i];
        cost += get_cost(cluster, i, medoid);
    }
    return cost;
}

bool KMedoids::regroup() {
    // classify each net_flow .
    for (auto &a : cluster.member){
        a.clear();
    }

    int med = 0;
    double min_dist;
    for (int i = 0; i < net_flow.size(); ++ i) {
        min_dist = INT_MAX;
        for (int j = 0; j < net_flow.size(); ++ j) {
            if (Distance[i][j] < min_dist) {
                if (!cluster.none_medoids[j])                 // assert j is the medoids. 
                {
                    min_dist = Distance[i][j];
                    med = j;
                }
            }
        }// end inerfor 
    cluster.member[cluster.medoids2index[med]].emplace_back(i); 
    }// end for;

    return true;
}

int preProcess() {
    /*
    this preprocessor function used to extract network flow from network packet. 
    rule: a network flow includes at least TWO packets with 
          same source address, source port, destination address, destination port, and protocol, 
    */
    stable_sort(net_packet, net_packet + size_packet);      

    int l = 0, r = 0;   // L and R are used to find the left and right boundaries of a network flow, respectively.
    while (r < size_packet) {
        while (r < size_packet - 1 && net_packet[l] == net_packet[r + 1]) ++ r; 
        if (r > l) {
            int idx = l;
            double aver_trans_time = 0, aver_len = 0; 
            int denom = r - l;
            while (l < r) {
                aver_trans_time += (net_packet[l + 1].arri_time - net_packet[l].arri_time);
                aver_len  +=  net_packet[l].pack_len;
                ++ l;
            }
            aver_len += net_packet[r].pack_len;
            aver_trans_time /= denom;
            aver_len /= (denom + 1);
            flow.emplace_back(make_pair(net_packet[idx].arri_time, make_pair(aver_trans_time, aver_len)));
        }
        l = r = r + 1;
    }
    sort(flow.begin(), flow.end());  
    return 0;
}


bool read_packet_helper(const string &filepath) {
/*
    read the network packet from file1.txt .
    Save the data to a global structure variable: net_packet.
*/
    ifstream infile(filepath, ios::in);
    if (!infile) return false;
    string s;
    getline(infile, s);              // Discard the first line of text

    int i = 0; 
    while ( !infile.eof() ) {
        infile >> net_packet[i].src_addr >> net_packet[i].src_port 
               >> net_packet[i].dst_addr >> net_packet[i].dst_port 
               >> net_packet[i].protocol >> net_packet[i].arri_time 
               >> net_packet[i].pack_len ;
        ++ i;
    }
    size_packet = i;
    return true;
}


bool read_initmedoids_helper(const string &path) {
    // get the initial medoids index. 
    ifstream infile(path, ios::in);
    if (!infile) return false;
    infile >> k;
    vector<int> t;
    cluster_init.member.resize(k, t);
    cluster_init.index2medoids.resize(k);
    cluster_init.none_medoids.resize(flow.size());

    for (int i = 0, tmp; i < k; ++ i) {
        infile >> tmp;
        cluster_init.medoids2index.insert({tmp, i});
        cluster_init.index2medoids[i] = tmp;
    }

    for (int i = 0; i < flow.size(); ++ i) {
        if (cluster_init.medoids2index.find(i) == cluster_init.medoids2index.end()) 
            cluster_init.none_medoids[i] = true;
        else
            cluster_init.none_medoids[i] = false;
    }

    return true;
}

void writeFlow2file(const string &filepath) {
    ofstream flowtxt;
    flowtxt.open(filepath);
    for (int i = 0; i < flow.size(); ++ i) {
        flowtxt << i << ' ' << fixed << setprecision(2) << flow[i].second.first << ' ' << flow[i].second.second << endl;
    }
}

void writeKMedoids2file(const string &filepath, double cost) {
    ofstream kmdetails;
    kmdetails.open(filepath);

    // total cost
    kmdetails << fixed << setprecision(2) << cost << endl;               

    // k medoids
    for (int i = 0; i < k; ++ i) {
        kmdetails << cluster_init.index2medoids[i] << ' ';               
    }kmdetails << endl;

    // flows of each medoids
    for (int i = 0; i < k; ++ i) {
         for (int j = 0; j < cluster_init.member[i].size(); ++ j) {      
             kmdetails << cluster_init.member[i][j] << ' ';
         }kmdetails << endl;
     }
}

int main(int argc, char **argv){
    read_packet_helper(argv[1]);
    preProcess();
    writeFlow2file("./Flow.txt");
    read_initmedoids_helper(argv[2]);

    KMedoids kmedoid(flow, k, cluster_init);
    kmedoid.K_medoids_algorithm();
    double cost = kmedoid.total_cost();
    writeKMedoids2file("./KMedoidsClusters.txt", cost);
    return 0;
}