Complete problems 13-20 in section 2.6 of your textbook.

4. 4: return the objects associated with the first k distances of the sorted list

5. 5: end for

13. 13. Consider the problem of finding the K-nearest neighbors of a data object. A programmer designs Algorithm 2.3 for this task.

1. Describe the potential problems with this algorithm if there are duplicate objects in the data set. Assume the distance function will return a distance of 0 only for objects that are the same.

2. How would you fix this problem?

14. 14. The following attributes are measured for members of a herd of Asian elephants: weight, height, tusk length, trunk length, and ear area. Based on these measurements, what sort of proximity measure from Section 2.4 would you use to compare or group these elephants? Justify your answer and explain any special circumstances.

15. 15. You are given a set of m objects that is divided into k groups, where the ith group is of size mi. If the goal is to obtain a sample of size n<m, what is the difference between the following two sampling schemes? (Assume sampling with replacement.)

1. We randomly select n×mi/m elements from each group.

2. We randomly select n elements from the data set, without regard for the group to which an object belongs.

16. 16. Consider a document-term matrix, where tfij is the frequency of the ith word (term) in the jth document and m is the number of documents. Consider the variable transformation that is defined by

tfij′=tfij×logmdfi, (2.31)

where dfi is the number of documents in which the ith term appears, which is known as the document frequency of the term. This

transformation is known as the inverse document frequency transformation.

1. What is the effect of this transformation if a term occurs in one document? In every document?

2. What might be the purpose of this transformation?

17. 17. Assume that we apply a square root transformation to a ratio attribute x to obtain the new attribute x*. As part of your analysis, you identify an interval (a, b) in which x* has a linear relationship to another attributey.

1. What is the corresponding interval (A, B) in terms of x ?

2. Give an equation that relates y to x.

18. 18. This exercise compares and contrasts some similarity and distance measures.

1. For binary data, the L1 distance corresponds to the Hamming distance; that is, the number of bits that are different between two binary vectors. The Jaccard similarity is a measure of the similarity between two binary vectors. Compute the Hamming distance and the Jaccard similarity between the following two binary vectors.

x=0101010001y=0100011000

2. Which approach, Jaccard or Hamming distance, is more similar to the Simple Matching Coefficient, and which approach is more similar to the cosine measure? Explain. (Note: The Hamming measure is a distance, while the other three measures are similarities, but don’t let this confuse you.)

3. Suppose that you are comparing how similar two organisms of different species are in terms of the number of genes they share. Describe which measure, Hamming or Jaccard, you think would be more appropriate for comparing the genetic makeup of two

organisms. Explain. (Assume that each animal is represented as a binary vector, where each attribute is 1 if a particular gene is present in the organism and 0 otherwise.)

4. If you wanted to compare the genetic makeup of two organisms of the same species, e.g., two human beings, would you use the Hamming distance, the Jaccard coefficient, or a different measure of similarity or distance? Explain. (Note that two human beings share >99.9% of the same genes.)

19. 19. For the following vectors, x and y, calculate the indicated similarity or distance measures.

1. x=(1, 1, 1, 1), y=(2, 2, 2, 2) cosine, correlation, Euclidean

2. x=(0, 1, 0, 1), y=(1, 0, 1, 0) cosine, correlation, Euclidean, Jaccard

3. x=(0, −1, 0, 1), y=(1, 0, −1, 0) cosine, correlation, Euclidean

4. x=(1, 1, 0, 1, 0, 1), y=(1, 1, 1, 0, 0, 1) cosine, correlation, Jaccard

5. x=(2, −1, 0, 2, 0, −3), y=( −1, 1, −1, 0, 0, −1) cosine, correlation

20. 20. Here, we further explore the cosine and correlation measures.

1. What is the range of values possible for the cosine measure?

2. If two objects have a cosine measure of 1, are they identical? Explain.

3. What is the relationship of the cosine measure to correlation, if any? (Hint: Look at statistical measures such as mean and standard deviation in cases where cosine and correlation are the same and different.)

4. Figure 2.22(a) shows the relationship of the cosine measure to Euclidean distance for 100,000 randomly generated points that have been normalized to have an L2 length of 1. What general observation can you make about the relationship between

Euclidean distance and cosine similarity when vectors have an L2 norm of 1?

Figure 2.22. Graphs for Exercise 20.

Figure 2.22. Full Alternative Text

5. Figure 2.22(b) shows the relationship of correlation to Euclidean distance for 100,000 randomly generated points that have been standardized to have a mean of 0 and a standard deviation of 1. What general observation can you make about the relationship between Euclidean distance and correlation when the vectors have been standardized to have a mean of 0 and a standard deviation of 1?

6. Derive the mathematical relationship between cosine similarity and Euclidean distance when each data object has an L2 length of 1.

7. Derive the mathematical relationship between correlation and Euclidean distance when each data point has been been standardized by subtracting its mean and dividing by its standard deviation.

21. 21. Show that the set difference metric given by

d(A, B)=size(A−B)+size(B−A) (2.32)

satisfies the metric axioms given on page 77. A and B are sets and A−B is the set difference.

22. 22. Discuss how you might map correlation values from the interval [−1, 1] to the interval [0, 1]. Note that the type of transformation that you use might depend on the application that you have in mind. Thus, consider two applications: clustering time series and predicting the behavior of one time series given another.

23. 23. Given a similarity measure with values in the interval [0, 1], describe two ways to transform this similarity value into a dissimilarity value in the interval [0, ∞].

24. 24. Proximity is typically defined between a pair of objects.

1. Define two ways in which you might define the proximity among a group of objects.

2. How might you define the distance between two sets of points in Euclidean space?

3. How might you define the proximity between two sets of data objects? (Make no assumption about the data objects, except that a proximity measure is defined between any pair of objects.)

25. 25. You are given a set of points s in Euclidean space, as well as the distance of each point in s to a point x. (It does not matter if x∈S.)

1. If the goal is to find all points within a specified distance ε of point y, y≠x, explain how you could use the triangle inequality and the