001    /*
002     * Copyright (c) 1998-2014 ChemAxon Ltd. All Rights Reserved.
003     *
004     * This software is the confidential and proprietary information of
005     * ChemAxon. You shall not disclose such Confidential Information
006     * and shall use it only in accordance with the terms of the agreements
007     * you entered into with ChemAxon.
008     *
009     */
010    
011    package com.chemaxon.clustering.wards;
012    
013    import com.chemaxon.common.annotations.PublicAPI;
014    import com.google.common.annotations.Beta;
015    
016    /**
017     * Singleton instances of various cluster merge operations.
018     *
019     * <p>Please note that this class is marked with @Beta annotation, so it can be subject of incompatible changes or
020     * removal in later releases.</p>
021     *
022     * @see LanceWilliamsAlgorithm
023     *
024     * @author Gabor Imre
025     */
026    @Beta
027    @PublicAPI
028    public class LanceWilliamsMerges {
029    
030        /**
031         * Ward's minimum variance clustering.
032         *
033         * @see <a href="en.wikipedia.org/wiki/Ward's_method">en.wikipedia.org/wiki/Ward's_method</a>
034         */
035        public static class Wards implements LanceWilliamsMerge {
036    
037            @Override
038            public double dijk(int ni, int nj, int nk, double dij, double dik, double djk) {
039                final double nijk = ni + nj + nk;
040                return ((ni + nk) * dik + (nj + nk) * djk - nk * dij) / nijk;
041            }
042    
043            @Override
044            public String toString() {
045                return "Ward's minumum variance clustering";
046            }
047        }
048    
049        /**
050         * Single linkage clustering also known as nearest neighbor clustering.
051         *
052         * @see <a href="http://en.wikipedia.org/wiki/Single-linkage_clustering">http://en.wikipedia.org/wiki/Single-linkage_clustering</a>
053         */
054        public static class SingleLinkage implements LanceWilliamsMerge {
055    
056            @Override
057            public double dijk(int ni, int nj, int nk, double dij, double dik, double djk) {
058                return Math.min(dik, djk);
059            }
060    
061            @Override
062            public String toString() {
063                return "Single linkage/nearest neighbor clustering";
064            }
065        }
066    
067        /**
068         * Complete linkage clustering, also known as farthest neighbor clustering.
069         *
070         * @see <a href="http://en.wikipedia.org/wiki/Complete-linkage_clustering">http://en.wikipedia.org/wiki/Complete-linkage_clustering</a>
071         */
072        public static class CompleteLinkage implements LanceWilliamsMerge {
073    
074            @Override
075            public double dijk(int ni, int nj, int nk, double dij, double dik, double djk) {
076                return Math.max(dik, djk);
077            }
078    
079            @Override
080            public String toString() {
081                return "Complete linkage/farthest neighbor clustering";
082            }
083    
084        }
085    
086        /**
087         * Average linkage clustering, also known as UPGMA.
088         *
089         * @see <a href ="http://en.wikipedia.org/wiki/UPGMA">http://en.wikipedia.org/wiki/UPGMA</a>
090         */
091        public static class AverageLinkage implements LanceWilliamsMerge {
092    
093            @Override
094            public double dijk(int ni, int nj, int nk, double dij, double dik, double djk) {
095                return (dik * ni + djk * nj) / (ni + nj);
096            }
097    
098            @Override
099            public String toString() {
100                return "Average linkage clustering";
101            }
102    
103        }
104    }