北京交通大学-《大数据》结题报告

目录TOC\o"1-5"\h\z\o"CurrentDocument"一、 晨光数据的收集、数据格式预处理 2二、 相似项发现 3\o"CurrentDocument"电影需求的矩阵表示 3\o"CurrentDocument"最小哈希签名矩阵 5\o"CurrentDocument"用LSH求jaccard距离 9三、 降维 16四、 频繁项集 21\o"CurrentDocument"五、 聚类 27\o"CurrentDocument"六、 电影推荐算法 33\o"CurrentDocument"七、 SVM分类器 48\o"CurrentDocument"八、 总结 57大数据实验报告 基于matlab和visioC++6.0编程#据此求出二（最优解，算法另述）后：l l亦八yai*Xib*二yj “区Xj）y i£说明：线性支持向量机是基于最大间隔法的。该问题是一个二次规划问题，使用拉格朗日函数合并优化问题和约束，再使用对偶理论，得到上述的分类优化问题。需要注意的是，该问题仍然是一个有约束的最优化问题。5、线性不可分问题（1）线性软间隔分类机基本思路：由于样本线性不可分，原来对间隔的要求不能达到。引入松弛变量 E“使约束条件弱化为：yi（（wXi）b） i。但是，我们仍然希望该松弛变量 Ei最小化TOC\o"1-5"\h\z（如果Ei=0，则就是原线性硬间隔分类机）。于是，在优化目标函数中使用惩罚参数 C来引入对Ei最小化的目标。这样，该分类机的模型为：分类面：(wx)b=0.要求：minw,b1矿c「2 i1styi((wxjb)1)一1-JJ,1以此为原问题，其对偶问题为:TOC\o"1-5"\h\zmin Z*yiWcti(XjX)—送«,,oto ..52iz!j=1 j=1l<s.t Zyg=0i=1\o"CurrentDocument"0 <Cl l***w=SyiaiXi,b=yj-Zyq(XiXj)i：1 i=1⑵非线性硬间隔分类机（X），则高维空间中的线性（X），则高维空间中的线性经这种映射后，在高维空间中是线性可分的。设映射为:支持向量机模型为：分类面：(wx)F=0.要求：TOC\o"1-5"\h\z1ll lmin1二二%丫厂「j((xj「(Xj)) j,a2yj# jmlst为y^i=0i=1需要注意的是，由于数据被映射到高维空间， (xi)(xj)的计算量比XiXj大得多。此时引入了所谓“核函数”：K(Xi,Xj)»(xj(Xj)由上式可见，核函数的作用是，在将X映射到高维空间的同时，也计算了两个数据的在高维空间的内积，使计算量回归到 XiXj的量级。非线性软间隔分类机(C-支持向量分类机)非线性硬间隔分类机虽然将训练数据映射到高维空间中， 但核函数的选择只有几种，它们并不能保证在任何情况下都可以将训练数据映射到足够高的维度， 以使它们成为线性可分的。因此，有理由在此基础上引入线性软间隔分类机中的松弛变量。这样，原问题为：映射：T二{(Xi,yJ,(Xi,y)}其中：Xj二(Xi)分类面：(wx)b=0.1•21.min-|w+C迟勺,w,b 2 js.t yi((W”X；)+b)+1)釘工，i=1,…,l其对偶问题为：'1111min Z%丫严厲《化內)—送c(j,E2yj二 jl<s.t Zyq=00EctiEClb*=yj y「「K(Xi,Xj)i住f(x)二sgn i*yiK(x,xjb*这种支持向量机是最常用的。v-支持向量机分类机C—支持向量机中的惩罚参数 C难以选取。选择大的C是强调最小化训练错误；选择较小的C是强调最大化分类间隔。v-支持向量机分类机的原始问题：121职n 2w“s.t yi((w*)+b)AP乂,-0,i=1, ,1t_0其对偶问题为：'111min—瓦无％丫)8旳《化*),G2亠4ls.t Zyq=0i410兰ctj<lZ«i>VIy*11*b iyiK(xi,xj)K(xi,xk),j一个正类样本，k一个负类样本i=1(1**\f(x)二sgn忙iyK(x,x)b丿【设计理由】分类的方法有四种：感知机、 SVM支持向量机、最近邻和决策树。感知机只要是线性可分割，就会收敛，如果不是的话，最后会震荡，无限循环；且特征多的话，效果一般，所以不适合。 SVM的目的是寻找最佳的线性分割，最佳分割平面由支持向量决定，能线性分割时可使用最优化； 不能线性分割时则引入了惩罚因子， 利用梯度下降法通过多次循环，求得一次近似的最优解。所以选择 SVM分类器。【详细步骤，每一步的结果】（1）载入聚类结果：最后一列表示该向量所属类别号00:0000100L0000100r00002100000500I 0000400r00001000000100r0000100000010001001（2）调用程序进行分类clear;%清屏clc;X=xlsread('jieguo.xlsx');n=length(X);%总样本数量y=X(:,49);%类别标志X=X(:,1:48);TOL=0.0001;%精度要求C=1;%参数，对损失函数的权重b=0;%初始设置截距bWold=0;%未更新a时的W(a)Wnew=0;%更新a后的W(a)fori=1:1000%设置类别标志为1或者-1y(i)=-1;enda=zeros(n,1);%参数afori=1:n%随机初始化a,a属于[0,C]a(i)=0.2;end%为简化计算，减少重复计算进行的计算K=ones(n,n);fori=1:n%求出K矩阵，便于之后的计算forj=1:nK(i,j)=k(X(i,:),X(j,:));endendsum=zeros(n,1);%中间变量，便于之后的计算， sum(k)=sigmaa(i)*y(i)*K(k,i);fork=1:nfori=1:nsum(k)=sum(k)+a(i)*y(i)*K(i,k);endendwhile1%迭代过程%启发式选点n1=1;%初始化，n1,n2代表选择的2个点n2=2;%n1按照第一个违反KKT条件的点选择whilen1<=nify(n1)*(sum(n1)+b)==1&&a(n1)>=C&&a(n1)<= 0break;endify(n1)*(sum(n1)+b)>1&&a(n1)~= 0break;endify(n1)*(sum(n1)+b)<1&&a(n1)~=Cbreak;endn1=n1+1;end%n2按照最大化|E1-E2|的原则选取E1=0;E2=0;maxDiff=0;%假设的最大误差E1=sum(n1)+b-y(n1);%n1的误差fori=1:ntempSum=sum(i)+b-y(i);ifabs(E1-tempSum)>maxDiffmaxDiff=abs(E1-tempSum);n2=i;E2=tempSum;endend%以下进行更新a1old=a(n1);a2old=a(n2);KK=K(n1,n1)+K(n2,n2)-2*K(n1,n2);a2new=a2old+y(n2)*(E1-E2)/KK;%计算新的a2%a2必须满足约束条件S=y(n1)*y(n2);ifS==-1U=max(0,a2old-a1old);=min(C,C-a1old+a2old);elseU=max(0,a1old+a2old-C);=min(C,a1old+a2old);endifa2new>Va2new=V;endifa2new<Ua2new=U;enda1new=a1old+S*(a2old-a2new);%计算新的a1a(n1)=alnew;%更新aa(n2)=a2new;%更新部分值sum=zeros(n,1);fork=1:nfori=1:nsum(k)=sum(k)+a(i)*y(i)*K(i,k);endendWold=Wnew;Wnew=0;%更新a后的W(a)tempSum=0;%临时变量fori=1:nforj=1:ntempSum=tempSum+y(i)*y(j)*a(i)*a(j)*K(i,j);endWnew=Wnew+a(i);endWnew=Wnew-0.5*tempSum;%以下更新b:通过找到某一个支持向量来计算support=1;%支持向量坐标初始化whileabs(a(support))<1e-4&&support<=nsupport=support+1;endb=1/y(support)-sum(support);%判断停止条件ifabs(Wnew/Wold-1)<=TOLbreak;endend%输出结果:包括原分类，辨别函数计算结果， svm分类结果fori=1:nfprintf('第%d点:原标号’,i);ifi<=1000fprintf('-1');elsefprintf('1');endfprintf('判别函数值%f分类结果',sum(i)+b);ifabs(sum(i)+b-1)<0.5fprintf('1\n');elseifabs(sum(i)+b+1)<0.5fprintf('-1\n');elsefprintf('归类错误\n');end

endendend【结论】，进行分类判别后如果和之前，分类结果如下：设定前0.5*总数个点的原标号为-1，后一半的原标号为1，进行分类判别后如果和之前，分类结果如下：案工自.標咗兰-1逍割sfea-1-ooc-&M打理迭杲-L菜2点：理标号-1判别雷■HF宝042343籌m点；!ftiS号-1到剧鬲蠡hl.呼宓片奏苣采-】篥4.虜..球〒弩-1捌S!leefcH-4e.140254第请：原环号判G^sia井弄W具.三尖适谓第石点：岸标号-1判制馬憩值-出.Eoaim甘类结果扫矣常谍第「產.原吁寺"I刿捌£&&-1.000000号-1事些点：揖标号-1判盘丙數ffibl.OOKOO分实结果-1薫dC.E:眾恆号-1M^Eg^tiL-45.&42343挥红栋諒标号-1乱是工盎直-45S42243第語晟原标号-1袴别甫魏值r.GW0W第垢虎：厘梧号-1tWODOD甘类證黑-1第鼻点一更悵兰-1迪狂歪磁ti-丄一&OMWO分矣些±T期呻点：肆椁号-1二.号一芷艺恒弋二.4516:5片笑茎杲.m矣呈谆籌活点；犀标号-：-旨^■：■□--'-:n第灯点：屋标号-1则臣匣若ti-制.7^757第注点：厚拆号-：之昱芜急恒-£吕.時三昭2第誨点：愿标写~1判别西敕也一斗瓦84*3^3片殳结果勺真磁法聲阴点:W*S*-i赴密更宜说”肥.H26C5分尝纯邹白莹著哄第証豪县咨兰-1之是圣惡tl-狛.T44-3S4第22点:厚输^号~1*割函®fiL-l.OMXXJO分臺煙昊・】第23点二JSW号-1171269孑癸選具匀宾遷逼第附点:J1掾号-TL捌刖圖蠱疽TH6B41B1上尝卷理.：=矣罡送第曲点:犀择号-：^Sftti.~7C-S59Z43打琵结杲严宗釜谍第茄弓焉巧吞—.<<£fcta-4s=4丁二第27点：原椁号-1赳把歪壺ti-斗吕.9f45E£強皇肆占类星读業岂：理忘兰-1判别雷数直-龙5.&45S45片笑造案启癸老浜第期点：厦标号-1浏剳函暫狙害24甌2册片糞這果屈类帚倉粟g占..原悔号-1列邑至贮血-:.&CXX并宾建具-i

廉忏等-1分星至崇・L第器点：靠寿唱-1共捌雷螯恆-0-S7224OST辻芝呉-：第対点：厚标号栽別雷裁tflrO.693531第鹑点：廉标嘩-1赳刖鱼盖且■氏F：詰砧判到歯強置-办一7ft7B2a第苛占：厚标号--第37点；M标号^iUffifcfi-0-9S5B5rir韓杲-L第站卓：厚怖号梵捌65J7O5疔負结黑-1第40贞：厦标专-1CKKH5分类這弟・L浜4：点:菜忏号分昱垄晃-：第艷去：宗站考-1判£J商ft崔7分癸整果第43点:厚極号--^SJESttt-o.sawis分宗蜓果-】黑4斗点.廉極号-1分食绘1第衣直：眾询唱-L英捌雷叛宜亠0一B734Bi廿癸莖枭-1第7厚标号_1宜剧西数宜-0.B135O7甘益芸黑-1弟47点：廉存丐-1邑别連羔且•九託阶船分宾獎黑•：耒蛆录忌标唱-1龔判函誥匱-乩QS7C5S二三一-_判別西藪ttt-i”M454】甘呈整吴-:融：:点：厦标号-1直别痢數直■仇783961第5；盍：廉标专1判则站雄囱＞.BS3W二瓶乙占.：屋弼专L拦刮更載宜；.茁：X二第弗点：赋标号1到副底晝厦031&37€3354A： -王到国惹負二“焉爲