Source Code for Module pyspark.mllib.linalg

  1  # 
  2  # Licensed to the Apache Software Foundation (ASF) under one or more 
  3  # contributor license agreements.  See the NOTICE file distributed with 
  4  # this work for additional information regarding copyright ownership. 
  5  # The ASF licenses this file to You under the Apache License, Version 2.0 
  6  # (the "License"); you may not use this file except in compliance with 
  7  # the License.  You may obtain a copy of the License at 
  8  # 
  9  #    http://www.apache.org/licenses/LICENSE-2.0 
 10  # 
 11  # Unless required by applicable law or agreed to in writing, software 
 12  # distributed under the License is distributed on an "AS IS" BASIS, 
 13  # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
 14  # See the License for the specific language governing permissions and 
 15  # limitations under the License. 
 16  # 
 17   
 18  """ 
 19  MLlib utilities for linear algebra. For dense vectors, MLlib 
 20  uses the NumPy C{array} type, so you can simply pass NumPy arrays 
 21  around. For sparse vectors, users can construct a L{SparseVector} 
 22  object from MLlib or pass SciPy C{scipy.sparse} column vectors if 
 23  SciPy is available in their environment. 
 24  """ 
 25   
 26  from numpy import array, array_equal, ndarray, float64, int32 
 27   
 28   
 29 -class SparseVector(object): 
 30      """ 
 31      A simple sparse vector class for passing data to MLlib. Users may 
 32      alternatively pass SciPy's {scipy.sparse} data types. 
 33      """ 
 34   
 35 -    def __init__(self, size, *args): 
 36          """ 
 37          Create a sparse vector, using either a dictionary, a list of 
 38          (index, value) pairs, or two separate arrays of indices and 
 39          values (sorted by index). 
 40   
 41          @param size: Size of the vector. 
 42          @param args: Non-zero entries, as a dictionary, list of tupes, 
 43                 or two sorted lists containing indices and values. 
 44   
 45          >>> print SparseVector(4, {1: 1.0, 3: 5.5}) 
 46          [1: 1.0, 3: 5.5] 
 47          >>> print SparseVector(4, [(1, 1.0), (3, 5.5)]) 
 48          [1: 1.0, 3: 5.5] 
 49          >>> print SparseVector(4, [1, 3], [1.0, 5.5]) 
 50          [1: 1.0, 3: 5.5] 
 51          """ 
 52          self.size = int(size) 
 53          assert 1 <= len(args) <= 2, "must pass either 2 or 3 arguments" 
 54          if len(args) == 1: 
 55              pairs = args[0] 
 56              if type(pairs) == dict: 
 57                  pairs = pairs.items() 
 58              pairs = sorted(pairs) 
 59              self.indices = array([p[0] for p in pairs], dtype=int32) 
 60              self.values = array([p[1] for p in pairs], dtype=float64) 
 61          else: 
 62              assert len(args[0]) == len(args[1]), "index and value arrays not same length" 
 63              self.indices = array(args[0], dtype=int32) 
 64              self.values = array(args[1], dtype=float64) 
 65              for i in xrange(len(self.indices) - 1): 
 66                  if self.indices[i] >= self.indices[i + 1]: 
 67                      raise TypeError("indices array must be sorted") 
 68   
 69 -    def dot(self, other): 
 70          """ 
 71          Dot product with a SparseVector or 1- or 2-dimensional Numpy array. 
 72   
 73          >>> a = SparseVector(4, [1, 3], [3.0, 4.0]) 
 74          >>> a.dot(a) 
 75          25.0 
 76          >>> a.dot(array([1., 2., 3., 4.])) 
 77          22.0 
 78          >>> b = SparseVector(4, [2, 4], [1.0, 2.0]) 
 79          >>> a.dot(b) 
 80          0.0 
 81          >>> a.dot(array([[1, 1], [2, 2], [3, 3], [4, 4]])) 
 82          array([ 22.,  22.]) 
 83          """ 
 84          if type(other) == ndarray: 
 85              if other.ndim == 1: 
 86                  result = 0.0 
 87                  for i in xrange(len(self.indices)): 
 88                      result += self.values[i] * other[self.indices[i]] 
 89                  return result 
 90              elif other.ndim == 2: 
 91                  results = [self.dot(other[:, i]) for i in xrange(other.shape[1])] 
 92                  return array(results) 
 93              else: 
 94                  raise Exception("Cannot call dot with %d-dimensional array" % other.ndim) 
 95          else: 
 96              result = 0.0 
 97              i, j = 0, 0 
 98              while i < len(self.indices) and j < len(other.indices): 
 99                  if self.indices[i] == other.indices[j]: 
100                      result += self.values[i] * other.values[j] 
101                      i += 1 
102                      j += 1 
103                  elif self.indices[i] < other.indices[j]: 
104                      i += 1 
105                  else: 
106                      j += 1 
107              return result 
108   
109 -    def squared_distance(self, other): 
110          """ 
111          Squared distance from a SparseVector or 1-dimensional NumPy array. 
112   
113          >>> a = SparseVector(4, [1, 3], [3.0, 4.0]) 
114          >>> a.squared_distance(a) 
115          0.0 
116          >>> a.squared_distance(array([1., 2., 3., 4.])) 
117          11.0 
118          >>> b = SparseVector(4, [2, 4], [1.0, 2.0]) 
119          >>> a.squared_distance(b) 
120          30.0 
121          >>> b.squared_distance(a) 
122          30.0 
123          """ 
124          if type(other) == ndarray: 
125              if other.ndim == 1: 
126                  result = 0.0 
127                  j = 0   # index into our own array 
128                  for i in xrange(other.shape[0]): 
129                      if j < len(self.indices) and self.indices[j] == i: 
130                          diff = self.values[j] - other[i] 
131                          result += diff * diff 
132                          j += 1 
133                      else: 
134                          result += other[i] * other[i] 
135                  return result 
136              else: 
137                  raise Exception("Cannot call squared_distance with %d-dimensional array" % 
138                                  other.ndim) 
139          else: 
140              result = 0.0 
141              i, j = 0, 0 
142              while i < len(self.indices) and j < len(other.indices): 
143                  if self.indices[i] == other.indices[j]: 
144                      diff = self.values[i] - other.values[j] 
145                      result += diff * diff 
146                      i += 1 
147                      j += 1 
148                  elif self.indices[i] < other.indices[j]: 
149                      result += self.values[i] * self.values[i] 
150                      i += 1 
151                  else: 
152                      result += other.values[j] * other.values[j] 
153                      j += 1 
154              while i < len(self.indices): 
155                  result += self.values[i] * self.values[i] 
156                  i += 1 
157              while j < len(other.indices): 
158                  result += other.values[j] * other.values[j] 
159                  j += 1 
160              return result 
161   
162 -    def __str__(self): 
163          inds = self.indices 
164          vals = self.values 
165          entries = ", ".join(["{0}: {1}".format(inds[i], vals[i]) for i in xrange(len(inds))]) 
166          return "[" + entries + "]" 
167   
168 -    def __repr__(self): 
169          inds = self.indices 
170          vals = self.values 
171          entries = ", ".join(["{0}: {1}".format(inds[i], vals[i]) for i in xrange(len(inds))]) 
172          return "SparseVector({0}, {{{1}}})".format(self.size, entries) 
173   
174 -    def __eq__(self, other): 
175          """ 
176          Test SparseVectors for equality. 
177   
178          >>> v1 = SparseVector(4, [(1, 1.0), (3, 5.5)]) 
179          >>> v2 = SparseVector(4, [(1, 1.0), (3, 5.5)]) 
180          >>> v1 == v2 
181          True 
182          >>> v1 != v2 
183          False 
184          """ 
185   
186          return (isinstance(other, self.__class__) 
187                  and other.size == self.size 
188                  and array_equal(other.indices, self.indices) 
189                  and array_equal(other.values, self.values)) 
190   
191 -    def __ne__(self, other): 
192          return not self.__eq__(other) 
193   
194   
195 -class Vectors(object): 
196      """ 
197      Factory methods for working with vectors. Note that dense vectors 
198      are simply represented as NumPy array objects, so there is no need 
199      to covert them for use in MLlib. For sparse vectors, the factory 
200      methods in this class create an MLlib-compatible type, or users 
201      can pass in SciPy's C{scipy.sparse} column vectors. 
202      """ 
203   
204      @staticmethod 
205 -    def sparse(size, *args): 
206          """ 
207          Create a sparse vector, using either a dictionary, a list of 
208          (index, value) pairs, or two separate arrays of indices and 
209          values (sorted by index). 
210   
211          @param size: Size of the vector. 
212          @param args: Non-zero entries, as a dictionary, list of tupes, 
213                       or two sorted lists containing indices and values. 
214   
215          >>> print Vectors.sparse(4, {1: 1.0, 3: 5.5}) 
216          [1: 1.0, 3: 5.5] 
217          >>> print Vectors.sparse(4, [(1, 1.0), (3, 5.5)]) 
218          [1: 1.0, 3: 5.5] 
219          >>> print Vectors.sparse(4, [1, 3], [1.0, 5.5]) 
220          [1: 1.0, 3: 5.5] 
221          """ 
222          return SparseVector(size, *args) 
223   
224      @staticmethod 
225 -    def dense(elements): 
226          """ 
227          Create a dense vector of 64-bit floats from a Python list. Always 
228          returns a NumPy array. 
229   
230          >>> Vectors.dense([1, 2, 3]) 
231          array([ 1.,  2.,  3.]) 
232          """ 
233          return array(elements, dtype=float64) 
234   
235   
236 -def _test(): 
237      import doctest 
238      (failure_count, test_count) = doctest.testmod(optionflags=doctest.ELLIPSIS) 
239      if failure_count: 
240          exit(-1) 
241   
242  if __name__ == "__main__": 
243      _test() 
244