전체 페이지뷰

레이블이 mathematics인 게시물을 표시합니다. 모든 게시물 표시
레이블이 mathematics인 게시물을 표시합니다. 모든 게시물 표시

2015년 12월 14일 월요일

Single-link and complete-link clustering

posted from :
http://nlp.stanford.edu/IR-book/html/htmledition/single-link-and-complete-link-clustering-1.html

Single-link and complete-link clustering

In single-link clustering or single-linkage clustering , the similarity of two clusters is the similarity of their most similar members (see Figure17.3 , (a))[*]. This single-link merge criterion is local. We pay attention solely to the area where the two clusters come closest to each other. Other, more distant parts of the cluster and the clusters' overall structure are not taken into account.
In complete-link clustering or complete-linkage clustering , the similarity of two clusters is the similarity of their most dissimilar members (see Figure 17.3 , (b)). This is equivalent to choosing the cluster pair whose merge has the smallest diameter. This complete-link merge criterion is non-local; the entire structure of the clustering can influence merge decisions. This results in a preference for compact clusters with small diameters over long, straggly clusters, but also causes sensitivity to outliers. A single document far from the center can increase diameters of candidate merge clusters dramatically and completely change the final clustering.


\includegraphics[width=13.5cm]{rprojectcomplete.eps} A dendrogram of a complete-link clustering.The same 30 documents were clustered with single-link clustering in Figure 17.1 .
Figure 17.4 depicts a single-link and a complete-link clustering of eight documents. The first four steps, each producing a cluster consisting of a pair of two documents, are identical. Then single-link clustering joins the upper two pairs (and after that the lower two pairs) because on the maximum-similarity definition of cluster similarity, those two clusters are closest. Complete-link clustering joins the left two pairs (and then the right two pairs) because those are the closest pairs according to the minimum-similarity definition of cluster similarity.[*]
Figure 17.1 is an example of a single-link clustering of a set of documents and Figure 17.5 is the complete-link clustering of the same set. When cutting the last merge in Figure 17.5 , we obtain two clusters of similar size (documents 1-16, from NYSE closing averages to Lloyd's chief / U.S. grilling, and documents 17-30, from Ohio Blue Cross to Clinton signs law). There is no cut of the dendrogram in Figure 17.1 that would give us an equally balanced clustering.
Both single-link and complete-link clustering have graph-theoretic interpretations. Define $s_k$ to be the combination similarity of the two clusters merged in step $k$, and $G(s_k)$ the graph that links all data points with a similarity of at least $s_k$. Then the clusters after step $k$ in single-link clustering are the connected components of $G(s_k)$ and the clusters after step $k$ in complete-link clustering are maximal cliques of$G(s_k)$. A connected component is a maximal set of connected points such that there is a path connecting each pair. A clique is a set of points that are completely linked with each other.
These graph-theoretic interpretations motivate the terms single-link and complete-link clustering. Single-link clusters at step $k$ are maximal sets of points that are linked via at least one link (a single link) of similarity $s \geq s_k$; complete-link clusters at step $k$ are maximal sets of points that are completely linked with each other via links of similarity $s \geq s_k$.


\begin{figure}
% latex2html id marker 26560
\par
\psset{unit=0.5cm}
\par
\begin{...
...n single-link clustering can cause undesirable
elongated clusters.}
\end{figure}
Single-link and complete-link clustering reduce the assessment of cluster quality to a single similarity between a pair of documents: the two most similar documents in single-link clustering and the two most dissimilar documents in complete-link clustering. A measurement based on one pair cannot fully reflect the distribution of documents in a cluster. It is therefore not surprising that both algorithms often produce undesirable clusters. Single-link clustering can produce straggling clusters as shown in Figure 17.6 . Since the merge criterion is strictly local, a chain of points can be extended for long distances without regard to the overall shape of the emerging cluster. This effect is calledchaining .
The chaining effect is also apparent in Figure 17.1 . The last eleven merges of the single-link clustering (those above the $0.1$ line) add on single documents or pairs of documents, corresponding to a chain. The complete-link clustering in Figure 17.5 avoids this problem. Documents are split into two groups of roughly equal size when we cut the dendrogram at the last merge. In general, this is a more useful organization of the data than a clustering with chains.


\begin{figure}
% latex2html id marker 26574
\par
\psset{unit=0.5cm}
\par
\begin{...
...tering, the outlier $d_1$\ splits
$\{d_2,d_3,d_4,d_5\}$\ as shown.}
\end{figure}
However, complete-link clustering suffers from a different problem. It pays too much attention to outliers, points that do not fit well into the global structure of the cluster. In the example in Figure 17.7 the four documents $d_2, d_3, d_4, d_5$ are split because of the outlier $d_1$ at the left edge (Exercise 17.2.1 ). Complete-link clustering does not find the most intuitive cluster structure in this example.

2015년 12월 11일 금요일

Recommending Items

programming collective intelligent

https://github.com/hasun/ProgrammingCI

/**
 * Created by ts-jounghasun on 2015-12-11.
 */
public class Ch02Ranking {
//    # Gets recommendations for a person by using a weighted average
//    # of every other user's rankings
//    def getRecommendations(prefs,person,similarity=sim_pearson):
//    totals={}
//    simSums={}
//    for other in prefs:
//            # don't compare me to myself
//            if other==person: continue
//    sim=similarity(prefs,person,other)
//    # ignore scores of zero or lower
//    if sim<=0: continue
//            for item in prefs[other]:
//            # only score movies I haven't seen yet
//            if item not in prefs[person] or prefs[person][item]==0:
//            # Similarity * Score
//    totals.setdefault(item,0)
//    totals[item]+=prefs[other][item]*sim
//    # Sum of similarities
//    simSums.setdefault(item,0)
//    simSums[item]+=sim
//    # Create the normalized list
//    rankings=[(total/simSums[item],item) for item,total in totals.items( )]
//            # Return the sorted list
//    rankings.sort( )
//            rankings.reverse( )
//            return rankings
    public double getRecommendation (Map<String,Map<String,Double>> data , String person, Ch02Similarity similarity) {
        Map <String ,Double> totals = new HashMap<>();
        Map <String ,Double> simSums = new HashMap<>();
        for (Map.Entry <String,Map <String ,Double>> item : data.entrySet()){
            if (person.equals(item.getKey())){
                continue;
            }else {
                String otherP = item.getKey();
                double sim = similarity.getSimilarity(data, person, otherP);
                if (sim <= 0 ) continue;
                Map <String ,Double> othersPrefs = item.getValue();
//                # only score movies I haven't seen yet
                for (Map.Entry<String, Double> prefs  : othersPrefs.entrySet()) {
//                    if item not in prefs[person] or prefs[person][item]==0:
                    if (!data.get(person).containsKey(prefs.getKey()) || data.get(person).get(prefs.getKey())==0) {
                        double simS = 0 ;
                        double simS2 = 0;
                        if (!totals.containsKey(prefs.getKey())){
                            totals.put(prefs.getKey() , 0d);
                            simS = totals.get(prefs.getKey());
                            simS += prefs.getValue()*sim ;
                            totals.put(prefs.getKey() , simS);
                        }else {
                            simS = totals.get(prefs.getKey());
                            simS += prefs.getValue()*sim ;
                            totals.put(prefs.getKey() , simS);
                        }
                        if(!simSums.containsKey(prefs.getKey())){
                            simSums.put(prefs.getKey(),0d);
                            simS2 = simSums.get(prefs.getKey());
                            simS2 += sim ;
                            simSums.put(prefs.getKey() , simS2);
                        }else {
                            simS2 = simSums.get(prefs.getKey());
                            simS2 += sim ;
                            simSums.put(prefs.getKey() , simS2);
                        }
                    }
                }
            }
        }
        Map <String ,Double> rankings = new HashMap<>();
        for (Map.Entry<String, Double> totalItem  : totals.entrySet()) {
            rankings.put(totalItem.getKey() ,totalItem.getValue()/simSums.get(totalItem.getKey()));
        }
        System.out.print(rankings);
        return 0;
    }
//    def topMatches(prefs,person,n=5,similarity=sim_pearson):
//    scores=[(similarity(prefs,person,other),other)
//            for other in prefs if other!=person]
    public void topMatches (Map<String,Map<String,Double>> data ,String person , int num , Ch02Similarity similarity) {
        Map <String , Double> scores = new HashMap <String , Double>();
        for (Map.Entry <String,Map <String ,Double>> item : data.entrySet()) {
            if (person.equals(item.getKey())) {
                continue;
            } else {
                String otherP = item.getKey();
                double sim = similarity.getSimilarity(data, person, otherP);
                scores.put(otherP ,sim);
            }
        }
        scores = sortByValue(scores);
        System.out.println(scores);
    }
    public static <K, V extends Comparable <? super V>> Map<K, V> sortByValue( Map<K, V> map )
    {
        List<Map.Entry<K, V>> list = new LinkedList<Map.Entry<K, V>>( map.entrySet() );
        Collections.sort(list, new Comparator<Map.Entry<K, V>>() {
            public int compare(Map.Entry<K, V> o1, Map.Entry<K, V> o2) {
                return -(o1.getValue()).compareTo(o2.getValue());
            }
        });
        Map<K, V> result = new LinkedHashMap<K, V>();
        for (Map.Entry<K, V> entry : list)
        {
            result.put( entry.getKey(), entry.getValue() );
        }
        return result;
    }
}
cs

2015년 12월 9일 수요일

Pearson's correlation

Definition[edit]

Pearson's correlation coefficient is the covariance of the two variables divided by the product of their standard deviations. The form of the definition involves a "product moment", that is, the mean (the first moment about the origin) of the product of the mean-adjusted random variables; hence the modifier product-moment in the name.

For a population[edit]

Pearson's correlation coefficient when applied to a population is commonly represented by the Greek letter ρ (rho) and may be referred to as the population correlation coefficient or the population Pearson correlation coefficient. The formula for ρ[7] is:
 \rho_{X,Y}= \frac{\operatorname{cov}(X,Y)}{\sigma_X \sigma_Y}
where:
The formula for ρ can be expressed in terms of mean and expectation. Since
Then the formula for ρ can also be written as
 \rho_{X,Y}=\frac{\operatorname{E}[(X-\mu_X)(Y-\mu_Y)]}{\sigma_X\sigma_Y}
where:
  •  \operatorname{cov}  and  \sigma_X  are defined as above
  •  \mu_X  is the mean of  X
  •  \operatorname{E}  is the expectation.
The formula for ρ can be expressed in terms of uncentered moments. Since
  • \mu_X=\operatorname{E}[X]
  • \mu_Y=\operatorname{E}[Y]
  • \sigma_X^2=\operatorname{E}[(X-\operatorname{E}[X])^2]=\operatorname{E}[X^2]-\operatorname{E}[X]^2
  • \sigma_Y^2=\operatorname{E}[(Y-\operatorname{E}[Y])^2]=\operatorname{E}[Y^2]-\operatorname{E}[Y]^2
  • \operatorname{E}[(X-\mu_X)(Y-\mu_Y)]=\operatorname{E}[(X-\operatorname{E}[X])(Y-\operatorname{E}[Y])]=\operatorname{E}[XY]-\operatorname{E}[X]\operatorname{E}[Y],\,
Then the formula for ρ can also be written as
\rho_{X,Y}=\frac{\operatorname{E}[XY]-\operatorname{E}[X]\operatorname{E}[Y]}{\sqrt{\operatorname{E}[X^2]-\operatorname{E}[X]^2}~\sqrt{\operatorname{E}[Y^2]- \operatorname{E}[Y]^2}}.

For a sample[edit]

Pearson's correlation coefficient when applied to a sample is commonly represented by the letter r and may be referred to as the sample correlation coefficient or the sample Pearson correlation coefficient. We can obtain a formula for r by substituting estimates of the covariances and variances based on a sample into the formula above. So if we have one dataset {x1,...,xn} containing n values and another dataset {y1,...,yn} containing n values then that formula for r is:
r = r_{xy} =\frac{\sum ^n _{i=1}(x_i - \bar{x})(y_i - \bar{y})}{\sqrt{\sum ^n _{i=1}(x_i - \bar{x})^2} \sqrt{\sum ^n _{i=1}(y_i - \bar{y})^2}}
where:
  • n, x_i, y_i are defined as above
  • \bar{x}=\frac{1}{n}\sum_{i=1}^n x_i (the sample mean); and analogously for \bar{y}
Rearranging gives us this formula for r:
r = r_{xy} =\frac{n\sum x_iy_i-\sum x_i\sum y_i}
{\sqrt{n\sum x_i^2-(\sum x_i)^2}~\sqrt{n\sum y_i^2-(\sum y_i)^2}}.
where:
  • n, x_i, y_i are defined as above
  • This formula suggests a convenient single-pass algorithm for calculating sample correlations, but, depending on the numbers involved, it can sometimes be numerically unstable.
Rearranging again gives us this[7] formula for r:
r = r_{xy} =\frac{\sum x_iy_i-n\bar{x}\bar{y}}
{\sqrt{(\sum x_i^2-n\bar{x}^2)}~\sqrt{(\sum y_i^2-n\bar{y}^2)}}.
where:
  • n, x_i, y_i, \bar{x}, \bar{y} are defined as above
An equivalent expression gives the formula for r as the mean of the products of the standard scores as follows:
r = r_{xy} =\frac{1}{n-1} \sum ^n _{i=1} \left( \frac{x_i - \bar{x}}{s_x} \right) \left( \frac{y_i - \bar{y}}{s_y} \right)
where
  • n, x_i, y_i, \bar{x}, \bar{y} are defined as above, and s_x, s_y are defined below
  • \left( \frac{x_i - \bar{x}}{s_x} \right) is the standard score (and analogously for the standard score of y)
Alternative formulae for r are also available. One can use the following formula for r:
r = r_{xy} =\frac{\sum x_iy_i-n \bar{x} \bar{y}}{(n-1) s_x s_y}
where:




Algorithms.of.the.Intelligent.Web 

private static final double ZERO = 0.0d;
    
    int n;
    
    double[] x;
    double[] y;
    
    public PearsonCorrelation(Dataset ds, Item iA, Item iB) {
        
        double aAvgR = iA.getAverageRating();
        double bAvgR = iB.getAverageRating();
        
        Integer[] uid = Item.getSharedUserIds(iA, iB);
        n = uid.length;
        x = new double[n];
        y = new double[n];
        
        User u;
        double urA=0;
        double urB=0;
        
        for (int i=0; i<n; i++) {
            
            u = ds.getUser(uid[i]);
            urA = u.getItemRating(iA.getId()).getRating();
            urB = u.getItemRating(iB.getId()).getRating();
            
            x[i] = urA - aAvgR;
            y[i] = urB - bAvgR;
        }
    }
    
    public PearsonCorrelation(double[] x, double[] y) throws java.lang.IllegalArgumentException {
        
        if (x.length != y.length) {
            throw new IllegalArgumentException("Arrays x and y should have the same length!");
        }
    
        n = x.length;
        //System.out.print("N="+n);
        
        this.x = x;
        this.y = y;
    }
    
    public double calculate() {
        
        if( n == 0) {
            return 0.0;
        }
        
        double rho=0.0d;
        
        double avgX = getAverage(x);
        double avgY = getAverage(y);
        
        double sX = getStdDev(avgX,x);
        double sY = getStdDev(avgY,y);
        
        double xy=0;
        
        for (int i=0; i < n; i++) {
        
            xy += (x[i]-avgX)*(y[i]-avgY);
        }
        //No variation -- all points have the same values for either X or Y or both
        if( sX == ZERO || sY == ZERO) {
            
            double indX = ZERO;
            double indY = ZERO;
            
            for (int i=1; i < n; i++) {
                
                indX += (x[0]-x[i]);
                indY += (y[0]-y[i]); 
            }
                        
            if (indX == ZERO && indY == ZERO) {
                // All points refer to the same value
                // This is a degenerate case of correlation
                return 1.0;
            } else {
                //Either the values of the X vary or the values of Y
                if (sX == ZERO) {
                    sX = sY;
                } else {
                    sY = sX;
                }
            }
        }
                
        rho = xy / (n*(sX*sY));
        
        return rho;
    }
    private double getAverage(double[] v) {
        double avg=0;
        
        for (double xi : v ) {
            avg += xi;
        }
        
        avg = avg/v.length;
        
        //System.out.print("Average: "+avg);
        return avg;
    }
    
    private double getStdDev(double m, double[] v) {
        double sigma=0;
        
        for (double xi : v ) {
            sigma += (xi - m)*(xi - m);
        }
        
        sigma = sigma / v.length;
        
        //System.out.print("StdDev: "+Math.sqrt(sigma));
        return Math.sqrt(sigma);
    }
cs

Programming Collective Intelligence 

public double sim_pearson (Map < String, Map < String, Double >> personalRate, String person1, String person2) {
        Map<String, Double> Si = new HashMap<String, Double>();
        double result = 0;
        double sumP1 = 0;
        double sumP2 = 0;
        double sumP1Sq = 0 ;
        double sumP2Sq = 0 ;
        double pSum = 0;
        double pScore = 0 ;
        double num = 0;
        double den = 0 ;
        for (Map.Entry<String, Double> item : personalRate.get(person1).entrySet()) {
            for (Map.Entry<String, Double> item2 : personalRate.get(person2).entrySet()) {
                if (item.getKey().equals(item2.getKey())) {
                    Si.put(item.getKey(), 1.0);
                }
            }
        }
        for ( Map.Entry<String,Double> matchedItem : Si.entrySet()) {
            sumP1 += personalRate.get(person1).get(matchedItem.getKey());
            sumP2 += personalRate.get(person2).get(matchedItem.getKey());
            sumP1Sq += Math.pow(personalRate.get(person1).get(matchedItem.getKey()), 2);
            sumP2Sq += Math.pow(personalRate.get(person2).get(matchedItem.getKey()), 2);
            pSum += (personalRate.get(person1).get(matchedItem.getKey())*personalRate.get(person2).get(matchedItem.getKey()));
        }
        num = pSum-(sumP1*sumP2/Si.size());
        den = Math.sqrt((sumP1Sq - Math.pow(sumP1 ,2)/Si.size())*(sumP2Sq - Math.pow(sumP2, 2)/Si.size()));
        if (den==0) result = 0;
        else result = num/den;
        return result;
    }
cs