30-05-2012, 05:05 PM
A DIVIDE AND CONQUER APPROACH FOR MINIMUM SPANNING TREE-BASED CLUSTERING
A DIVIDE AND CONQUER APPROACH FOR MINIMUM .doc (Size: 3.73 MB / Downloads: 140)
INTRODUCTION
1.1 EXISTING SYSTEM
Some classical algorithms rely on either the idea of grouping the data points around some “centers” or the idea of separating the data points using some regular geometric curves such as hyper planes. As a result, they generally do not work well when the boundaries of the clusters are irregular.
1.2 PROPOSED SYSTEM
Sufficient empirical evidences have shown that a minimum spanning tree representation is quite invariant to the detailed geometric changes in clusters’ boundaries. Therefore, the shape of a cluster has little impact on the performance of minimum spanning tree (MST)-based clustering algorithms, which allows us to overcome many of the problems faced by the classical clustering algorithms.
2.1 STUDY AND ANALYSIS
2.1Feasibility study
All projects are feasible given unlimited resources and infinite time. But the development of software is plagued by the scarcity of resources and difficult delivery rates. It is both necessary and prudent to evaluate the feasibility of a project at the earliest possible time.
Three key considerations are involved in the feasibility analysis.
2.1.1Economic Feasibility
This procedure is to determine the benefits and savings that are expected from a candidate system and compare them with costs. If benefits outweigh costs, then the decision is made to design and implement the system. Otherwise, further justification or alterations in proposed system will have to be made if it is to have a chance of being approved. This is an ongoing effort that improves in accuracy at each phase of the system life cycle.
2.1.2 Technical Feasibility
Technical feasibility centers on the existing computer system (hardware, software, etc.,) and to what extent it can support the proposed addition. If the budget is a serious constraint, then the project is judged not feasible.
2.1.3 Operational Feasibility
People are inherently resistant to change, and computers have been known to facilitate change. It is understandable that the introduction of a candidate system requires special effort to educate, sell, and train the staff on new ways of conducting business.
The minimum spanning trees are the spanning trees that have the minimal total weight. Two properties used to identify edges provably in an MST are the cut property and the cycle property by I. Katriel et.al. The cut property states that the edge with the smallest weight crossing any two partitions of the vertex set must belong to the MST. The cycle property states that the edge with the largest weight in any cycle in a graph cannot be in the MST. As a result, when the weight associated with each edge denotes a distance between the two end points, any edge in the minimum spanning tree will be the shortest distance between the two sub trees that are connected by that edge. Therefore, removing the longest edge will theoretically result in a two-cluster grouping. Removing the next longest edge will result in a three-cluster grouping, and so on. This corresponds to choosing the breaks where the maximum weights occur in the sorted edges.