Foundations of Data Science

《Foundations of Data Science》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、FoundationsofDataScience1JohnHopcroftRavindranKannanVersion21/8/2014ThesenotesarearstdraftofabookbeingwrittenbyHopcroftandKannanandinmanyplacesareincomplete.However,thenotesareingoodenoughshapetopreparelecturesforamoderntheoreticalcourseincomputerscience.Pleasedonotputsolutionstoexercisesonl

2、ineasitisimportantforstudentstoworkoutsolutionsforthemselvesratherthancopythemfromtheinternet.ThanksJEH1Copyright2011.Allrightsreserved1Contents1Introduction72High-DimensionalSpace102.1PropertiesofHigh-DimensionalSpace.....................122.2TheLawofLargeNumbers..........................132

3、.3TheHigh-DimensionalSphere.........................152.3.1TheSphereandtheCubeinHighDimensions............162.3.2VolumeandSurfaceAreaoftheUnitSphere.............172.3.3TheVolumeisNeartheEquator...................202.3.4TheVolumeisinaNarrowAnnulus..................232.3.5TheSurfaceAreaisNearth

4、eEquator................242.4VolumesofOtherSolids............................262.5GeneratingPointsUniformlyatRandomontheSurfaceofaSphere....272.6GaussiansinHighDimension.........................272.7BoundsonTailProbability...........................332.8Applicationsofthetailbound.............

5、............352.9RandomProjectionandJohnson-LindenstraussTheorem..........382.10BibliographicNotes...............................412.11Exercises.....................................423Best-FitSubspacesandSingularValueDecomposition(SVD)523.1SingularVectors.................................533.2

6、SingularValueDecomposition(SVD).....................563.3BestRankkApproximations.........................583.4LeftSingularVectors..............................603.5PowerMethodforComputingtheSingularValueDecomposition......623.6ApplicationsofSingularValueDecomposition................643.6.1Pri

7、ncipalComponentAnalysis.....................643.6.2ClusteringaMixtureofSphericalGaussians.............653.6.3SpectralDecomposition........................713.6.4SingularVectorsandRankingDocuments..............713.6.5AnApplicationofSVDtoaDiscr