## 4 Data Mining
### Distributed Clustering Algorithm within MoDisNet  
To realize the P2P based DDM, the algorithm has to provide the information exchange in P2P style. Here, we designed a clustering algorithm which can satisfy the P2P mining demands. The clustering problem is defined as follow: clustering is the process of grouping the data into classes of clusters so that objects within a cluster have high similarity in comparison to one another, but are very dissimilar to objects in other clusters [29]. Cluster analysis has been widely used in numerous applications, including pattern recognition, data analysis, image regions and market research. We use the clustering analysis in MoDisNet system to find out the pollution patterns (or pollution clouds) in the urban environments. The distributed data process including the data process in both MSNs and SSNs. For the MSNs, the main tasks are:  
1. sensing the air pollution data and conveying the analogy signals to digital signals;
2. storing the sampled data; and
3. sending the data to nearest SSN if the timer in MSN expires.  
And for the SSNs, the main tasks are:  
1. receiving data from MSNs;
2. choosing a certain number of SSNs as the Information Exchange Node Set (IENS) in term of a random algorithm (the random algorithm is beyond the discussion of this paper), then sending polling message to those nodes and waiting for the data exchange messages;
3. receiving the data exchange messages from the SSNs in IENS; and
4. executing the distributed data mining algorithm.  
To realize the data processing and analyzing functions described above, a distributed _k_-means algorithm (the goal is to find \(k\) centers that minimize the maximum distance of a point to its closest center [30]) is designed to mining the air pollution patterns in different locations according to the sampled air pollutants' volumes. This algorithm runs in each SSN. To describe this algorithm, we explain some of the definitions first (suppose the total numbers of SSN is n (n \(>\) 0)).  
* _SSN\({}_{i}\)_: a SSN node with the identity \(i\) (_i_ = 0,..., _n_-1);
* _S\({}_{i}\)_: an Information Exchange Node Set (IENS) of _SSN\({}_{i}\)_, which is a set of some of the SSNs that can exchange information with _SSN\({}_{i}\)_;
* _k_: the number of clusters that required in _k_-means algorithm (_k_ \(>\) 0);
* _C\({}^{l}\)\({}_{i,l}\)_: the cluster center of _j_th (_j_ = 0,..., _k_-1) cluster that is computed in _SSN\({}_{i}\)_ in _l_th recursion (_l_ \(\geq\) 0);
* _Num\({}_{i,l}\)_: the number of members (data points) belongs to _j_th cluster in _SSN\({}_{i}\)_;
* _\(\delta\)_: a pre-defined threshold.  
The algorithm is described as below:  
1. Node \(SSN_{i}\) chooses a certain number of SSNs as \(S_{i}\) in term of a random algorithm;
2. Node \(SSN_{i}\) receives data from MSNs as the local data and chooses \(k\) local data as the initial local cluster centres \(C^{0}_{i,j}\) (\(j=0\),..., \(k\)-1);
3. Node \(SSN_{i}\) calculates the Euclidean distance between each local data and each \(C^{0}_{i,j}\);
4. Node \(SSN_{i}\) distributes each data to the nearest \(C^{0}_{i,j}\) as the member of this cluster, and each local cluster of \(SSN_{i}\) can be described as (\(C^{0}_{i,j}\), \(Num_{i,j}\));
5. Node \(SSN_{i}\) sends polling messages in intervals to each SSN in \(S_{i}\) and expect to receive data information form them;
6. Node \(SSN_{x}\) in \(S_{i}\) sends back the local data description (\(C^{0}_{x,i}\), \(Num_{x,j}\)) to \(SSN_{i}\) if it receives the polling message from \(SSN_{i}\);
7. If node \(SSN_{i}\) receives all the data information it expects send back from all the node in \(S_{i}\), \(SSN_{i}\) calculates the new cluster centres as \(C^{1}_{i,j}\);
8. Node \(SSN_{i}\) computes the offset between \(C^{1}_{i,j}\) and \(C^{0}_{i,j}\), if the offset \(\leq\delta\), then the algorithm finishes; otherwise replaces \(C^{0}_{i,j}\) by \(C^{1}_{i,j}\), and go to step 3.