We experimentally study anomalous diffusion of ultra-cold atoms in a one dimensional polarization optical lattice. The atomic spatial distribution is recorded at different times and its dynamics and shape is analyzed. We find that the width of the cloud exhibits a power-law time dependence with an exponent that depends on the lattice depth. Moreover, the distribution exhibits fractional self-similarity with the same characteristic exponent. The self-similar shape of the distribution is found to be well fitted by a Levy distribution, but with a characteristic exponent that differs from the temporal one. Numerical simulations suggest that this is due to long trapping times in the lattice and correlations between the atom's velocity and flight duration.