3. Блок-схема алгоритму
Текст програми:
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
public class MainProgram {
public static List<Cluster> IsoData(List<Point2D> points, int K, int On, int Os, int Oc, int L, int I)
{
final double A = 0.5;
List<Cluster> clusters = new ArrayList<Cluster>();
clusters.add(new Cluster(points.get(0)));
for (int k = 1; k <= I; k++)
{
for (Cluster c : clusters)
{
c.clear();
}
// Step 2
for (Point2D p : points)
{
boolean isFirstTime = true;
double min = 0;
int minIndex = 0;
for (int i = 0; i < clusters.size(); i++)
{
double distance = clusters.get(i).distanceTo(p);
if (isFirstTime || distance < min)
{
isFirstTime = false;
min = distance;
minIndex = i;
}
}
clusters.get(minIndex).addPoint(p);
}
// Step 3
for (int i = 0; i < clusters.size(); i++)
{
if (clusters.get(i).size() < On)
{
clusters.remove(i);
}
}
// Step 4
for (Cluster c : clusters)
{
c.calculateNewCenter();
}
// Step 5
List<Double> distances = new ArrayList<Double>();
for (int i = 0; i < clusters.size(); i++)
{
distances.add(clusters.get(i).averageDistance());
}
// Step 6
double generalAverageDistance = 0;
for (int i = 0; i < clusters.size(); i++)
{
generalAverageDistance += clusters.get(i).size() * distances.get(i);
}
generalAverageDistance /= points.size();
// Step 7
if (k == I)
{
Oc = 0;
}
else if (clusters.size() <= K / 2 || !(k % 2 == 0 || clusters.size() >= 2 * K))
{
// Step 8
List<Vector2D> vectors = new ArrayList<Vector2D>();
for (int j = 0; j < clusters.size(); j++)
{
Vector2D vector = new Vector2D();
for (Point2D p : clusters.get(j).points())
{
vector.setX(vector.getX() + Math.pow(p.getX() - clusters.get(j).getCenter().getX(), 2));
vector.setY(vector.getY() + Math.pow(p.getY() - clusters.get(j).getCenter().getY(), 2));
}
vectors.add(vector);
}
// Step 9 and 10
int oldNc = clusters.size();
for (int j = 0; j < oldNc; j++)
{
vectors.get(j).setX(Math.sqrt(vectors.get(j).getX() / clusters.get(j).size()));
vectors.get(j).setY(Math.sqrt(vectors.get(j).getY() / clusters.get(j).size()));
if (vectors.get(j).getX() > vectors.get(j).getY())
{
double max = vectors.get(j).getX();
if (max > Os && ((distances.get(j) > generalAverageDistance && clusters.get(j).size() > 2 * (On + 1)) || (clusters.size() <= K / 2)))
{
clusters.add(new Cluster(new Point2D(clusters.get(j).getCenter().getX() - A * max, clusters.get(j).getCenter().getY())));
clusters.get(j).getCenter().setX(clusters.get(j).getCenter().getX() + A * max);
}
}
else
{
double max = vectors.get(j).getY();
if (max > Os && ((distances.get(j) > generalAverageDistance && clusters.get(j).size() > 2 * (On + 1)) || (clusters.size() <= K / 2)))
{
clusters.add(new Cluster(new Point2D(clusters.get(j).getCenter().getX(), clusters.get(j).getCenter().getY() - A * max)));
clusters.get(j).getCenter().setY(clusters.get(j).getCenter().getY() + A * max);
}
}
}
if (oldNc != clusters.size())
{
continue;
}
}
// Step 11
List<ClusterDistance> clusterDistances = new ArrayList<ClusterDistance>();
for (int i = 0; i < clusters.size() - 1; i++)
{
for (int j = i + 1; j < clusters.size(); j++)
{
clusterDistances.add(new ClusterDistance(clusters.get(i).distanceTo(clusters.get(j).getCenter()), i, j));
}
}
// Step 12
Collections.sort(clusterDistances);
for (int i = 0; i < clusterDistances.size(); i++)
{
if (clusterDistances.get(i).Distance >= Oc || i == L)
{
clusterDistances.subList(i, clusterDistances.size() - i).clear();
break;
}
}
// Step 13
HashSet<Integer> mergedClusters = new HashSet<Integer>();
for (int i = 0; i < clusterDistances.size(); i++)
{
if (!mergedClusters.contains(clusterDistances.get(i).IndexCluster1) && !mergedClusters.contains(clusterDistances.get(i).IndexCluster2))
{
Cluster cluster1 = clusters.get(clusterDistances.get(i).IndexCluster1);
Cluster cluster2 = clusters.get(clusterDistances.get(i).IndexCluster2);
clusters.remove(cluster1);
clusters.remove(cluster2);
double x = (cluster1.size() * cluster1.getCenter().getX() + cluster2.size() * cluster2.getCenter().getX()) / (cluster1.size() + cluster2.size());
double y = (cluster1.size() * cluster1.getCenter().getY() + cluster2.size() * cluster2.getCenter().getY()) / (cluster1.size() + cluster2.size());
clusters.add(new Cluster(new Point2D(x, y)));
}
}
}
return clusters;
}
public static void main(String[] args) {
List<Point2D> list = new ArrayList<Point2D>(){{
add(new Point2D(5,5));
add(new Point2D(6,6));
add(new Point2D(7,7));
add(new Point2D(8,8));
add(new Point2D(7,15));
add(new Point2D(8,4));
add(new Point2D(9,15));
add(new Point2D(10,15));
add(new Point2D(11,15));
add(new Point2D(14,2));
add(new Point2D(15,3));
add(new Point2D(15,4));
}};
List<Cluster> clusters = IsoData(list, 3, 2, 1, 5, 0, 5);
for (int i = 0; i < clusters.size(); i++)
{
System.out.println(clusters.get(i).toString(i));
System.out.println();
}
}
}
class Point2D {
private double x;
private double y;
public double getX() {
return x;
}
public double getY() {
return y;
}
public void setX(double x) {
this.x = x;
}
public void setY(double y) {
this.y = y;
}
public Point2D(double x, double y) {
this.x = x;
this.y = y;
}
public double distanceTo(Point2D p) {
return Math.sqrt(Math.pow(x - p.x, 2) + Math.pow(y - p.y, 2));
}
public String toString() {
return String.format("(%.2f; %.2f)", x, y);
}
}
class Cluster {
protected Point2D center;
protected List<Point2D> points;
public Cluster(Point2D center) {
this.center = center;
this.points = new ArrayList<Point2D>();
}
public Point2D getCenter() {
return center;
}
public void setCenter(Point2D center) {
this.center = center;
}
public int size() {
return points.size();
}
public List<Point2D> points() {
return points;
}
public void addPoint(Point2D p) {
points.add(p);
}
public double distanceTo(Point2D p) {
return center.distanceTo(p);
}
public void calculateNewCenter() {
Point2D c = new Point2D(0, 0);
for (Point2D p : points) {
c.setX(c.getX() + p.getX());
c.setY(c.getY() + p.getY());
}
c.setX(c.getX() / points.size());
c.setY(c.getY() / points.size());
center = c;
}
public void clear() {
points.clear();
}
public double averageDistance() {
double result = 0;
for (Point2D p : points) {
result += center.distanceTo(p);
}
return result / points.size();
}
public String toString(int index) {
StringBuilder builder = new StringBuilder("Cluster #").append(index).append(" ").append(center.toString()).append("\n");
for (Point2D p : points) {
builder.append(p.toString()).append(", ");
}
builder.setLength(builder.length() - 2);
return builder.toString();
}
}
class Vector2D {
private double x;
private double y;
public double getX() {
return x;
}
public void setX(double x) {
this.x = x;
}
public double getY() {
return y;
}
public void setY(double y) {
this.y = y;
}
}
class ClusterDistance implements Comparable<ClusterDistance> {
public double Distance;
public int IndexCluster1;
public int IndexCluster2;
public ClusterDistance(double d, int i, int j) {
Distance = d;
IndexCluster1 = i;
IndexCluster2 = j;
}
public int compareTo(ClusterDistance other) {
return new Double(Distance).compareTo(other.Distance);
}
}