~ubuntu-branches/ubuntu/precise/weka/precise

* Tobias Scheffer: Finding Association Rules That Trade Support Optimally against Confidence. In: 5th European Conference on Principles of Data Mining and Knowledge Discovery, 424-435, 2001.

*

* The implementation follows the paper expect for adding a rule to the output of the 'n' best rules. A rule is added if:

* the expected predictive accuracy of this rule is among the 'n' best and it is not subsumed by a rule with at least the same expected predictive accuracy (out of an unpublished manuscript from T. Scheffer).

*

* BibTeX:

* <pre>

* @inproceedings{Scheffer2001,

* author = {Tobias Scheffer},

* booktitle = {5th European Conference on Principles of Data Mining and Knowledge Discovery},

* pages = {424-435},

* publisher = {Springer},

* title = {Finding Association Rules That Trade Support Optimally against Confidence},

* year = {2001}

* }

* </pre>

*

* Valid options are:

* <pre> -N <required number of rules output>

* The required number of rules. (default = 100)</pre>

* <pre> -A

* If set class association rules are mined. (default = no)</pre>

* <pre> -c <the class index>

* The class index. (default = last)</pre>

* @author Stefan Mutter (mutter@cs.waikato.ac.nz)

* @version $Revision: 1.11 $ */

public class PredictiveApriori

extends Associator

implements OptionHandler, CARuleMiner, TechnicalInformationHandler {

/** for serialization */

static final long serialVersionUID = 8109088846865075341L;

/** The minimum support. */

protected int m_premiseCount;

/** The maximum number of rules that are output. */

protected int m_numRules;

100

101

/** The number of rules created for the prior estimation. */

102

protected static final int m_numRandRules = 1000;

103

104

/** The number of intervals used for the prior estimation. */

105

protected static final int m_numIntervals = 100;

106

107

/** The set of all sets of itemsets. */

108

protected FastVector m_Ls;

109

110

/** The same information stored in hash tables. */

111

protected FastVector m_hashtables;

112

113

/** The list of all generated rules. */

114

protected FastVector[] m_allTheRules;

115

116

/** The instances (transactions) to be used for generating

117

the association rules. */

118

protected Instances m_instances;

119

120

/** The hashtable containing the prior probabilities. */

121

protected Hashtable m_priors;

122

123

/** The mid points of the intervals used for the prior estimation. */

124

protected double[] m_midPoints;

125

126

/** The expected predictive accuracy a rule needs to be a candidate for the output. */

127

protected double m_expectation;

128

129

/** The n best rules. */

130

protected TreeSet m_best;

131

132

/** Flag keeping track if the list of the n best rules has changed. */

133

protected boolean m_bestChanged;

134

135

/** Counter for the time of generation for an association rule. */

136

protected int m_count;

137

138

/** The prior estimator. */

139

protected PriorEstimation m_priorEstimator;

140

141

/** The class index. */

142

protected int m_classIndex;

143

144

/** Flag indicating whether class association rules are mined. */

145

protected boolean m_car;

146

147

/**

148

* Returns a string describing this associator

149

* @return a description of the evaluator suitable for

150

* displaying in the explorer/experimenter gui

151

152

public String globalInfo() {

153

return

154

"Class implementing the predictive apriori algorithm to mine "

155

+ "association rules.\n"

156

+ "It searches with an increasing support threshold for the best 'n' "

157

+ "rules concerning a support-based corrected confidence value.\n\n"

158

+ "For more information see:\n\n"

159

+ getTechnicalInformation().toString() + "\n\n"

160

+ "The implementation follows the paper expect for adding a rule to the "

161

+ "output of the 'n' best rules. A rule is added if:\n"

162

+ "the expected predictive accuracy of this rule is among the 'n' best "

163

+ "and it is not subsumed by a rule with at least the same expected "

164

+ "predictive accuracy (out of an unpublished manuscript from T. "

165

+ "Scheffer).";

166

}

167

168

/**

169

* Returns an instance of a TechnicalInformation object, containing

170

* detailed information about the technical background of this class,

171

* e.g., paper reference or book this class is based on.

172

173

* @return the technical information about this class

174

175

public TechnicalInformation getTechnicalInformation() {

176

TechnicalInformation result;

177

178

result = new TechnicalInformation(Type.INPROCEEDINGS);

179

result.setValue(Field.AUTHOR, "Tobias Scheffer");

180

result.setValue(Field.TITLE, "Finding Association Rules That Trade Support Optimally against Confidence");

181

result.setValue(Field.BOOKTITLE, "5th European Conference on Principles of Data Mining and Knowledge Discovery");

182

result.setValue(Field.YEAR, "2001");

183

result.setValue(Field.PAGES, "424-435");

184

result.setValue(Field.PUBLISHER, "Springer");

185

186

return result;

187

}

188

189

/**

190

* Constructor that allows to sets default values for the

191

* minimum confidence and the maximum number of rules

192

* the minimum confidence.

193

194

public PredictiveApriori() {

195

196

resetOptions();

197

}

198

199

/**

200

* Resets the options to the default values.

201

202

public void resetOptions() {

203

204

m_numRules = 105;

205

m_premiseCount = 1;

206

m_best = new TreeSet();

207

m_bestChanged = false;

208

m_expectation = 0;

209

m_count = 1;

210

m_car = false;

211

m_classIndex = -1;

212

m_priors = new Hashtable();

213

214

215

216

}

217

218

/**

219

* Returns default capabilities of the classifier.

220

221

* @return the capabilities of this classifier

222

223

public Capabilities getCapabilities() {

224

Capabilities result = super.getCapabilities();

225

226

// attributes

227

result.enable(Capability.NOMINAL_ATTRIBUTES);

228

result.enable(Capability.MISSING_VALUES);

229

230

// class

231

result.enable(Capability.NOMINAL_CLASS);

232

result.enable(Capability.MISSING_CLASS_VALUES);

233

234

return result;

235

}

236

237

/**

238

* Method that generates all large itemsets with a minimum support, and from

239

* these all association rules.

240

241

* @param instances the instances to be used for generating the associations

242

* @throws Exception if rules can't be built successfully

243

244

public void buildAssociations(Instances instances) throws Exception {

245

246

int temp = m_premiseCount, exactNumber = m_numRules-5;

247

248

m_premiseCount = 1;

249

m_best = new TreeSet();

250

m_bestChanged = false;

251

m_expectation = 0;

252

m_count = 1;

253

m_instances = new Instances(instances);

254

255

if (m_classIndex == -1)

256

m_instances.setClassIndex(m_instances.numAttributes()-1);

257

else if (m_classIndex < m_instances.numAttributes() && m_classIndex >= 0)

258

m_instances.setClassIndex(m_classIndex);

259

else

260

throw new Exception("Invalid class index.");

261

262

// can associator handle the data?

263

getCapabilities().testWithFail(m_instances);

264

265

//prior estimation

266

m_priorEstimator = new PriorEstimation(m_instances,m_numRandRules,m_numIntervals,m_car);

267

m_priors = m_priorEstimator.estimatePrior();

268

m_midPoints = m_priorEstimator.getMidPoints();

269

270

m_Ls = new FastVector();

271

m_hashtables = new FastVector();

272

273

for(int i =1; i < m_instances.numAttributes();i++){

274

m_bestChanged = false;

275

if(!m_car){

276

// find large item sets

277

findLargeItemSets(i);

278

279

//find association rules (rule generation procedure)

280

findRulesQuickly();

281

}

282

else{

283

findLargeCarItemSets(i);

284

findCaRulesQuickly();

285

}

286

287

if(m_bestChanged){

288

temp =m_premiseCount;

289

while(RuleGeneration.expectation(m_premiseCount, m_premiseCount,m_midPoints,m_priors) <= m_expectation){

290

m_premiseCount++;

291

if(m_premiseCount > m_instances.numInstances())

292

break;

293

}

294

}

295

if(m_premiseCount > m_instances.numInstances()){

296

297

// Reserve space for variables

298

m_allTheRules = new FastVector[3];

299

m_allTheRules[0] = new FastVector();

300

m_allTheRules[1] = new FastVector();

301

m_allTheRules[2] = new FastVector();

302

303

int k = 0;

304

while(m_best.size()>0 && exactNumber > 0){

305

m_allTheRules[0].insertElementAt((ItemSet)((RuleItem)m_best.last()).premise(),k);

306

m_allTheRules[1].insertElementAt((ItemSet)((RuleItem)m_best.last()).consequence(),k);

307

m_allTheRules[2].insertElementAt(new Double(((RuleItem)m_best.last()).accuracy()),k);

308

k++;

309

exactNumber--;

310

}

311

return;

312

}

313

314

if(temp != m_premiseCount && m_Ls.size() > 0){

315

FastVector kSets = (FastVector)m_Ls.lastElement();

316

m_Ls.removeElementAt(m_Ls.size()-1);

317

kSets = ItemSet.deleteItemSets(kSets, m_premiseCount,Integer.MAX_VALUE);

318

m_Ls.addElement(kSets);

319

}

320

}

321

322

// Reserve space for variables

323

m_allTheRules = new FastVector[3];

324

m_allTheRules[0] = new FastVector();

325

m_allTheRules[1] = new FastVector();

326

m_allTheRules[2] = new FastVector();

327

328

int k = 0;

329

while(m_best.size()>0 && exactNumber > 0){

330

m_allTheRules[0].insertElementAt((ItemSet)((RuleItem)m_best.last()).premise(),k);

331

m_allTheRules[1].insertElementAt((ItemSet)((RuleItem)m_best.last()).consequence(),k);

332

m_allTheRules[2].insertElementAt(new Double(((RuleItem)m_best.last()).accuracy()),k);

333

k++;

334

exactNumber--;

335

}

336

}

337

338

/**

339

* Method that mines the n best class association rules.

340

* @return an sorted array of FastVector (depending on the expected predictive accuracy) containing the rules and metric information

341

* @param data the instances for which class association rules should be mined

342

* @throws Exception if rules can't be built successfully

343

344

public FastVector[] mineCARs(Instances data) throws Exception{

345

346

m_car = true;

347

m_best = new TreeSet();

348

m_premiseCount = 1;

349

m_bestChanged = false;

350

m_expectation = 0;

351

m_count = 1;

352

buildAssociations(data);

353

FastVector[] allCARRules = new FastVector[3];

354

allCARRules[0] = new FastVector();

355

allCARRules[1] = new FastVector();

356

allCARRules[2] = new FastVector();

357

for(int k =0; k < m_allTheRules[0].size();k++){

358

int[] newPremiseArray = new int[m_instances.numAttributes()-1];

359

int help = 0;

360

for(int j = 0;j < m_instances.numAttributes();j++){

361

if(j != m_instances.classIndex()){

362

newPremiseArray[help] = ((ItemSet)m_allTheRules[0].elementAt(k)).itemAt(j);

363

help++;

364

}

365

}

366

ItemSet newPremise = new ItemSet(m_instances.numInstances(), newPremiseArray);

367

newPremise.setCounter (((ItemSet)m_allTheRules[0].elementAt(k)).counter());

368

allCARRules[0].addElement(newPremise);

369

int[] newConsArray = new int[1];

370

newConsArray[0] =((ItemSet)m_allTheRules[1].elementAt(k)).itemAt(m_instances.classIndex());

371

ItemSet newCons = new ItemSet(m_instances.numInstances(), newConsArray);

372

newCons.setCounter(((ItemSet)m_allTheRules[1].elementAt(k)).counter());

373

allCARRules[1].addElement(newCons);

374

allCARRules[2].addElement(m_allTheRules[2].elementAt(k));

375

}

376

377

return allCARRules;

378

}

379

380

/**

381

* Gets the instances without the class attribute

382

* @return instances without class attribute

383

384

public Instances getInstancesNoClass() {

385

386

Instances noClass = null;

387

try{

388

noClass = LabeledItemSet.divide(m_instances,false);

389

}

390

catch(Exception e){

391

e.printStackTrace();

392

System.out.println("\n"+e.getMessage());

393

}

394

//System.out.println(noClass);

395

return noClass;

396

}

397

398

/**

399

* Gets the class attribute of all instances

400

* @return Instances containing only the class attribute

401

402

public Instances getInstancesOnlyClass() {

403

404

Instances onlyClass = null;

405

try{

406

onlyClass = LabeledItemSet.divide(m_instances,true);

407

}

408

catch(Exception e){

409

e.printStackTrace();

410

System.out.println("\n"+e.getMessage());

411

}

412

return onlyClass;

413

414

}

415

416

/**

417

* Returns an enumeration describing the available options.

418

419

* @return an enumeration of all the available options.

420

421

public Enumeration listOptions() {

422

423

String string1 = "\tThe required number of rules. (default = " + (m_numRules-5) + ")",

424

string2 = "\tIf set class association rules are mined. (default = no)",

425

string3 = "\tThe class index. (default = last)";

426

FastVector newVector = new FastVector(3);

427

428

newVector.addElement(new Option(string1, "N", 1,

429

"-N <required number of rules output>"));

430

newVector.addElement(new Option(string2, "A", 0,

431

"-A"));

432

newVector.addElement(new Option(string3, "c", 1,

433

"-c <the class index>"));

434

return newVector.elements();

435

}

436

437

438

/**

439

* Parses a given list of options.

440

441

442

* Valid options are:

443

444

* <pre> -N <required number of rules output>

445

* The required number of rules. (default = 100)</pre>

446

447

* <pre> -A

448

* If set class association rules are mined. (default = no)</pre>

449

450

* <pre> -c <the class index>

451

* The class index. (default = last)</pre>

452

453

454

455

* @param options the list of options as an array of strings

456

* @throws Exception if an option is not supported

457

458

public void setOptions(String[] options) throws Exception {

459

460

resetOptions();

461

462

String numRulesString = Utils.getOption('N', options);

463

if (numRulesString.length() != 0)

464

m_numRules = Integer.parseInt(numRulesString)+5;

465

else

466

m_numRules = Integer.MAX_VALUE;

467

468

String classIndexString = Utils.getOption('c',options);

469

if (classIndexString.length() != 0)

470

m_classIndex = Integer.parseInt(classIndexString);

471

472

m_car = Utils.getFlag('A', options);

473

}

474

475

/**

476

* Gets the current settings of the PredictiveApriori object.

477

478

* @return an array of strings suitable for passing to setOptions

479

480

public String [] getOptions() {

481

Vector result;

482

483

result = new Vector();

484

485

result.add("-N");

486

result.add("" + (m_numRules-5));

487

488

if (m_car)

489

result.add("-A");

490

491

result.add("-c");

492

result.add("" + m_classIndex);

493

494

return (String[]) result.toArray(new String[result.size()]);

495

}

496

497

498

/**

499

* Outputs the association rules.

500

501

* @return a string representation of the model

502

503

public String toString() {

504

505

StringBuffer text = new StringBuffer();

506

507

if (m_allTheRules[0].size() == 0)

508

return "\nNo large itemsets and rules found!\n";

509

text.append("\nPredictiveApriori\n===================\n\n");

510

text.append("\nBest rules found:\n\n");

511

512

for (int i = 0; i < m_allTheRules[0].size(); i++) {

513

text.append(Utils.doubleToString((double)i+1,

514

(int)(Math.log(m_numRules)/Math.log(10)+1),0)+

515

". " + ((ItemSet)m_allTheRules[0].elementAt(i)).

516

toString(m_instances)

517

+ " ==> " + ((ItemSet)m_allTheRules[1].elementAt(i)).

518

toString(m_instances) +" acc:("+

519

Utils.doubleToString(((Double)m_allTheRules[2].

520

elementAt(i)).doubleValue(),5)+")");

521

522

text.append('\n');

523

}

524

525

526

return text.toString();

527

}

528

529

530

/**

531

* Returns the tip text for this property

532

* @return tip text for this property suitable for

533

* displaying in the explorer/experimenter gui

534

535

public String numRulesTipText() {

536

return "Number of rules to find.";

537

}

538

539

/**

540

* Get the value of the number of required rules.

541

542

* @return Value of the number of required rules.

543

544

public int getNumRules() {

545

546

return m_numRules-5;

547

}

548

549

/**

550

* Set the value of required rules.

551

552

* @param v Value to assign to number of required rules.

553

554

public void setNumRules(int v) {

555

556

m_numRules = v+5;

557

}

558

559

/**

560

* Sets the class index

561

* @param index the index of the class attribute

562

563

public void setClassIndex(int index){

564

565

m_classIndex = index;

566

}

567

568

/**

569

* Gets the index of the class attribute

570

* @return the index of the class attribute

571

572

public int getClassIndex(){

573

574

return m_classIndex;

575

}

576

577

/**

578

* Returns the tip text for this property

579

* @return tip text for this property suitable for

580

* displaying in the explorer/experimenter gui

581

582

public String classIndexTipText() {

583

return "Index of the class attribute.\n If set to -1, the last attribute will be taken as the class attribute.";

584

}

585

586

/**

587

* Sets class association rule mining

588

* @param flag if class association rules are mined, false otherwise

589

590

public void setCar(boolean flag){

591

592

m_car = flag;

593

}

594

595

/**

596

* Gets whether class association ruels are mined

597

* @return true if class association rules are mined, false otherwise

598

599

public boolean getCar(){

600

601

return m_car;

602

}

603

604

/**

605

* Returns the tip text for this property

606

* @return tip text for this property suitable for

607

* displaying in the explorer/experimenter gui

608

609

public String carTipText() {

610

return "If enabled class association rules are mined instead of (general) association rules.";

611

}

612

613

/**

614

* Returns the metric string for the chosen metric type.

615

* Predictive apriori uses the estimated predictive accuracy.

616

* Therefore the metric string is "acc".

617

* @return string "acc"

618

619

public String metricString() {

620

621

return "acc";

622

}

623

624

625

/**

626

* Method that finds all large itemsets for the given set of instances.

627

628

* @param index the instances to be used

629

* @throws Exception if an attribute is numeric

630

631

private void findLargeItemSets(int index) throws Exception {

632

633

FastVector kMinusOneSets, kSets = new FastVector();

634

Hashtable hashtable;

635

int i = 0;

636

// Find large itemsets

637

//of length 1

638

if(index == 1){

639

kSets = ItemSet.singletons(m_instances);

640

ItemSet.upDateCounters(kSets, m_instances);

641

kSets = ItemSet.deleteItemSets(kSets, m_premiseCount,Integer.MAX_VALUE);

642

if (kSets.size() == 0)

643

return;

644

m_Ls.addElement(kSets);

645

}

646

//of length > 1

647

if(index >1){

648

if(m_Ls.size() > 0)

649

kSets = (FastVector)m_Ls.lastElement();

650

m_Ls.removeAllElements();

651

i = index-2;

652

kMinusOneSets = kSets;

653

kSets = ItemSet.mergeAllItemSets(kMinusOneSets, i, m_instances.numInstances());

654

hashtable = ItemSet.getHashtable(kMinusOneSets, kMinusOneSets.size());

655

m_hashtables.addElement(hashtable);

656

kSets = ItemSet.pruneItemSets(kSets, hashtable);

657

ItemSet.upDateCounters(kSets, m_instances);

658

kSets = ItemSet.deleteItemSets(kSets, m_premiseCount,Integer.MAX_VALUE);

659

if(kSets.size() == 0)

660

return;

661

m_Ls.addElement(kSets);

662

}

663

}

664

665

666

667

668

/**

669

* Method that finds all association rules.

670

671

* @throws Exception if an attribute is numeric

672

673

private void findRulesQuickly() throws Exception {

674

675

RuleGeneration currentItemSet;

676

677

// Build rules

678

for (int j = 0; j < m_Ls.size(); j++) {

679

FastVector currentItemSets = (FastVector)m_Ls.elementAt(j);

680

Enumeration enumItemSets = currentItemSets.elements();

681

while (enumItemSets.hasMoreElements()) {

682

currentItemSet = new RuleGeneration((ItemSet)enumItemSets.nextElement());

683

m_best = currentItemSet.generateRules(m_numRules, m_midPoints,m_priors,m_expectation,

684

m_instances,m_best,m_count);

685

686

m_count = currentItemSet.m_count;

687

if(!m_bestChanged && currentItemSet.m_change)

688

m_bestChanged = true;

689

//update minimum expected predictive accuracy to get into the n best

690

if(m_best.size() >0)

691

m_expectation = ((RuleItem)m_best.first()).accuracy();

692

else m_expectation =0;

693

}

694

}

695

}

696

697

698

/**

699

* Method that finds all large itemsets for class association rule mining for the given set of instances.

700

* @param index the size of the large item sets

701

* @throws Exception if an attribute is numeric

702

703

private void findLargeCarItemSets(int index) throws Exception {

704

705

FastVector kMinusOneSets, kSets = new FastVector();

706

Hashtable hashtable;

707

int i = 0;

708

// Find large itemsets

709

if(index == 1){

710

kSets = CaRuleGeneration.singletons(m_instances);

711

ItemSet.upDateCounters(kSets, m_instances);

712

kSets = ItemSet.deleteItemSets(kSets, m_premiseCount,Integer.MAX_VALUE);

713

if (kSets.size() == 0)

714

return;

715

m_Ls.addElement(kSets);

716

}

717

718

if(index >1){

719

if(m_Ls.size() > 0)

720

kSets = (FastVector)m_Ls.lastElement();

721

m_Ls.removeAllElements();

722

i = index-2;

723

kMinusOneSets = kSets;

724

kSets = ItemSet.mergeAllItemSets(kMinusOneSets, i, m_instances.numInstances());

725

hashtable = ItemSet.getHashtable(kMinusOneSets, kMinusOneSets.size());

726

m_hashtables.addElement(hashtable);

727

kSets = ItemSet.pruneItemSets(kSets, hashtable);

728

ItemSet.upDateCounters(kSets, m_instances);

729

kSets = ItemSet.deleteItemSets(kSets, m_premiseCount,Integer.MAX_VALUE);

730

if(kSets.size() == 0)

731

return;

732

m_Ls.addElement(kSets);

733

}

734

}

735

736

/**

737

* Method that finds all class association rules.

738

739

* @throws Exception if an attribute is numeric

740

741

private void findCaRulesQuickly() throws Exception {

742

743

CaRuleGeneration currentLItemSet;

744

// Build rules

745

for (int j = 0; j < m_Ls.size(); j++) {

746

FastVector currentItemSets = (FastVector)m_Ls.elementAt(j);

747

Enumeration enumItemSets = currentItemSets.elements();

748

while (enumItemSets.hasMoreElements()) {

749

currentLItemSet = new CaRuleGeneration((ItemSet)enumItemSets.nextElement());

750

m_best = currentLItemSet.generateRules(m_numRules, m_midPoints,m_priors,m_expectation,

751

m_instances,m_best,m_count);

752

m_count = currentLItemSet.count();

753

if(!m_bestChanged && currentLItemSet.change())

754

m_bestChanged = true;

755

if(m_best.size() >0)

756

m_expectation = ((RuleItem)m_best.first()).accuracy();

757

else

758

m_expectation =0;

759

}

760

}

761

}

762

763

/**

764

* returns all the rules

765

766

* @return all the rules

767

* @see #m_allTheRules

768

769

public FastVector[] getAllTheRules() {

770

return m_allTheRules;

771

}

772

773

/**

774

* Main method.

775

776

* @param args the commandline parameters

777

778

public static void main(String[] args) {

779

runAssociator(new PredictiveApriori(), args);

780

}

781

}

782

Older »